// http://www.infoarena.ro/problema/rucsac
// 100 p

#include <fstream>
#include <iomanip>
#include <iostream>

using namespace std;

struct obiect {
    int g, p; // greutatea, profitul
};

obiect a[5001];
int n, G, o, g, p, c, pn, lp, lc, mp[2][10001];
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");

/* Ideea de rezolvare:
   Pentru un rucsac de capacitate c, asociem obiectul curent (o), avand greutatea a[lc].g,
   cu varianta optima obtinuta prin plasarea a o-1 obiecte intr-un rucsac cu capacitate c-a[lc].g. */

int main() {
    fi >> n >> G; // numarul de obiecte, capacitatea totala a rucsacului
    for (o = 1; o <= n; o++)
        fi >> a[o].g >> a[o].p;
    lp = 0;
    lc = 1;
    for (o = 1; o <= n; o++) {                    // pentru fiecare obiect
        for (c = 1; c <= G; c++) {                // pentru fiecare capacitate a rucsacului
            if (a[o].g <= c) {                    // Obiectul curent incape in rucsac?
                pn = a[o].p + mp[lp][c - a[o].g]; // profitul nou
                if (pn > mp[lp][c])               // Avem profit mai bun folosind obiectul curent?
                    mp[lc][c] = pn;               // Retinem profitul nou.
                else
                    mp[lc][c] = mp[lp][c]; // Retinem profitul obtinut cu primele o-1 obiecte.
            }
            else
                mp[lc][c] = mp[lp][c];    // Retinem profitul obtinut cu primele o-1 obiecte.
            cout << setw(4) << mp[lc][c]; // Daca vrem sa vedem matricea pe ecran.
        }
        lp = 1 - lp;
        lc = 1 - lc; // Schimbam intre ele liniile.
        // cout << '\n';
    }
    fo << mp[lp][G]; // Am folosit toate obiectele si capacitatea integrala a ruscacului.
    return 0;
}