CF1203F2.Complete the Projects (hard version)

The only difference between easy and hard versions is that you should complete all the projects in easy version but this is not necessary in hard version.

Polycarp is a very famous freelancer. His current rating is $r$ units.

Some very rich customers asked him to complete some projects for their companies. To complete the $i$-th project, Polycarp needs to have at least $a_i$ units of rating; after he completes this project, his rating will change by $b_i$ (his rating will increase or decrease by $b_i$) ($b_i$ can be positive or negative). Polycarp's rating should not fall below zero because then people won't trust such a low rated freelancer.

Polycarp can choose the order in which he completes projects. Furthermore, he can even skip some projects altogether.

To gain more experience (and money, of course) Polycarp wants to choose the subset of projects having maximum possible size and the order in which he will complete them, so he has enough rating before starting each project, and has non-negative rating after completing each project.

Your task is to calculate the maximum possible size of such subset of projects.

简单版本与困难版本的唯一区别在于：在简单版本中，你需要完成所有项目；而在困难版本中，这并非必需。

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

一些非常富有的客户邀请他为他们的公司完成若干项目。要完成第 $i$ 个项目，Polycarp 必须至少拥有 $a_i$ 单位的评分；完成该项目后，他的评分将变化 $b_i$（即评分增加或减少 $b_i$ 单位）（$b_i$ 可为正数或负数）。Polycarp 的评分不得低于零，否则人们将不再信任如此低评分的自由职业者。

Polycarp 可以自行选择完成项目的顺序；此外，他甚至可以完全跳过某些项目。

为了获得更多经验（当然还有金钱），Polycarp 希望选出一个尽可能大的项目子集，并确定其完成顺序，使得他在开始每个项目前都拥有足够的评分，且在完成每个项目后评分仍为非负数。

你的任务是计算满足上述条件的项目子集的最大可能大小。

The first line of the input contains two integers $n$ and $r$ ($1 \le n \le 100, 1 \le r \le 30000$) — the number of projects and the initial rating of Polycarp, respectively.

The next $n$ lines contain projects, one per line. The $i$-th project is represented as a pair of integers $a_i$ and $b_i$ ($1 \le a_i \le 30000$, $-300 \le b_i \le 300$) — the rating required to complete the $i$-th project and the rating change after the project completion.

输入的第一行包含两个整数 $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$）表示，其中 $a_i$ 是完成第 $i$ 个项目所需的最低评分，$b_i$ 是完成该项目后评分的变化量。

Print one integer — the size of the maximum possible subset (possibly, empty) of projects Polycarp can choose.

输出一个整数——Polycarp 可选择的项目最大可能子集的大小（该子集可以为空）。