题目描述

农夫约翰想给 N 头奶牛送礼物，总预算为 B 个货币单位。
每头奶牛 i 的礼物价格为 P(i)，运费为 S(i)，因此正常总价为 P(i)+S(i)。
FJ 有一张 一次性优惠券，可将 任意一头 奶牛的价格 减半（向下取整，P(i) 保证为偶数）。
使用优惠券后，该奶牛的花费变为 P(i)/2 + S(i)。

请你帮 FJ 计算，在预算 B 内，最多能让多少头奶牛收到礼物。

输入格式

• 第 1 行：两个空格分隔的整数 N 和 B（1 ≤ N ≤ 1000，1 ≤ B ≤ 1 000 000 000）。
• 第 2~N+1 行：每行两个空格分隔的整数 P(i) 和 S(i)（0 ≤ P(i), S(i) ≤ 1 000 000 000，P(i) 为偶数）。

输出格式

• 第 1 行：一个整数，表示最多能送礼的奶牛数量。

样例

样例输入

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

样例输出

4

样例解释

• 选择奶牛 1、2、3、4，并在奶牛 3 使用优惠券：
  花费 = (4+2) + (2+0) + (8/2+1) + (6+3) = 6+2+5+9 = 22 ≤ 24。
• 共 4 头奶牛收到礼物，输出 4。

数据范围与提示

• 1 ≤ N ≤ 1000
• 1 ≤ B ≤ 1 000 000 000
• P(i) 为偶数，保证 P(i)/2 向下取整无误差