UVa Q10154 (!finish)

//UVa Q10154
#include <bits/stdc++.h>
using namespace std;

struct turtle{
    int W, carry;
}arr[5607];

int dp[5607];
int weight[5607];
bool cmp(turtle a, turtle b){
    return a.carry < b.carry;
}

int32_t main(){
    int n = 0;
    while(cin >> arr[n].W >> arr[n].carry)++n;
    sort(arr, arr+n, cmp);
    for(int i = 0; i < n; ++i)arr[i].carry -= arr[i].W;
    for(int i = 0; i < n; ++i){
        dp[i] = 1;
        weight[i] = arr[i].W;
        for(int j = 0; j < i; ++j){
            if(arr[i].carry >= weight[j] && dp[i] < dp[j]+1){
                dp[i] = dp[j]+1;
                weight[i] = weight[j] + arr[i].W;
            }
        }
    }
    int big = 0;
    for(int i = 1; i < n; ++i){
        if(dp[big] < dp[i])big = i;
    }
    cout << dp[big] << '\n';
    return 0;
}