题目链接：

http://poj.org/problem?id=2184
https://www.oj.swust.edu.cn/problem/show/2793

题意：每个物品有两种属性（有负的），要求选一些物品，使得所选的物品两种属性加起来的和最大，并且每种属性的和不能是负的

哎，我反正是想不到是01背包。。。

最多100个物品，每个物品 价值 和 重量 都是 $[-1000,1000]$[−1000,1000]，所以重量最多是 $[-100\ast 1000,100\ast 1000]$[−100∗1000,100∗1000]但是背包不能是负的，就加都加100000变成 $[0,200000]$[0,200000]，所以背包最大空间 $W$W就是200000

但是，一下几点我不是很理解：
①为什么dp初值要赋值为 $-\infty$−∞
②为什么重量是负的时候，用的完全背包？而且并不是像模板一样从 $c$c到 $W$W

后来有点理解：
①：因为我们的 $dp\left[i\right]$dp[i]可能是负的，你看最后都还要找 $dp\left[i\right]\>0$dp[i]>0的，所以初值就不能比 $0$0大，那取好小合适喃？最坏情况就是 $100$100个都是 $-1000$−1000，那至少要取 $-1000000$−1000000才合适，所以懒得了，直接 $-\infty$−∞
②：这个就要从01背包为啥是倒起来说了，阔以看哈这个。
比如我们来了一个重量 $c=3$c=3，价值为 $v$v，假如计算 $dp\left[10\right]$dp[10],
那么 $dp\left[10\right]=max\left(dp\right[10],dp[10-3]+v)$dp[10]=max(dp[10],dp[10−3]+v)
即： $dp\left[10\right]=max\left(dp\right[10],dp[7]+v)$dp[10]=max(dp[10],dp[7]+v)
因为是倒起来，计算 $dp\left[10\right]$dp[10]的时候， $dp\left[7\right]$dp[7]还没有更新过，所以还是上一次状态，所以倒起来是对的，这是我们正常的背包嘛~

But：

假如来了一个重量 $c=-3$c=−3的东西
那么 $dp\left[10\right]=max\left(dp\right[10],dp[10-(-3)]+v)$dp[10]=max(dp[10],dp[10−(−3)]+v)
即： $dp\left[10\right]=max\left(dp\right[10],dp[13]+v)$dp[10]=max(dp[10],dp[13]+v)
如果倒起来，这样计算 $dp\left[10\right]$dp[10]的时候， $dp\left[13\right]$dp[13]却已经更新过了，所以不是上一次的状态，这样不对
但是这个时候正起来就对了
所以正起来看起来像完全背包，但是其实并不是，其实他还是01背包，网上有人说小于0就是完全背包，我就说咋就变成完全背包了嘛，死活理解不到。。。

#include"iostream"
#include"cstring"
using namespace std;
const int maxn=2e5+5;
int dp[maxn];
int inf=1e9;
int sh=100000;
int W=2e5;
int N;
void bag01(int v,int c)
{
    if(c>0)for(int i=W;i>=c;i--)dp[i]=max(dp[i],dp[i-c]+v);
    else for(int i=0;i<W+c;i++)dp[i]=max(dp[i],dp[i-c]+v);
}
int main()
{
    while(cin>>N)
    {
        for(int i=0;i<=W;i++)dp[i]=-inf;
        dp[sh]=0;
        for(int i=1;i<=N;i++)
        {
            int v,c;
            cin>>c>>v;
            bag01(v,c);
        }
        int ans=0;
        for(int i=sh;i<=W;i++)//相当于只要正的那一坨
        {
            if(dp[i]>0)ans=max(ans,i+dp[i]-sh);//取v+c最大的
        }
        cout<<ans<<endl;
    }
}