#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;

struct objects
{
    int weight, profit;
};
objects obj[5001];

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

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

    fout << m[n][g];

    return 0;
}