#include <fstream>
using namespace std;

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

struct obiect{
    int pret;
    int greutate;
};

int d[5000][10000];

int main() {
    int n, G;
    obiect a[5002];
    f >> n >> G;
    for (int i = 1; i <= n; ++i) {
        f >> a[i].greutate >> a[i].pret;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = a[i].greutate; j <= G; ++j)
            d[i][j] = max(d[i - 1][j - a[i].greutate] + a[i].pret, d[i - 1][j]);
    }
    g << d[n][G];
    return 0;
}