第一行二個(gè)數(shù)n(n≤500)，m(m≤6000)，其中n代表希望購(gòu)買(mǎi)的獎(jiǎng)品的種數(shù)，m表示撥款金額。

接下來(lái)n行，每行3個(gè)數(shù)，v、w、s，分別表示第I種獎(jiǎng)品的價(jià)格、價(jià)值（價(jià)格與價(jià)值是不同的概念）和能購(gòu)買(mǎi)的最大數(shù)量（買(mǎi)0件到s件均可），其中v≤100，w≤1000，s≤10。

5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

1040