FJ 开始经营小摆件生意，买卖奶牛圣诞树挂饰之类的小物件。他知道，从包含 $N$ 种（$1 \le N \le 100$）不同奶牛摆件的目录中进的每件货都能卖掉，每种摆件想买多少就买多少。他只有 $M$（$1 \le M \le 100,000$）资金可投资，但希望在营业第一年结束时，使利润（定义稍有不同寻常）最大。

第 $i$ 种摆件的购入成本为 $C_i$（$1 \le C_i \le 100,000$），每卖出一件获得收入 $R_i$（$1 \le R_i \le 100,000$），利润为 $R_i-C_i$。FJ 可以任意搭配出售的摆件。购买时不必花光全部资金。

FJ 在营业第一年结束时能获得的最大总利润（$profit = initial\_cash - all\_costs + all\_sales$）是多少？保证这个数小于 $1,000,000,000$。

考虑 FJ 只有 $3$ 种摆件、初始资金为 $M=17$ 的情况。各摆件的成本和收入如下：

             摆件     成本     收入
               #        C_i       R_i
               1         2         4
               2         5         6
               3         3         7

此时 FJ 应花 $15$ 购买 $5$ 件第 $3$ 种摆件，再花 $2$ 购买 $1$ 件第 $1$ 种摆件，共花 $17$。利润为 $5 * (7-3) + 1 * (4-2) = 5*4 + 1*2 = 22$。在给定成本与收入结构下，他不可能做得更好。

注意：第二个测试用例很有挑战性，但我们的答案是正确的。

输入格式

• 第 1 行：两个用空格分隔的整数 $N$ 和 $M$。

• 第 $2..N+1$ 行：第 $i+1$ 行包含两个用空格分隔的整数 $C_i$ 和 $R_i$。

输出格式

• 第 1 行：给定成本和收入时 FJ 能获得的最大利润。

样例

输入格式 1

3 17
2 4
5 6
3 7

输出格式 1

22

题目来源：传统题目，2009 年。