#include <bits/stdc++.h>
using namespace std;

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

int main()
{
    int n, gmax;
    int i, k, S;
    in >> n >> gmax;
    vector<int> c(n+1), g(gmax+1), cmax(gmax+1);
    vector<vector<int> > uz(gmax+1, vector<int>(n+1));

    for(i = 1; i <= n; i++) in >> g[i] >> c[i];

    for(S = 1; S <= gmax; S++) cmax[S] = -1;
    for(S = 1; S <= gmax; S++)
        for(i = 1; i <= n; i++)
            if(g[i] <= S && cmax[S-g[i]] != -1 && !uz[S-g[i]][i])
                if(cmax[S] < c[i] + cmax[S-g[i]])
                {
                    cmax[S] = c[i] + cmax[S-g[i]];

                    for(k = 1; k <= n; k++) uz[S][k] = uz[S-g[i]][k];
                    uz[S][i] = 1;
                }

    out << cmax[gmax];

	return 0;
}