#include <fstream>

using namespace std;

int n, c;
int table[5000][10000];

int v[5000];
int w[5000];

int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");

    f >> n >> c;

    for(int i = 1; i <= n; i++)
        f >> w[i] >> v[i];

    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= c; j++)
        {
            table[i][j] = table[i-1][j];

            if(w[i] <= j)
                table[i][j] = max(table[i][j], v[i] + table[i-1][j-w[i]]);
        }

    g << table[n][c];

    return 0;
}