B26 实践-1 心怀天下的骑士

题目描述

小喵作为喵星上最强大的骑士，他心怀天下，经常会帮助一些有需要的冒险家。

现在有 $n$ 位需要打造武器的冒险家，他们手上有 $a_i$ 颗魔晶，还缺 $b_i$ 颗魔晶才能打造武器。小喵带来了 $s$ 颗魔晶，可以将这些魔晶给冒险家打造武器。小喵还有一个特殊的技能——熔炼，能在武器打造完成后回收自己给出的魔晶和该冒险家手上原有的魔晶。

小喵想知道。他最多能帮助多少位冒险家打造武器？

输入格式

第一行两个整数 $n,s$ ，表示冒险家的数量和小喵手上的魔晶数量；

接下来的 $n$ 行，每行两个整数 $a_i,b_i$ ，依次表示该冒险家手上有的魔晶数量和需要的魔晶数量。

输出格式

一行一个整数，输出小喵最多能帮助多少名冒险家打造武器。

样例输入1

2 2
1 4
2 1

样例输出1

2

样例输入2

2 2
1 4
1 1

样例输出2

1

样例解释

样例 $1$：有 $2$​ 名冒险家需要帮助，小喵一开始手里有 $2$​ 块魔晶。第 $1$​ 位冒险家手上有 $1$​ 块魔晶，还需要 $4$​ 块魔晶，第 $2$ 位冒险家手上有 $2$ 块魔晶，还需要 $1$ 块魔晶。小喵可以先帮第 $2$ 位冒险家打造武器，即给第 $2$ 位冒险家 $1$ 块魔晶，这样打造武器后，小喵可以通过熔炼技能获得 $3$ 块魔晶，此时他手上有 $4$ 块魔晶，可以帮助第 $1$ 位冒险家。所以共可以帮助 $2$ 位冒险家。

样例 $2$ ：小喵只能先帮助第 $2$ 位冒险家，通过熔炼手上魔晶变为 $3$ 颗，不能满足第 $1$ 位冒险家的需要，所以最多只能帮助 $1$ 位冒险家。

数据范围

对于 $100\%$ 的数据：$1\le n \le 1000,1\le s \le 10^4,1\le a_i\le 10^5,1\le b_i \le 10^9$ 。