#include <iostream>
#include <fstream>
std::ifstream fin("rucsac.in");
std::ofstream fout("rucsac.out");
#define MOD 1000000007
int bun[10001];
int w[5001];
int p[5001];
int main()
{
    int n, g;
    fin >> n >> g;
    for(int i = 1; i <= n; i++)
    {
        fin >> w[i] >> p[i];     
    }
    bun[0] = 0;
    int maxi = 0;
    for(int i = 1; i <=n ;i++)
    {
        for(int j = g - w[i]; j >= 0; --j){
            if(bun[j + w[i]] < bun[j] + p[i])
            {
                
                bun[j + w[i]] = bun[j] + p[i];
                if(bun[j + w[i]] > maxi)
                {
                    maxi = bun[j + w[i]];
                }
            }
        }
    }    
    fout << maxi;
    return 0;
}