题目描述

     今天Jungle接到一个工作，项目代码中需要进行多项排查，代码中什么内存泄露、数组越界、魔鬼数字等等这些问题多得数不清，PL要求Jungle在TR4点之前尽可能地排查更多有价值的问题。

     像内存泄露和数组越界这些问题价值就比较高，魔鬼数字这类价值稍低。
     现在，已知有N项排查，以及每一项排查检视出来的时间W和价值V，且留给Jungle的时间只有K。假设每一项需要排查的问题存在无数个，Jungle应该如何安排时间，才能检视出最大的价值呢？

输入描述

第一行输入N和K（1<=K<= 1000 ,  1<= N<=10000）；

接下来N行是每项排查需要的时间W和价值V( 0 < W ， V <= 1000)。

输出描述

输出包含一个整数，Jungle所能检视出的问题的最大总价值。

示例

提示

样例中，排查10个第一项排查，即可得到最大价值20。

input

9 17
20 8
16 17
14 6
17 6
9 18
17 7
15 20
12 15
18 3

output

20

相关标签