#include <fstream>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
#define VMAX 10001
int s1[VMAX],s2[VMAX],n,g,a,b;
void cons(int s1[],int s2[])
{
    for(int i=1;i<=g;i++)
        s2[i]=0;
    for(int i=1;i<=g-a;i++)
        if(s1[i]!=0)
        {
            if(s2[i]<s1[i]) s2[i]=s1[i];
            if(s2[i+a]<s1[i]+b) s2[i+a]=s1[i]+b;
        }
    for(int i=g-a+1;i<=n;i++)
        if(s2[i]<s1[i]) s2[i]=s1[i];
    if(a<=g && s2[a]<b) s2[a]=b;
}
int vmax(int s[])
{
    int vmax=0;
    for(int i=1;i<=g;i++)
        if(s[i]>vmax) vmax=s[i];
    return vmax;
}
int main()
{
    fin>>n>>g;
    for(int i=1;i<=n;i++)
    {
        fin>>a>>b;
        if(i%2==1)
            cons(s2,s1);
        else
            cons(s1,s2);
    }
    if(n%2==1)
        fout<<vmax(s1);
    else
        fout<<vmax(s2);
    return 0;
}