Rucsac

#include <bits/stdc++.h>

using namespace std;

int N, G, g, p, a[10005];

ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

int main() {
    fin >> N >> G;
    for(int i = 1; i <= N; ++i) {
        fin >> g >> p;
        for(int j = G; j >= g; --j)
        a[j] = max(a[j], a[j - g] + p);
    }
    fout << a[G];
}