该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

元旦临近，XH 打算给 $N$ 位朋友各送一份礼物，他准备了 $S$ 元作为礼物采购资金。采购清单显示，为第 $i$ 位朋友购买礼物需 $a_i$ 元，快递费为 $b_i$ 元。恰逢百货大楼元旦促销，XH 抽到一张奖券，可用于半价购买一件商品（若用于购买第 $i$ 件礼物，总开销为 $a_i/2 + b_i$ 元，且 $a_i$ 为偶数 ）。XH 想知道在资金限制下，最多能给多少位朋友送礼物。

输入格式

• 第一行：输入两个整数 $N$ 和 $S$ ，分别表示朋友数量和礼物基金总额。
• 第 $2$ 行至 $N + 1$ 行：每行输入两个整数 $a_i$ 和 $b_i$ ，表示为第 $i$ 位朋友购买礼物的费用和快递费。

数据范围：对于 $50\%$ 的数据，$1 \leq N \leq 100$ ；对于 $100\%$ 的数据，$1 \leq N \leq 1000$ ，$1 \leq S \leq 10^9$ ，$0 \leq a_i, b_i \leq 10^9$ 。

输出格式

输出一个整数，代表 XH 最多能送礼物的朋友数量。

示例

• 输入示例1

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

• 输出示例1

4

• 解释：购买1到4号礼物，奖券给3号使用，费用为 $(4 + 2)+(2 + 0)+(4 + 1)+(6 + 3)=22$ ，奖券也可用于1号或4号礼物。
• 输入示例2

10 280
18 30
20 37
18 47
10 35
22 36
16 32
10 38
12 32
18 36
12 36

• 输出示例2

6