#include <bits/stdc++.h>

FILE *fin = fopen("rucsac.in", "r");
FILE *fout = fopen("rucsac.out", "w");

int N, G, dp[2][10005], g[5005], v[5005];

inline void Read() {
    fscanf(fin, "%d %d", &N, &G);
    for(i = 1; i <= N; i++) {
        fscanf(fin, "%d %d", &g[i], &v[i]);
    }
    fclose(fin);
}

inline void Solve() {
    int i, j, ans, L;
    L = 1;
    for(i = 1; i <= N; i++) {
        L = 1 - L;
        for(j = 0; j <= G; j++) {
            dp[L][j] = dp[1 - L][j];
            if(j >= g[i]) {
                dp[L][j] = min(dp[1 - L][j - g[i] + v[i]], dp[L][j]);
            }
        }
    }
    ans = dp[L][0];
    for(i = 1; i <= G; i++)
        ans = max(ans, dp[L][i]);
    fprintf(fout, "%d\n", ans);
    fclose(fout);
}

int main()
{
    printf("Hello world!\n");
    return 0;
}