#include<bits/stdc++.h>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
#define nrmax 5000
#define maxg 10001
int w[nrmax+5],p[nrmax+5];
 int s[maxg];
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 = 0; 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;

}