#include <bits/stdc++.h>
#include <stdlib.h>

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

struct obiect {
    int w, p;
}obiecte[5005];

int d[5005][10005];

int main() {
    int n, g;
    fin >> n >> g;
    for (int i = 1; i <= n; i ++)
        fin >> obiecte[i].w >> obiecte[i].p;
    for (int i = 1; i <= n; i ++) {
        if (i == 1)
            d[i][obiecte[i].w] = obiecte[i].p;
        else {
            for (int cw = 1; cw <= g; cw ++) {
                if (obiecte[i].w <= cw) {
                    d[i][cw] = max(d[i - 1][cw], d[i - 1][cw - obiecte[i].w] + obiecte[i].p);
                }
            }
        }
    }
    fout << d[n][g];

    return 0;
}