古韵之刺绣

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

日暮堂前花蕊娇,
争拈小笔上床描,
绣成安向春园里,
引得黄莺下柳条。

——胡令能《咏绣障》
古时女子四德中有一项——女红。女红的精巧程度对于女子来说是十分重要的。韵哲君十分爱好女红,尤其是刺绣。

当衬衣公司的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]< maxint)和这匹布上所绣花纹的种类编号z[i]。

输出格式

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

样例1

样例输入1

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

样例输出1

10449

第二届“古韵OI”邀请赛

未参加
状态
已结束
规则
OI
题目
4
开始于
2008-08-07 18:30
结束于
2008-08-07 22:00
持续时间
3.5 小时
主持人
参赛人数
872