Migrated from Lutece 1691 这是一道比CCCC简单题经典的中档题

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

谭爷曾经是个很爱喝豆奶的男人，UESTC小卖部有N种豆奶，每种豆奶的数量为C1，C2......Cn。谭爷在抢劫小卖部的时候会从中任选若干件放在容量为W的谭爷巨型背包里，每种豆奶的体积为W1，W2......Wn（Wi为整数），与之相对应的价值为P1,P2......Pn（Pi为整数）。求背包能够容纳的豆奶最大价值。

Input

第1行，两个整数N和W，中间用空格隔开。N为豆奶的种类数，W为背包的容量。(1 <= N <= 100，1 <= W <= 50000) 第2 - N + 1行，每行3个整数Wi，Pi和Ci，分别是豆奶体积、价值和数量。(1 <= Wi, Pi <= 10000， 1 <= Ci <= 200)

Output

谭爷可以抢到的最大的豆奶价值之和。

Samples

3 6
2 2 5
3 3 8
1 4 1

9

Resources

2017 UESTC Training for Dynamic Programming