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

题目背景

\(\small\sf\red{tmdj}\)知道了自己要用的能量之后，他便开始规划自己的能量补充。

题目描述

有\(n\)个食物，第\(i\)个食物的价格是\(w_i\)，第\(i\)个食物能提供的能量为\(v_i\)。\(\small\sf\red{tmdj}\)有\(m\)元，问\(\small\sf\red{tmdj}\)最多可以补充多少能量。

输入格式

第一行两个整数，\(n\)和\(m\)，\(n\)表示食物总量，\(m\)表示\(\small\sf\red{tmdj}\)有的钱数

接下来\(n\)行，一行两个整数，表示食物能提供的能量和食物的价格

输出格式

样例 #1

样例输入 #1

5 3000
2500 100
1700 2400
1300 1400
2700 2000
2000 1200

样例输出 #1

5800

提示

\(1\) \(\le\) \(n\) \(\le\) \(25\)
\(1\) \(\le\) \(m\) \(\le\) \(30000\)