2401：新年礼物（gifts）
文件提交：文件名：gifts
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
1
提交：285
解决：35
题目描述
因为今年NOIP比赛大家成绩都很好，为了奖励大家，在新年的时候陈老师想要从网上买一些礼物寄给大家。陈老师调研了大家喜欢的礼物，并且一一上网查到了商品的价格，统计出了一张表。
陈老师有n名学生，每名学生想要的礼物都有一个价格pi和邮费si，也就是说，购买这件礼物需要付pi+si元。陈老师只有b元的预算，他想给尽量多的同学购买礼物。陈老师在整理购物车的时候发现，tb也给了他一个新年礼物，那就是一张优
惠券。这张优惠券能够让一个商品以半价购买，既使用了优惠券的商品需要付pi/2+si元。
输入
从文件 gifts.in 中读入数据。
第1行有2个正整数，表示共有n名学生和b元钱。
第2到n+1行，每行有两个正整数，分别代表这名同学想要的礼物的价格pi和邮
费si，数据保证pi一定为偶数。
输出
输出到文件 gifts.out 中。
输出一行一个整数，表示要陈老师能够购买的最多礼物数
样例输入
5 24
4 2
2 0
8 1
6 3
12 5样例输出
4提示
【样例 1 解释】
共有5名学生，有24元的预算。如果给第1~4名同学购买礼物，并且在购买第三名同学的礼物时使用优惠券的话，总共会花(4+2)+(2+0)+(4+1)+(6+3) = 22元，满足预算。容易发现陈老师无法给全部5名同学都买礼物，因此答案为4。
需要注意的是，在给1~4名同学买礼物时，这张优惠券如果在第1名同学或第4名同学的礼物上使用，也可以满足预算条件 【输入样例2】
10 17
16 33
18 31
15 37
17 34
20 35
15 38
15 31
14 35
16 37
10 38
0
【输入样例3】
15 596
57 3
85 3
61 3
98 3
85 4
47 3
42 4
95 3
85 3
82 3
41 4
64 4
36 4
100 4
66 3
【输出样例3】
10
【数据范围】
对于20%的数据，1 ≤ n ≤ 10，1 ≤ b，pi，si ≤ 1000；
对于60%的数据，1 ≤ n ≤ 5000，1 ≤ b，pi，si ≤ 109；
对于100%的数据，1 ≤ n ≤ 200000，1 ≤ b，pi，si ≤ 109。