礼物

题目描述

小明想给他的 $N$ 个朋友送礼物，购买礼物的预算是 $B(1 \le B \le 10^9)$ 元钱。

第 $i$ 个朋友想要一件 $p_i$ 元的礼物，把礼物送到第 $i$ 个朋友的快递费是 $s_i$ 元。 因此小明把这件礼物送到第 $i$ 个朋友手上总共需要花费 $p_i+s_i$ 元。

小明有一张优惠券，他可以在购买一件礼物时仅花费原价的一半。 如果小明在购买第 $i$ 个朋友的礼物时使用了优惠券，那么他一共只用花费 $\dfrac{p_i}{2}+s_i$。

为了方便计算，$p_i$ 都是偶数。优惠券使用过后不能再使用。

帮助小明求出他最多可以给多少个朋友购买礼物。

输入格式

第一行两个整数 $N,B$，代表朋友数量和总预算。

接下来 $N$ 行，每行两个整数 $p_i,s_i$，分别代表礼物价格和快递费。

输出格式

输出一个整数，表示最多可以给多少位朋友买礼物。

输入输出样例 #1

输入 #1

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

输出 #1

4

说明/提示

有 $5$ 头牛，预算是 $24$ 元。第 $1$ 个朋友想要的礼物价格为 $4$ 元，快递费为 $2$ 元，其他朋友想要的礼物依此类推。小明可以在购买第 $3$ 个朋友想要的礼物时使用优惠券，总花费为：

$(4+2)+(2+0)+(4+1)+(6+3)=22$

注意到，他也可以把优惠券用在购买第 $1$ 头或第 $4$ 个朋友想要的礼物，这样也能购买 $4$ 件礼物，并且不超过预算。

对于 $40\%$ 的数据，$1\le N \le 20$

对于 $100\%$ 的数据，$1\le N \le 1000$