B. 国王的金矿

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

国王在他的国家发现了NNN座金矿,为了描述方便,我们给他们从1到NNN编号。

对于第iii个金矿,需要投入CiC_iCi个的费用,能挖出来WiW_iWi个单位的金子。

现在国王想开挖这些金矿,但是最多只有MMM个软妹币用于投入,问最多可以挖出来多少单位的金子。

输入格式

第一行两个整数,分别为NNNMMM

接下来N行每行两个整数,第i+1i+1i+1行为CiC_iCiWiW_iWi

输出格式

一行一个整数,为最多可以挖出来多少单位的金子。

样例

####样例输入

3 10
8 5
3 4
6 3

####样例输出

7

数据范围与提示

1 ≤\le NNN,MMM ≤\le 2000

1 ≤\le WiW_iWi ≤\le 300000