测试数据来自 system/1459

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　H老师计划给他的 \(n\) 个学生送贺卡，由于每位同学生有不同得性格特点，因此他们对贺卡得品质要求不同。具体来说就是给第 \(i\) 个学生购买贺卡要花费 \(a_i\) 元，为了送贺卡活动更有仪式感，H老师还准备对每张贺卡做精美的封面包装，就是说每张贺卡还需要封面包装费 \(b_i\) 元。

　　H老师有一张通用优惠券，使用它可以半价购买一张贺卡，即如果优惠券用于购买学生 \(i\) 的贺卡，则需要的总费用为是 \(⌊a_i/2⌋+b_i\) 元（其中⌊ ⌋取下整）。

　　现在H老师预算 \(s\) 元购买贺卡，请你帮助它计算最多能给多少学生送贺卡。

【输入格式】

　　第一行是两个正整数 \(n\) 和 \(s\)，中间用一个空格隔开，分表表示学生总人数和H老师预算用于购买贺卡的钱数（单位：元）。
　　接下来的 \(n\) 行，每行包含两个非负整数 \(a_i\) 和 \(b_i\) 中间用一个空格隔开，第 \(i+1\) 行的正整数分别表示第 \(i\) 张贺卡价格和包装价格（单位：元）。

【输出格式】

　　只有一行，包含一个整数，表示H老师送出贺卡的最多学生数。

【输入输出样例1】

　Input

6 24
4 2
2 0
8 1
12 5
6 3
8 5

　Output

4

【输入输出样例1说明】

　　有 6 位学生，它们需要的贺卡售价和包装花费分别为（4,2）、（2,0）、（8,1）、（12,5）、（6,3）、（8,5），H老师购买第 1 张,第 2 张,第 3 张,和第 5 张贺卡这 4 张贺卡，且优惠券用于购买第 5 张，那么花费总数为：(4+2)+(2+0)+(8+1)+(6/2+3)=23元。可以证明，这是最多的购买方法。

【输入输出样例2】

　Input

10 75
10 7
4 15
6 10
12 2
16 1
8 17
6 20
14 5
4 14
10 15

　Output

5

【输入输出样例2说明】

　　H老师的一种最优购买方案是：把优惠券用于购买第5张贺卡，所需费用16/2+1=9元，余下的钱用于购买（12,2）、（6,10）、（10,7）、（4,14）这四张贺卡，共需65元。购买5张贺卡共需74元，剩下1元不能购买任何贺卡。

【数据说明】

　　对于 \(20\%\) 的数据，\(1 ≤ n ≤ 10\)
　　对于 \(50\%\) 的数据，\(1 ≤ n ≤ 1000\)
　　对于 \(100\%\) 的数据，\(1 ≤ n ≤ 2×10^5\)，\(1 ≤ s ≤ 2×10^9\)，\(1 ≤ a_i,b_i ≤ 2×10^9\)。

【来源】

　　Mr.he