#include <fstream>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
struct fint
{
    int greutate,price;
};
const int nm=10000;
int dp[nm+5],aux[nm+5];
fint v[5005];
int n,gmax;
int main()
{
    cin>>n>>gmax;
    for(int i=1;i<=n;i++)
        cin>>v[i].greutate>>v[i].price;
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j+v[i].greutate<=gmax;j++)
            if(dp[j])
                aux[j+v[i].greutate]=dp[j]+v[i].price;
        for(int j=1;j<=gmax;j++)
            dp[j]=aux[j];
    }
    int sol=0;
    for(int i=1;i<=gmax;i++)
        sol=max(sol,dp[i]-1);
    cout<<sol;
    cin.close();
    cout.close();
    return 0;
}
/**
**/