CF1203F2 Complete the Projects (hard version)

简单版和困难版的唯一区别在于，简单版要求你完成所有项目，而困难版则不要求。 Polycarp 是一位非常著名的自由职业者。他当前的评分为 $r$ 单位。 一些非常富有的客户请他为他们的公司完成一些项目。要完成第 $i$ 个项目，Polycarp 至少需要 $a_i$ 单位的评分；完成该项目后，他的评分会变化 $b_i$（评分会增加或减少 $b_i$，$b_i$ 可以为正或负）。Polycarp 的评分不能降到零以下，否则人们就不会信任评分如此低的自由职业者。 Polycarp 可以自行选择完成项目的顺序。此外，他甚至可以跳过某些项目。 为了获得更多的经验（当然还有金钱），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 能够选择的最大项目子集的大小（可以为空）。

由 ChatGPT 4.1 翻译