# include <bits/stdc++.h>
#define nr 5010
#define gmax 10010

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n,g,greutate[10010],cost[5010],dp[10010],costmax;

int main()
{
    int i,j;
    fin>>n>>g;
    for(i=1;i<=n;++i)
        fin>>greutate[i]>>cost[i];
    fin.close();
    for(i=1;i<=n;++i)
    {
        for(j=g-greutate[i];j>=0;j--)
        {
           if(dp[j+greutate[i]]<dp[j]+cost[i])
           {
               dp[j+greutate[i]]=dp[j]+cost[i];
               if(costmax<dp[j+greutate[i]])
               costmax=dp[j+greutate[i]];
           }
        }
    }
    fout<<costmax<<"\n";
    fout.close();
    return 0;
}