C~K的奖券

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

超市举行兑奖活动啦!!!

C~K 费劲心力,终于搞到了 m 张兑奖券,而奖品区有 n 件奖品,分别标号为 1~n,其中第 i 件奖品需要 need(i) 张奖券进行兑换,同时也只能兑换一次,为了辛苦得到的奖券不能够浪费,C~K 给每件奖品都评了分,其中第i件奖品的评分值为 value(i),表示 C~K 对这件奖品的喜好值,现在他想知道,凭借他手上的这些奖券,可以换到哪些奖品,使得这些奖品的喜好值最大。

Input

输入数据有多组(数据组数不超过 100),到 EOF 结束。

每一组测试数据第一行为两个正整数 n, m。表示奖品的个数及 C~K 手中的奖券数。

接下来 n 行描述每一行描述一个奖品,其中第 i 行为两个整数 need(i) 和 value(i),意义如前文所述。

(0 < n <= 500, 0 < m <= 10^5, 0 < need(i) <= 2*10^5, 0 < value(i) <= 10^3)

Output

对于每组输入的数据输出一个整数 ans,代表 C~K可 以获得的总喜好值。

Sample Input

1 3
1 1

Sample Output

1

Hint

Source

【2017年寒假集训 结训赛2】C~K