Description

JOI 君有 \(n\) 个装在手机上的挂饰, 编号为 \(1, 2, \ldots, n\). JOI 君可以将其中的一些装在手机上.

JOI 君的挂饰有一些与众不同----其中的一些挂饰附有可以挂其他挂件的挂钩. 每个挂件要么 直接挂在手机上, 要么挂在其他挂件的挂钩上. 直接挂在手机上的挂件最多有 \(1\) 个.

此外, 每个挂件有一个安装时会获得的喜悦值, 用一个整数来表示. 如果 JOI 君很讨厌某个 挂饰, 那么这个挂饰的喜悦值就是一个负数.

JOI 君想要最大化所有挂饰的喜悦值之和. 注意不必要将所有的挂钩都挂上挂饰, 而且一个 都不挂也是可以的.

Input

第一行一个整数 \(n\), 代表挂饰的个数.

接下来 \(n\) 行, 第 \(i\) 行 \((1 \leq i \leq n)\) 有两个空格分隔的整数 \(A_i\) 和 \(B_i\), 表示挂饰 \(i\) 有 \(A_i\) 个挂钩, 安装后会获得 \(B_i\) 的喜悦值.

Output

输出一行一个整数, 表示手机上连接的挂饰总和的最大值.

Sample Input

5
0 4
2 -2
1 -1
0 1
0 3

Sample Output

5

Data Range

对于所有数据, 满足:\(1 \leq n \leq 2000, 0 \leq A_i \leq n, |B_i| \leq 10^6\)

Explanation

首先发现这样一个性质, 就是说只要确定好了选哪些挂饰 (并且需要的挂钩数不多于提供的 挂钩数), 总有一种办法使得我们可以把挂饰挂好, 因为这是一个树形结构, 然后简单构造 一下就可以了. 并且题目并没有让我们构造==

所以问题就变为确定一堆挂饰, 使得它们的需要的净挂钩数不多于 \(1\) 就可以了, 好了, 这就是一道十分水的背包问题了......

记得初始化要默认全是 \(-\infty\). ...... 不然就会像我一样死调好久 QAQ

Source Code


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

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

template <typename _T>
class ext_array {
private:
    _T arr[maxn<<1];
    int n;
public:
    _T& operator [] (int _p) {
        return arr[min(max(_p,-n),n)+maxn];
    } void init(int _n, lli val) {
        n = _n; for (int i = 0; i < maxn<<1; i++)
            arr[i] = val;
        return ;
    }
};

int n;
lli a[maxn], b[maxn];
ext_array<lli> dp;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    dp.init(n, -infinit);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &a[i], &b[i]);
    // Another EZ knapsack problem
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        lli x = 1 - a[i];
        if (x > 0) // This costs more than it provides
            for (int j = n; j >= -n; j--)
                maximize(dp[j + x], dp[j] + b[i]);
        else // This generates more hooks
            for (int j = -n; j <= n; j++)
                maximize(dp[j + x], dp[j] + b[i]);
    }
    // Must use no more than 0 hooks
    lli res = 0;
    for (int i = -n; i <= 1; i++)
        maximize(res, dp[i]);
    printf("%lld\n", res);
    return 0;
}