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

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

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

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

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

输出一个整数，表示社区中最多能够领到礼物的儿童数。

样例 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 \le 10^{18}。

月赛贪心