Description

奶牛想证明他们是聪明而风趣的。为此，贝西筹备了一个奶牛博览会，她已经对N头奶牛进行了面试，确定了每头奶牛的智商和情商。 贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果，所以贝西不希望出展奶牛的智商之和小于零，或情商之和小于零。满足这两个条件下，她希望出展奶牛的智商与情商之和越大越好，请帮助贝西求出这个最大值.

Input

第一行：一个整数N，表示奶牛的数量， 1 ≤ N ≤ 100 第二行到第N + 1行：第i + 1行有两个用空格分开的整数：Si和Fi，分别表示第i头奶牛的智商和情商， -1000 ≤ Si ≤ 1000， -1000 ≤ Fi ≤ 1000

Output

第一行：单个整数，表示情商与智商和的最大值。贝西可以不让任何奶牛参加展览，如 果这样应该输出0

Sample Input

5
-5 7
8 -6
6 -3
2 1
-8 -5

Sample Output

8

Hint

选择 1， 3， 4 号奶牛，此时智商和为-5 + 6 + 2 = 3，情商和为7 - 3 + 1 = 5。加 入 2 号奶牛可使总和提升到10，不过由于情商和变成负的了，所以是不允许的.

题解

每只牛有两种选择：参加会展和不参加会展。我们要求在智商一定的情况下情商的最大值，这其实就是01背包的模板。状态转移方程的推导如下：
第 $i$ 只奶牛不参加会展： $dp[i][j]=dp[i-1][j]$
第 $i$ 只奶牛参加会展： $dp[i][j]=dp[i-1][j-a[i].iq]+a[i].eq$
加上决策，选取上面两种情况的最大值： $dp[i][j]=\max(dp[i-1][j], dp[i-1][j-a[i].iq]+a[i].eq)$

有一些奶牛智商居然是负的，这样导致 $j-a[i].iq$ 比 $j$ 大，可以在动规的时候判断一下，如果这只奶牛很傻，那么正着dp，否则反着dp。

因为 $a[i].iq$ 和 $a[i].eq$ 都有可能是负数，所以会导致数组越界。这时，我们可以把 $dp$ 数组向右移动 $400000$ 位。数组的改变意味着我们状态的定义也会发生改变：
$dp[j]$ 表示在奶牛智商之和为 $j-400000$ 时，情商的最大值。

但是在最后求答案时，不要忘记我们求得其实是 $dp[j]+j-400000$的最大值。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
typedef pair<int,int> PII;
typedef long long LL;
const int INF=0x3f3f3f3f;

int f[1000*400*2+10];
int a[410];
int b[410];
int n;

int main()
{
    cin>>n;
    int base=1000*n;
    int upper=base*2;

    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];

    memset(f,-0x3f,sizeof f);
    f[base]=0;

    for(int i=1;i<=n;i++)
        if(a[i] >= 0)
        {
            for(int j=upper;j>=a[i];j--)
                f[j]=max(f[j],f[j-a[i]]+b[i]);
        }
        else
        {
            for(int j=0;j-a[i]<=upper;j++)
                f[j]=max(f[j],f[j-a[i]]+b[i]);
        }

    int res=-upper;
    for(int i=base;i<=upper;i++)
        if(f[i]>0)
            res=max(res,f[i]+i-base);

    if(res < 0) res=0;
    cout<<res<<endl;
   // system("pause");
}