#include <fstream>

using namespace std;

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

/// https://www.infoarena.ro/problema/rucsac
int m[5001][10001]={0};
int n, g, i, j;

int weight[5001], profit[5001];

int main() {
    fin >> n >> g;
    for (i=1; i<=n; i++)
        fin >> weight[i] >> profit[i];

    for (i=1; i<=n; i++)
    {
        for (j=0; j<=g; j++)
        {
            if (weight[i] <= j)
                m[i][j] = max(m[i-1][j], profit[i] + m[i-1][j-weight[i]]);
            else
                m[i][j] = m[i-1][j];
        }
    }

    fout << m[n][g];

    return 0;
}