奶酪

题目描述

有 $n$ 种奶酪，总共 $w$ 克。 每种奶酪放在披萨上能提升 $A_i$ 的美味度​，但是最多放 $B_i$ 克。 求能产生的最大美味度。

输入格式

第一行有两个数，为 $n$ 和 $m$。

接下来有 $n$ 行，每一行有 $A_i$，$B_i$ ​两个数，意思如题目所示。

输出格式

输出一行一个整数,为可能的最大美味度。

样例 #1

样例输入 #1

3 5
3 1
4 2
2 3

样例输出 #1

15

数据范围

• $1\le N\le3\times 10^5$
• $1\le W\le3\times 10^8$
• $1\le A_i \le 10^9$
• $1\le B_i \le 1000$