//多分 w + s が小さい方から並べるのが強いんだよね。きっと。(隣り合う2つを入れ替えても的な議論をする) #include #include #include #include #define int long long #define rep(i, n) for(i = 0; i < n; i++) using namespace std; typedef tuple T; void chmin(int &a, int b) { a = min(a, b); } int INF = 1e+10; int n; T tup[1000]; int w[1000], s[1000]; int dp[1001][1001]; //dp[i][j] = i人のうちj人を選んだときの合計重さの最小値 signed main() { int i, j; cin >> n; rep(i, n) { int _w, _s; cin >> _w >> _s; tup[i] = T(_w + _s, _w, _s); } sort(tup, tup + n); rep(i, n) { w[i] = get<1>(tup[i]); s[i] = get<2>(tup[i]); } rep(i, n + 1) rep(j, n + 1) dp[i][j] = INF; dp[0][0] = 0; rep(i, n) { for (j = 0; j <= i; j++) { if (dp[i][j] <= s[i]) { chmin(dp[i + 1][j + 1], dp[i][j] + w[i]); } chmin(dp[i + 1][j], dp[i][j]); } } for (i = n; i >= 0; i--) { if (dp[n][i] < INF) break; } cout << i << endl; return 0; }