#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int t[5010][10010],i,j,G,N,w[5010],v[5010];
void sup(int i)
{int j;
    for(j=1;j<=G;j++)
    if(w[i]>j)
    t[i][j]=t[i-1][j];
    else
        t[i][j]=max(v[i]+t[i-1][j-w[i]],t[i-1][j]);
}
int main()
{
fin>>N>>G;
for(i=1;i<=N;i++)
    fin>>w[i]>>v[i];
//for(i=1;i<=N;i++)
//    for(j=i+1;j<=N;j++)
//    if(w[i]>w[j])   //sortarea dupa grutate
//{w[0]=w[i];
//w[i]=w[j];
//w[j]=w[0];
//v[0]=v[i];
//v[i]=v[j];
//v[j]=v[0];
//}
for(i=1;i<=N;i++)
sup(i);
    fout<<t[N][G];
    return 0;
}