学步园

Cow Exhibition

// File Name: poj2184.cpp
// Author: rudolf
// Created Time: 2013年04月21日 星期日 19时33分16秒

#include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>

using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=110;
int dp[200010];
int value[maxn];
int weight[maxn];
int nkind;

int main()
{
	int k=100000;
	while(cin>>nkind)
	{
		for(int i=0;i<nkind;i++)
		{
			cin>>value[i]>>weight[i];
		}
		for(int i=0;i<=200000;i++)
			dp[i]=-INF;
		dp[k]=0;
		for(int i=0;i<nkind;i++)
		{
			if(value[i]>0)
			{
				for(int j=200000;j>=value[i];j--)
					if(dp[j-value[i]]>-INF)
						dp[j]=max(dp[j],dp[j-value[i]]+weight[i]);
			}
			else
			{
				for(int j=0;j<=200000+value[i];j++)
				{
					if(dp[j-value[i]]>-INF)
						dp[j]=max(dp[j],dp[j-value[i]]+weight[i]);
				}
			}
		}
		int ans=0;
		for(int i=100000;i<=200000;i++)
			if(dp[i]>=0&&dp[i]+i-100000>ans)
				ans=dp[i]+i-100000;
		cout<<ans<<endl;	
	}
return 0;
}