题目描述

强哥在码头发现了一批珍贵的货物！共有 $N$ 种不同类型的货物，每种货物都有：

• 每箱的价值 $A_i$（数值越大越值钱）
• 可用的箱数 $B_i$ 箱

强哥的货船最大载重量为 $W$ 箱。货船的总价值是所有装载货物的价值之和。请你帮强哥计算出他的货船能够装载的最大总价值是多少！

数据范围

• 所有输入均为整数。
• $1 \le N \le 3 \times 10^5$
• $1 \le W \le 3 \times 10^8$
• $1 \le A_i \le 10^9$
• $1 \le B_i \le 1000$

输入格式

N W
A₁ B₁
A₂ B₂
...
A_N B_N

输出格式

输出一个整数表示最大可能的总价值

输入样例1

3 5
3 1
4 2
2 3

输出样例1

15

输入样例2

4 100
6 2
1 5
3 9
8 7

输出样例2

100