#include <iostream>
#include <fstream>

using namespace std;
int w[5001], p[5001], g[10001];
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int main()
{
    long long int n, G;
    fin >> n >> G;
    for(int i = 1; i <= n; i++)
    {
        fin >> w[i] >> p[i];
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = G; j >= 0 ; j--)
        {
            if(j - w[i] >= 0)
            {
                g[j] = max(g[j], g[j-w[i]]+p[i]);
            }
           // cout << g[j] << ' ';
        }
        //cout << endl;
    }
    fout << g[G];
    return 0;
}