#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];
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++)
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]);
    fout<<t[N][G];
    return 0;
}