题目描述

Farmer John 想给他的 $N$ （ $1 \le N \le 1000$ ）头奶牛送礼物，购买礼物的预算是 $B$ （ $1 \le B \le 10^9$ ）元钱。

第 $i$ 头奶牛想要一件 $P_i$ 元的礼物，把礼物送到第 $i$ 头奶牛的快递费是 $S_i$ 元，因此 Farmer John 把这件礼物送到第 $i$ 头奶牛手上总共需要花费 $P_i + S_i$ 元。 Farmer John 有一张优惠券，他可以在购买一件礼物时仅花费原价的一半。如果 Farmer John 在购买第 $i$ 头奶牛的礼物时使用了优惠券，那么他一共只用花费 $\frac{P_i}{2} + S_i$ 。为了方便计算， $P_i$ 都是偶数。优惠券使用过后不能再使用。

帮助 Farmer John 求出他最多可以给多少头奶牛购买礼物。

输入格式（文件名：gifts.in）

第 $1$ 行：两个整数 $N$ 、 $B$ 。

第 $2 \dots N + 1$ 行：第 $i + 1$ 行包含两个整数 $P_i$ 、 $S_i$ （ $0 \le P_i, S_i \le 10^9$ ）， $P_i$ 是偶数。

输出格式（文件名：gifts.out）

第 $1$ 行： Farmer John 最多能购买的礼物数量。

输入样例

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

输出样例

4

样例解释

有 $5$ 头牛，预算是 $24$ 元。第 $1$ 头奶牛想要的礼物价格为 $4$ 元，快递费为 $2$ 元，其他奶牛想要的礼物依此类推。

Farmer John 可以在购买第 $3$ 头奶牛想要的礼物时使用优惠券。总花费为 $(4 + 2) + (2 + 0) + (4 + 1) + (6 + 3) = 22$ 。注意到，他也可以把优惠券用在购买第 $1$ 头或第 $4$ 头奶牛想要的礼物，这样也能购买 $4$ 件礼物，并且不超过预算。