#include<bits/stdc++.h>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
#define nrmax 5000
int w[nrmax+5],p[nrmax+5],s[nrmax+1];
int N,G;
void read()
{

    in>>N>>G;
    for(int i=1;i<=N;++i)
        in>>w[i]>>p[i];
}
void solve()
{
    s[0]=0;
    int solutie=0;
    for( int i = 1; i <= N; ++i)
		for( int j = G - w[i]; j >= 0; --j){
            if(s[j+w[i]]<s[j]+p[i])
        {
            s[j+w[i]]=s[j]+p[i];


        } if(s[j+w[i]]>solutie)
        solutie=s[j+w[i]];
		}
        out<<solutie;
}
int main()
{
    read();
    solve();
    return 0;

}