# Poj Solution 2184

```http://poj.org/problem?id=2184

#include <stdio.h>
#include <memory.h>
#include <algorithm>
#include <functional>
using namespace std;

bool mem[200100],*sign = mem+100000;
int mem2[200100],*ans = mem2+100000;

typedef pair<int,int> node;
node c[100];
int n;

node mem3[2][100000],*s = mem3[0], *t = mem3[1];
int sn,tn;

int main()
{
int i, j, n, k, h, m, v;

scanf( "%d", &n );

for( i=0; i<n; i++ )
scanf( "%d %d", &c[i].first, &c[i].second );

memset( sign-1000*n-5, 0, sizeof(bool) * ( 1000*2*n+10 ) );

sign[0] = true;
ans[0] = 0;
sn = 0;

s[sn].first = 0;
s[sn].second = 0;
sn++;

for( i=0; i<n; i++ )
{
for( m=sn, j=0 ; j < m ; j++ )
{
h = s[j].second + c[i].second;
k = s[j].first + c[i].first;

if( ! sign[k] )
{
sign[k] = true;
ans[k] = h;

s[sn].first = k;
s[sn].second = h;
sn++;
}
else if( h > ans[k] )
{
ans[k] = h;

s[sn].first = k;
s[sn].second = h;
sn++;
}

}

std::merge( s, s+m, s+m, s+sn, t, greater<node>() );
swap( t, s );

m = sn;
v = s[0].second;
tn = 0;
t[tn++] = s[0];

for( j = 1; j<m; j++ )
{
if( s[j].second > v )
{
t[tn++] =  s[j];
v = s[j].second;
}
}

swap( t, s);
swap( tn, sn);

if( tn >= 100000 || sn >=100000 )
while(1) printf( "faintn" );

}

for( i=0; i<=1000*n; i++ )
if( sign[i] && ans[i] >=0 && i + ans[i] > answer )