Migrated from Lutece 1606 难喝的饮料

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

图文无关

wdk喜欢跑步，每天晚上他都要跑上半小时。跑得大汗淋漓后，他不得不喝点饮料补充水分。

饮料有两大类，一类是饮用水，可以无限取用。一类是苏打水，每种只有一瓶。

wdk不喜欢喝饮料，每喝一瓶饮料他的难受程度就上升$b_i$。他不想难受得满地打滚，所以他不会让自己的难受程度高于$K$。

每瓶饮料可以补充水分$a_i$。此外，wdk是个有始有终的人，他要么喝下一整瓶水，要么不喝。

现在wdk想问问你他最多能补充多少水分呢?

Input

第一行两个数$1<=n<=2\times10^4和0<=K<=10^4$，表示一共有$n$种饮料，难受阙值为$K$。

接下来$n$行，每行三个数$t, 0<=a<=10^4, 0<b<=10^4$，$a,b$含义同题意，$t=1$表示是饮用水，$t=2$表示是苏打水。

Output

一个数，表示最多补充的水分。

Samples

3 10
1 3 5
2 4 6
1 2 3

6

Note

良心出题人！test1 为样例！ (然而最极端的数据在41和42)

Resources

2017 UESTC Training for Dynamic Programming