题目描述

有 $N$ 种礼物。第 $i$ 种礼物的单价为 $P_i$ 元，有 $C_i$ 名儿童喜欢这种礼物。每名儿童最多需要一份自己喜欢的礼物，因此第 $i$ 种礼物最多需要购买 $C_i$ 份。

现有 $M$ 元预算，求最多可以让多少名儿童得到自己喜欢的礼物。

输入格式

第一行包含两个整数 $N,M$。

接下来 $N$ 行，每行包含两个整数 $P_i,C_i$，分别表示一种礼物的单价和喜欢它的儿童人数。

输出格式

输出一个整数，表示最多可以得到礼物的儿童人数。

5 20
10 2
8 3
12 1
15 1
4 1

3

6 28
1 1
3 1
6 1
2 1
12 1
15 1

5

数据范围与提示

• $1 \le N \le 10^5$
• $1 \le M \le 10^{18}$
• $1 \le P_i,C_i,P_i \times C_i \le 10^{18}$