#include <bits/stdc++.h>

using namespace std;

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

const int MAX_N = 5000;  // Numărul maxim de obiecte
const int MAX_G = 10000; // Greutatea maximă a rucsacului

int W[MAX_N];  // Tablou static pentru greutățile obiectelor
int P[MAX_N];  // Tablou static pentru profiturile obiectelor
int D[MAX_G + 1];  // Tablou static pentru programarea dinamică (profituri maxime)

int main() {
    int N, G;  // N = numărul de obiecte, G = greutatea maximă a rucsacului
    fin >> N >> G;

    // Citirea datelor de intrare
    for (int i = 0; i < N; i++) {
        fin >> W[i] >> P[i];
    }

    // Inițializarea tabloului D cu 0
    ///fill(D, D + G + 1, 0);

    // Programare dinamică pentru calcularea profitului maxim
    for (int i = 0; i < N; i++) {
        // Parcurgem greutățile invers, pentru a nu suprascrie valori necesare
        for (int cw = G; cw >= W[i]; cw--) {
            D[cw] = max(D[cw], D[cw - W[i]] + P[i]);
        }
    }

    // Afișarea valorilor intermediare din D pentru debugging
    /*for (int i = 0; i <= G; ++i) {
        cout << i << " " << D[i] << "\n";
    }*/

    // Rezultatul final este profitul maxim pentru greutatea maximă G
    fout << D[G] << endl;

    fin.close();
    fout.close();

    return 0;
}