← 返回题目列表

Codeforces · 1203/F2

F2. 完成项目(困难版)

中文机器翻译题面 查看原题

简单版和困难版之间的唯一区别是您应该在简单版中完成所有项目,但在困难版中则不需要。

Polycarp 是一位非常著名的自由职业者。他目前的评级为 $$$r$$$ 单位。

一些非常富有的客户要求他为他们的公司完成一些项目。要完成第 $$$i$$$ 个项目,Polycarp 需要至少有 $$$a_i$$$ 单位的评级;当他完成这个项目后,他的评级将改变$$$b_i$$$(他的评级将增加或减少$$$b_i$$$)($$$b_i$$$可以是正数或负数)。波利卡普的评级不应低于零,因为这样人们就不会信任评级如此低的自由职业者。

Polycarp 可以选择他完成项目的顺序。此外,他甚至可以完全跳过一些项目。

为了获得更多经验(当然还有金钱)Polycarp 希望选择具有最大可能规模的项目子集以及完成这些项目的顺序,因此他在开始每个项目之前有足够的评级,并且在完成每个项目后有非负评级。

您的任务是计算此类项目子集的最大可能规模。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$r$$$ ($$$1 \le n \le 100, 1 \le r \le 30000$$$) — 分别是项目数量和 Polycarp 的初始评级。

接下来的 $$$n$$$ 行包含项目,每行一个。第 $$$i$$$ 个项目表示为一对整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i \le 30000$$$, $$$-300 \le b_i \le 300$$$) — 完成第 $$$i$$$ 个项目所需的评级以及项目完成后的评级变化。

输出

打印一个整数 — Polycarp 可以选择的项目的最大可能子集(可能为空)的大小。

示例

输入 #1

3 4
4 6
10 -2
8 -1

输出 #1

3

输入 #2

5 20
45 -6
34 -15
10 34
1 27
40 -45

输出 #2

5

输入 #3

3 2
300 -300
1 299
1 123

输出 #3

3