日暮堂前花蕊娇， 争拈小笔上床描， 绣成安向春园里， 引得黄莺下柳条。 ——胡令能《咏绣障》         古时女子四德中有一项——女红。女红的精巧程度对于女子来说是十分重要的。韵哲君十分爱好女红，尤其是刺绣。 当衬衣公司的Immortal掌柜在知道韵哲君有这一手艺后，交给韵哲君一个任务：在他所提供的各种各样大小的布上绣上精美的花纹（每匹布上只能绣一种花纹）。有3种花纹可以供韵哲君选择，每一体积布上的每种花纹的美观度c和所占体积v都不同。Immortal带了一个不知道是否足够装下所有刺绣作品的包，请你帮忙计算一下，Immortal的包里所能装下作品的最大美观度。

第一行为两个数n（布的匹数，0< n< =100）、m（包的容积，0< m< =8000）；
第二行到第四行，每行有3个数据：花纹种类编号z（0< z< maxint）、每一体积布上这种花纹的美观度c[z]（0< c[z]< maxint）和每一体积布上绣的这种花纹的体积v[z]（0< z< maxint）；
第五行到n+4行每行有2个数据，分别是第i匹布的体积b[i]（0< b[i]< &nbsp maxint）和这匹布上所绣花纹的种类编号z[i]。

输出一个正整数，为Immortal的包里所能装下作品的最大美观度。

5 100
8 2001 5
4 9 8
3 74 4
111 4
79 8
6 3
5 8
23 4
 ·   \n
 ·    · \n
 · · \n
 ·  · \n
   · \n
  · \n
 · \n
 · \n
  · \n

10449
     \n