#include <iostream>
#include <fstream>
#include <cstring>
#define maxi 10000
#define nmax 1000
using namespace std;
ifstream f;
ofstream G;
int dp1[maxi+5],dp2[maxi+5],n,g,greutate[nmax+5],profit[nmax+5];
void read()
{
    f.open("rucsac.in",ios::in);
    f>>n>>g;
    for(int i=1;i<=n;i++)
    {
        f>>greutate[i]>>profit[i];
    }
    f.close();
    return;
}
inline int maxim(int a,int b)
{
    return(a>b?a:b);
}
int dinamica()
{
    for(int i=0;i<=g;i++)
    {
        if(i>=greutate[1])
        {
            dp1[i]=profit[1];
        }
    }
    for(int stari=2;stari<=n;stari++)
    {
        for(int i=0;i<=g;i++)
        {
            dp2[i]=dp1[i];
        }
        for(int i=0;i<=g;i++)
        {
            if(i-greutate[stari]>=0)
            {
                dp2[i]=maxim(dp2[i],dp1[i-greutate[stari]]+profit[stari]);
            }
        }
        for(int i=0;i<=g;i++)
            dp1[i]=dp2[i];
    }
    return dp2[g];
}
int main()
{
    G.open("rucsac.out",ios::out);
    read();
    G<<dinamica();
    G.close();
    return 0;
}