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


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


int n,g,ans;
int gr[5005];
int pr[5005];
int dp[10005];


void read()
{
    fin>>n>>g;
    for(int i=1;i<=n;i++)
        fin>>gr[i]>>pr[i];
}


void solve()
{
    dp[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=g;j>=0;j--)
            if(dp[j] && j+gr[i]<=g)
            {
                dp[j+gr[i]]=max(dp[j+gr[i]],dp[j]+pr[i]);
                ans=max(ans,dp[j+gr[i]]);
            }
    fout<<ans-1;
}


int main()
{
    read();
    solve();
    return 0;
}