Description

有 n 件物品, 每件物品有一个价值和一个重量，分别记为：$v_1;v_2; …v_n w_1;w_2; …w_n$其中所有的 重量wi 均为整数。 现有一个背包，其最大载重量为C，要求从这n件物品中任取若干件（这些物品要么被装入要么被留下）。问背包中装入哪些物品可使得所装物品的价值和最大？

Format

Input

第1行：2个整数n(1<=n<=1000)和C(1<=C<=10000)，分别表示物品的件数和背包的最大载重量。
第2-n+1行：每行2个用空格分开的整数，第i+1行的整数表示第i件物品的重量wi和价值vi(1<=vi,wi<=10000)。

Output

第1行：1个整数，表示背包所能装下的物品的最大总价值。

Samples

4 5
2 3
3 4
4 5
5 6

7

Limitation

1s, 1024KiB for each test case.