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


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


int n,g,sol;
int gr[5005];
int pr[5005];
int dp[10005];///profitul maxim prin care pot obt greutatea i


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]);
                sol=max(sol, dp[j+gr[i]]);
            }
        }
    }
    fout<<sol-1;
}


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