#include <bits/stdc++.h>
using namespace std;
const int MAX = 10000;
int dp[MAX + 1];
int readInt(FILE *fin) {
    int x;
    char ch;
    ch = fgetc(fin);
    while (isspace(ch)) {
        ch = fgetc(fin);
    }
    x = 0;
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = fgetc(fin);
    }
    return x;
}
int minim(int a, int b) {
    return a < b ? a : b;
}
int main()
{
    FILE *fin, *fout;
    int n, i, g, x, j, p, rez, s;
    fin = fopen("rucsac.in", "r");
    fscanf(fin, "%d%d", &n, &g);
    s = 0;
    for (i = 0; i < n; i++) {
        x = readInt(fin);
        p = readInt(fin);
        for (j = minim(s, g - x); j >= 0; j--) {
            if (dp[j] + p > dp[j + x]) {
                dp[j + x] = dp[j] + p;
            }
        }
        s += x;
    }
    fclose(fin);
    rez = 0;
    for (i = 0; i <= g; i++) {
        if (dp[i] > rez) {
            rez = dp[i];
        }
    }
    fout = fopen("rucsac.out", "w");
    fprintf(fout, "%d\n", rez);
    fclose(fout);
    return 0;
}