#include <fstream>
#include <iostream>

using namespace std;

int a[4][10004], n, g;
int p[5003], w[5003];

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

int main()
{
    int i, j, l;
    fin >> n >> g;
    for (i = 1; i <= n; i++)
        fin >> w[i] >> p[i];
    l = 1;
    for (i = 1; i <= n; i++)
    {
        for (j = 0; j <= g; j++)
        {
            if (l == 1)
            {
                a[1][j] = a[2][j];
                if (w[i] <= j)
                    a[1][j] = max(a[1][j], a[2][j-w[i]] + p[i]);
            }
            else
            {
                a[2][j] = a[1][j];
                if (w[i] <= j)
                    a[2][j] = max(a[2][j], a[1][j-w[i]] + p[i]);
            }
        }
        if (l == 2) l = 1;
        else l = 2;
    }
    fout << a[((n%2)^1)+1][g] << "\n";
    return 0;
}