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

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

#define MAXN 5010
#define MAXG 10010

int d[MAXN][MAXG];
int w[MAXN], p[MAXN];

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

    return 0;
}