题目描述

为了庆祝一年一度的圣诞节，社区决定给本社区的儿童准备礼物。礼品公司的仓库中有 $N$ 种不同的礼物，每种礼物的库存数量是无限的，但不同的儿童对不同礼物的喜好各不相同。

根据调查数据，有 $C_i$ 名儿童喜欢第 $i$ 种礼物，这种礼物的采购单价为 $P_i$ 元。

社区为本次圣诞礼物准备了 $M$ 元的采购预算。请你编程计算出，在有限的预算内，最多可以使得多少名儿童领到自己喜欢的礼物。

输入格式

第一行包含两个正整数 $N$ 和 $M$，分别表示礼物的种类数和社区采购的预算。

接下来 $N$ 行，每行包含两个正整数 $P_i$ 和 $C_i$，分别表示第 $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 说明：社区有 $20$ 元预算，可以采购 $2$ 个第 $2$ 种礼物，花费 $2 \times 8=16$ 元，再采购 $1$ 个第 $5$ 种礼物，花费 $4$ 元，共花费 $20$ 元。可以让最多 $3$ 个儿童领到自己喜欢的礼物。

数据范围

• 测试点 $1$：$C_i=1$，$1 \le N \le 20$
• 测试点 $2 \sim 4$：$1 \le N \le 20$
• 测试点 $5 \sim 6$：$1 \le N \le 1000$
• 测试点 $7 \sim 10$：$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}$