题目链接：传送门
思路：
对于对rating有提升的项目，肯定做越多越好，所以把$b_{i} >= 0$的项目按rating要求从小到大贪心地都做掉，得到最高的rating记为r。
对于剩余的$b_{i} < 0$的项目，因为r的范围很小，在6e4的亚子，可以考虑用01背包来做。
但是直接上01背包会WA，是因为不同项目选择的先后顺序会对结果有影响。
比如现在的r是5，有两个项目，（ai，bi）分别为（3，-3）和（3，-1），如果先做前面的项目，就会导致rating不够做后一个项目。
考虑任意两个项目i（ai，bi），j（aj，bj），先做i后做j的话，就要求初始的rating >= aj+|bi|，反之要求rating >= ai+b|j|。
显然要求的初始rating越低越好：若aj+|bi| < ai+b|j|，说明前者要求更低，此时应先做i。移项一下就可以得ai-|bi| > aj-|bj|。
所以ai-|bi|（bi<0）越大的项目，就可以越优先地做。根据这个sort一下，跑一遍01背包就出答案了。
代码：O(r*n)
#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 105
#define R 30005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define mp(a,b) make_pair(a, b)
#define endl '\n'
#define lowbit(x) (x&-x) using namespace std;
typedef long long ll;
typedef double db; /** fast read **/
template <typename T>
inline void read(T &x) {
x = ; T fg = ; char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') fg = -;
ch = getchar();
}
while (isdigit(ch)) x = x*+ch-'', ch = getchar();
x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); } struct Node{
int a, b;
bool operator < (const Node& x) const {
return a < x.a;
}
};
int f[R<<];
vector <Node> vpos, vneg;
bool cmp(Node x, Node y) {
return x.a-x.b < y.a-y.b;
}
int main()
{
int n, r;
read(n, r);
for (int i = ; i <= n; i++) {
int a, b; read(a, b);
if (b >= )
vpos.push_back(Node{a, b});
else
vneg.push_back(Node{a, -b});
}
sort(vpos.begin(), vpos.end());
sort(vneg.begin(), vneg.end(), cmp);
int ans = ;
for (int i = ; i < sz(vpos); i++) {
Node tmp = vpos[i];
if (r >= tmp.a) {
r += tmp.b;
ans++;
}
}
for (int i = sz(vneg)-; i >= ; i--) {
Node tmp = vneg[i];
for (int j = max(tmp.a, tmp.b); j <= r; j++) {
f[j-tmp.b] = max(f[j-tmp.b], f[j]+);
}
}
int res = ;
for (int i = ; i <= r; i++)
res = max(res, f[i]);
ans += res;
cout << ans << endl; return ;
}
/*
8 15000
11031 -299
8368 -289
12459 -297
6511 -297
2628 -299
3478 -296
1050 -293
12981 -294
*/