题意描述

一群小矮人掉进了一个很深的陷阱里，由于太矮爬不上来，于是他们决定搭一个人梯。

即：一个小矮人站在另一小矮人的肩膀上，直到最顶端的小矮人伸直胳膊可以碰到陷阱口。

对于每一个小矮人，我们知道他从脚到肩膀的高度$a_i$，并且他的胳膊长度为$b_i$。陷阱深度为$h$。

如果我们利用矮人$1$，矮人$2$，矮人$3$…矮人$k$搭一个梯子，满足$a_1+a_2+a_3+….+a_k+b_k \geq h$,那么矮人$k$就可以离开陷阱逃跑了。

一旦一个矮人逃跑了，他就不能再搭人梯了。

我们希望尽可能多的小矮人逃跑，那么问题来了，最多可以使多少个小矮人逃跑呐。

输入格式

第一行一个整数$n$，表示矮人的个数，接下来$n$行每一行两个整数$a_i$和$b_i$，最后一行是$h$。

输出格式

输出仅一行，包含一个整数表示答案。

Input & Output ‘s examples

Input ‘s eg 1

Output ‘s eg 1

Input ‘s eg 2

Output ‘s eg 2

数据范围和约定

对于$30\%$的数据，有$0 \leq n \leq 200$。

对于$100\%$的数据，有$0 \leq n \leq 2000$，$0 \leq a_i , b_i , h \leq 10^5$

分析

简单贪心 + 简单dp = 一道紫题
——我瞎编的

首先考虑每个小矮人对于答案的贡献，显然，让长的矮的先逃出去一定更优，让手短的先出去一定更优。

因此我们按照$a_i + b_i$进行排序，选出来长的矮手还短的，让他们先出去。

但现在问题来了，如果前面的人长得高但是手短，则对答案来说把他放在下面是更优的。

考虑$\text{dp}$。

设$f[i]$表示逃出去$i$个人后所能组成的人塔的最大高度。

显然，如果第$i$个人能逃出去，则$f[i] = max(f[i] , f[i - 1] - a[i])$。

套个背包模板就过去了，时间复杂度为$O(n^2)$，通过本题还是绰绰有余的。

剩下的见代码。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define ll long long
#define pb push_back
#define MP make_pair
#define ull unsigned long long
#define PII pair<int , int>
#define PIL pair<int , long long>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(a))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;
const int INF = 2147483647;
const long long INFL = 9223372036854775807;

struct Pre{
    int a , b;
}p[M];

bool cmp(Pre a , Pre b){
    return a.a + a.b < b.a + b.b;
}

int f[M];

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    int n , h; scanf("%d" , &n);
    rep(i , 1 , n){
        scanf("%d%d" , &p[i].a , &p[i].b);
        f[0] += p[i].a;
        f[i] = -0x3f3f3f3f;
    }
    scanf("%d" , &h);
    sort(p + 1 , p + 1 + n , cmp);
    rep(i , 1 , n){
        for(int j = i; j >= 1; j --){
            if(f[j - 1] + p[i].b >= h){
                f[j] = max(f[j] , f[j - 1] - p[i].a);
            }
        }
    }
    per(i , n , 0){
        if(f[i] >= 0){
            printf("%d\n" , i);
            return 0;
        }
    }

    return 0;
}