古时女子四德中有一项——女红。女红的精巧程度对于女子来说是十分重要的。韵哲君十分爱好女红，尤其是刺绣。 当衬衣公司的Immortal掌柜在知道韵哲君有这一手艺后，交给韵哲君一个任务：在他所提供的各种各样大小的布上绣上精美的花纹（每匹布上只能绣一种花纹）。有3种花纹可以供韵哲君选择，每一体积布上的每种花纹的美观度c和所占体积v都不同。Immortal带了一个不知道是否足够装下所有刺绣作品的包，请你帮忙计算一下，Immortal的包里所能装下作品的最大美观度。

第一行为两个数n（布的匹数，0

输出

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

样例输入

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

样例输出

10449

来源/分类

第二届“古韵OI”邀请赛 

[提交] [状态]