Migrated from Lutece 2067 如何才能保留那些美好

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

进入命运石之门的子辉，看到的是数量巨大的记忆碎片，深知很难把这些美好记忆都带回去给 Sakura 的子辉感到深深的无力。

一共有n块记忆碎片，每块记忆碎片的体积为 $V_i$ , 每块的美好值为 $W_i$，子辉现在有一个可以装最大体积为m的魔法包，子辉想知道自己最多可以带多大的美好值的记忆碎片回去给 Sakura。

Input

第一行包含两个整数 $n$ 和 $m$。

第二行到第 $n+1$ 行每行两个整数，分别表示1-n块记忆碎片的体积 $V_i$ 和 $W_i$ 美好值。

$1<= n <=100$

$1<= m <= 10^6$

$0 <= V_i <= m$

$0 <= W_i <= 100$

Output

输出包含一个整数，表示最多可以带回去多大的美好值的记忆碎片。

Samples

3 70
71 100 
69 1 
1 2

3

Resources

2018 UESTC Training for Dynamic Programming