#include<iostream>
#include<fstream>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int w[5100],p[5100],dp[11000];
int main()
{

    int N,G,i,j;
    fin>>N>>G;
    for(i=1;i<=N;i++)
        fin>>w[i]>>p[i];
    //w[i]- greutatea elem de pe poz i
    //p[i]- pretul elementului de pe poz i
    //dp[i]- pretul maxim de greutate i
    dp[0]=1;
    for(i=1;i<=N;i++)
    {
        for(j=G;j>=0;j--)//j reprezinta o greutate care s-a obtinut pana acum
        {
            if(dp[j]!=0 && w[i]+j<=G)
            {
                dp[j+w[i]]=max(dp[j+w[i]],dp[j]+p[i]);
            }
        }
    }
    int Max=-1;
    for(i=1;i<=G;i++){
        if(dp[i]>Max)
            Max=dp[i];
    }
  fout<<endl;  
    fout<<Max-1;
}