4279: 圣诞礼物

内存限制：512 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：0 解决：0

题目描述

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

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

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

输入

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

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

输出

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

样例输入 复制 

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

样例输出 复制 

3

提示

样例

输入
复制 

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

输入
复制 

16 38
10 2
5 1
2 8
3 4
4 5
5 2
9 1
12 3
15 6
18 7
12 1
8 2
3 4
10 6
3 5
5 1

输出
复制 

15
说明

样例 1 说明

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

数据范围

测试点 1 满足 ��=1，1≤�≤20。

测试点 2∼4 满足 1≤�≤20。

测试点 5∼6 满足 1≤�≤1000。

测试点 7∼10 满足 1≤�≤105，1≤�≤1018，1≤��,��≤1018。

来源/分类

提交提交记录统计露一手!