#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int N, G;
    fin >> N >> G;

    vector<int> w(N), p(N);
    for (int i = 0; i < N; ++i)
        fin >> w[i] >> p[i];

    vector<int> elozo(G+1), akt(G+1);

    for (int g = 0; g <= G; ++g)
        if (g < w[0])
            akt[g] = 0;
        else
            akt[g] = p[0];

    for (int i = 1; i < N; ++i) {
        elozo.swap(akt);

        for (int g = 0; g <= G; ++g) {
            int mx = elozo[g];

            if (g >= w[i]) {
                int masik = elozo[g-w[i]] + p[i];
                if (masik > mx)
                    mx = masik;
            }

            akt[g] = mx;
        }
    }

    fout << akt[G] << '\n';

    return 0;
}