Cod sursa(job #617012)
#include <stdio.h>
#include <algorithm>
#define IN "rucsac.in"
#define OUT "rucsac.out"
using namespace std;
const int MaxN = 5005;
const int MaxG = 10005;
int Mat[2][MaxG];
int N, G, L;
int W[MaxN], P[MaxN];
int main()
{
freopen (IN , "r" , stdin);
freopen (OUT , "w" , stdout);
scanf ("%d %d", &N, &G);
for (int i = 0 ; i < N ; i++)
scanf ("%d %d", (W + i), (P + i));
for (int i = 0 ; i < N ; i ++, L = 1 - L)
for (int j = 0 ; j <= G ; j ++)
if (j - W[i] >= 0)
Mat[L][j] = max( Mat[1 - L][j], Mat[1 - L][j - W[i]] + P[i]);
printf("%d\n", Mat[1 - L][G]);
return 0;
}