#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<vector<int>> din(N, vector<int>(G+1));

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

    for (int i = 1; i < N; ++i)
        for (int g = 0; g <= G; ++g) {
            int mx = din[i-1][g];

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

            din[i][g] = mx;
        }

    fout << din[N-1][G] << '\n';

    return 0;
}