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

对于第i个金矿，需要投入Ci个的费用，能挖出来Wi个单位的金子。

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

### 输入格式:

第一行两个整数，分别为N和M,1 ≤N,M ≤ 2000;
接下来N行每行两个整数，第i+1行为Ci 和Wi,1 ≤Wi≤ 300000 。

### 输出格式:

一行一个整数

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

对于第i个金矿，需要投入Ci个的费用，能挖出来Wi个单位的金子。

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

### 输入格式:

第一行两个整数，分别为N和M,1 ≤N,M ≤ 2000;
接下来N行每行两个整数，第i+1行为Ci 和Wi,1 ≤Wi≤ 300000 。

### 输出格式:

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

### 输入样例:

in
3 10
8 5
3 4
6 3


### 输出样例:

out
7







答案：若无答案欢迎评论