#include <fstream>

using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int m[10001], g[5001] , v[50001];

int main()
{
    int n , G , i , j;
    in >> n >> G;
    for(i = 1; i <= n; i++)
    {
        in >> g[i] >> v[i];
    }
    for(i = 1; i <= n; i++)
    {
        for(j = G; j >= g[i]; j--)
        {
            m[j] = max(m[j], m[j - g[i]] + v[i]);
        }
    }
    out << m[G];
    return 0;
}