#include <fstream>

using namespace std;

int n, c;
int table[2][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];

    bool b = false;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= c; j++)
        {
            table[b][j] = table[!b][j];

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

    g << table[!b][c];

    return 0;
}