#include <bits/stdc++.h>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

const int nMax = 5001;
const int gMax = 1e5 + 1;
int W[nMax];
int P[gMax];
int d[gMax];
int main()
{

    int n, GMAX;

    f >> n >> GMAX;


    for (int i = 1; i <= n; ++i) {
        f >> W[i] >> P[i];
    }

    d[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= GMAX; ++j) {
            d[j] = d[j];
            if (W[i] <= j) {
                 d[j] = max(d[j], d[j - W[i] + P[i]]);
            }

            for (int z = 0; z <= GMAX; ++z) {
                d[z] = d[z];
            }
        }
    }

    g << d[GMAX];

    return 0;
}