该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P3027 [USACO10OCT] Making Money G

题目背景

小明带着 $m$ 块钱 走进一个山洞采购宝石，然后带着采购的宝石到市场去卖。

山洞里有 $n$ 种宝石（每种宝石无限多个），第 $i$ 种 宝石的价格为 $c_i$，拿到宝石店能卖 $r_i$ 块钱。

假如小明能在市场卖掉所有采购的宝石，求小明所获得的最大利润（未花完的钱算入利润里面）的最大值。

【输入文件】

第一行两个整数 $n \ m \ （1 \le n \le 100 , 1 \le m \le 10^5)$。

下来 $n$ 行，每行两个整数 $c_i \ r_i$（ $0 \le c_i，r_i \le 10^5$）。

【输出文件】

输出一行一个整数，即小明所获得的最大利润（未花完的钱算入利润里面）的最大值。

输入 #1

3 17 
2 4 
5 6 
3 7

输出 #1

22

输入 #2

3 16
2 4 
5 6 
3 7

输出 #2

21