Problem Description
Several dwarfs are trapped in a deep well. They are not tall enough to climb out of the well, so they want to make a human-pyramid, that is, one dwarf stands on another's shoulder, until the dwarf on the top can reach the top of the well when he raise his arms up. More precisely speaking, we know the i-th dwarf's height from feet to shoulder is Ai, and his arm length Bi. And we know the height of the well is H. If we can build a dwarf-tower consists of dwarf 1, dwarf 2, ..., dwarf k from bottom to top, such that A1 + A2 + ... + Ak-1 + Ak + Bk >= H, then dwarf k can escape from the well. Obviously, the escaped dwarf can't be used to build tower again.

We want the escaped dwarfs as many as possible. Please write a program to help the dwarfs.
 

Input
The first line of each test case contains N, (1 <= N <= 2000) the number of trapped dwarfs. Each of the following N lines contains two integers Ai and Bi. The last line is H, the height of the well. All the integers are less than 100,000.
 

Output
Output one line for each test case, indicating the number of dwarfs escaped at most.
 

Sample Input
2 20 10 5 5 30 2 20 10 5 5 35
 

Sample Output
2 1
Hint
For the first case, the tall dwarf can help the other dwarf escape at first. For the second case, only the tall dwarf can escape.
 

Author
TJU
 

Source
2012 Multi-University Training Contest 2
 

这种不知道是啥的dp最讨厌了

说题意：要跳过h高的墙，彼此身子身子叠一起，最上面的人手够到墙就可以。问最多多少人跳过

dp[i][j]代表的是在前i个人中能逃脱出j个人后，剩余井中矮人再想逃脱出至少一人还需要的最小高度是多少，分析如下，逃脱出的j个人中最后逃脱的一定是
         ai +bi最大的，这样才能得到dp值是最优的，需要首先对矮人按照ai + bi从大到小排序，考虑当前第i个人可以逃脱可以不逃脱，即dp[i][j]只可能由两种情况
         得来：

         dp[i-1][j]：i位置的人没逃脱出去，所以所需的高度就是dp[i-1][j] - a[i]。

         dp[i-1][j-1]：i位置的人逃脱出去了，所需高度有两种情况：

         1 i的身高和臂长之和足够大，利用之前所需高度就可以逃脱，这时所需高度是dp[i-1][j-1]；

         2 i的身高和臂长之和不够大，此时i最先逃脱，所以需要的高度就是前i-1个人帮助i逃脱，所需高度是H -sumA[i] - b[i]。

         以上两种情况必须都满足才能得到dp[i][j]，所以需要取最大值，
         综上得dp方程：dp[i][j] = MIN(dp[i-1][j] - dwarf[i].a , MAX(dp[i-1][j-1] , h - sum[i] -dwarf[i].b));

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
    int a,b;
}num[2002];
int sum[2002];
int dp[2002][2002];
int min(int a,int b){if(a<b)return a;return b;}
int max(int a,int b){if(a>b)return a;return b;}
bool cmp(node x,node y){return (x.a+x.b)>(y.a+y.b);}
int main()
{
    //freopen("cin.txt","r",stdin);
    int n,h;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)scanf("%d%d",&num[i].a,&num[i].b);
        scanf("%d",&h);
        sort(num+1,1+num+n,cmp);
        sum[0]=0;
        sum[1]=num[1].a;
        for(int i=2;i<=n;i++) sum[i]=sum[i-1]+num[i].a;
       // for(int i=1;i<=n;i++) printf("sum=%d,",sum[i]);
        memset(dp,0,sizeof(dp));
        for(int i=0;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                dp[i][j]=0x3f3f3f3f;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                dp[i][j]=min(dp[i-1][j]-num[i].a,max(dp[i-1][j-1], h-sum[i]-num[i].b));
            }
        }
        int ans;
        for(int i=n;i>=0;i--)
        if(dp[n][i]<=0){ans=i;break;}
        printf("%d\n",ans);
    }
    return 0;
}