该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

输入格式

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

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

输出格式

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

样例输入 1

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

样例输出 1

3

样例输入 2

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

样例输出 2

5

提示

样例 1 说明： 社区有 20 元预算，可以采购 2 个第 2 种礼物，花费 2×8=16 元，再采购 1 个第 5 种礼物，花费 4 元，共花费 20 元。可以让最多 3 个儿童领到自己喜欢的礼物。

数据范围：

• 测试点 1 满足 Cᵢ=1，1≤N≤20。
• 测试点 2∼4 满足 1≤N≤20。
• 测试点 5∼6 满足 1≤N≤1000。
• 测试点 7∼10 满足 1≤N≤10⁵，1≤M≤10¹⁸，1≤Pᵢ,Cᵢ,Pᵢ×Cᵢ≤10¹⁸。