Description

一群小矮人掉进了一个很深的陷阱里, 由于太矮爬不上来, 于是他们决定搭一个人梯. 即: 一个小矮人站在另一小矮人的肩膀上, 知道最顶端的小矮人伸直胳膊可以碰到陷阱口. 对于 每一个小矮人, 我们知道他从脚到肩膀的高度 \(A_i\), 并且他的胳膊长度为 \(B_i\). 陷阱 深度为 \(H\). 如果我们利用矮人 \(1\), 矮人 \(2\), 矮人 \(3\), ...... , 矮人 \(k\) 搭一个梯子, 满足 \(A_1 + A_2 + A_3 + \ldots + A_k + B_k \geq H\), 那么矮人 \(k\) 就可以离开陷阱逃跑了, 一旦一个矮人逃跑了, 他就不能再搭人梯了.

我们希望尽可能多的小矮人逃跑, 问最多可以使多少个小矮人逃跑.

Input

第一行一个整数 \(n\), 表示矮人的个数, 接下来 \(n\) 行每一行两个整数 \(A_i\) 和 \(B_i\), 最后一行是 \(H\).

Output

一个整数表示对多可以逃跑多少小矮人

Sample Input

2
20 10
5 5
30

Sample Output

2

Data Range

对于 30% 的数据,\(n \leq 200\)

对于 100% 的数据,\(n \leq 2000, A_i, B_i, H \leq 10^5\)

Explanation

我们发现垫在最底下的小矮人总是上不来, 所以基本上顺序没什么关系.

这样我们钦定个头最高的垫在底下, 好让更多的矮人上来 (高个儿表示不服)

然后发现不停地把人磊上去, 最后确定一个界限, 然后就可以成功求得答案.

似乎是一道比较显著的结论+贪心题~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

#define maximize(__x,__y) __x=max(__x,__y)
using namespace std;
typedef long long lli;
const int maxn = 2010;

struct dwarf {
    int body, arm; };
bool operator < (dwarf a, dwarf b) {
    return a.body + a.arm < b.body + b.arm; }

int n, H;
int dp[maxn];
dwarf arr[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &arr[i].body, &arr[i].arm);
        dp[0] += arr[i].body;
    }
    scanf("%d", &H);
    sort(arr + 1, arr + 1 + n);
    // Some magical dynamic programming...
    int res = 0;
    for (int i = 1; i <= n+1; i++)
        dp[i] = -1;
    for (int i = 1; i <= n; i++) {
        for (int j = res; j >= 0; j--) {
            if (dp[j] + arr[i].arm >= H)
                maximize(dp[j + 1], dp[j] - arr[i].body);
            if (dp[res + 1] >= 0)
                res += 1;
        }
    }
    // Output results
    printf("%d\n", res);
    return 0;
}