#include <fstream>

#define NMAX 5005
#define MMAX 10005

using namespace std;

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

int n, m, v[NMAX], v1[NMAX], a[5][MMAX];

int main()
{
    fin >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        fin >> v[i] >> v1[i];
    }

    for (int k = 0; k <= m; k++)
    {
        if (k >= v[1])
            a[1][k] = max(a[0][k], a[0][k - v[1]] + v1[1]);
        else
            a[1][k] = a[0][k];
    }

    for (int i = 2; i <= n; i++)
    {
        for (int k = 0; k <= m; k++)
        {
            if (k >= v[i])
                a[2][k] = max(a[1][k], a[1][k - v[i]] + v1[i]);
            else
                a[2][k] = a[1][k];
        }

        for (int k = 0; k <= m; k++)
        {
            swap(a[1][k], a[2][k]);
            a[2][k] = 0;
        }
    }

    fout << a[1][m];
    return 0;
}