#include <fstream>
using namespace std;
int castig1[10002],castig2[10002],c[10002],gr[10002];
int main()
{
    int n,i,j,g;
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");
    in>>n>>g;
    for(i=1;i<=n;i++)
    {
        in>>gr[i]>>c[i];
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=g;j++)
        {
            if(i%2==1)
            {
                if(gr[i]<=j)
                {
                    if(castig2[j]<castig2[j-gr[i]]+c[i])
                    {
                        castig1[j]=castig2[j-gr[i]]+c[i];
                    }
                    else
                    {
                        castig1[j]=castig2[j];
                    }
                }
                else
                {
                    castig1[j]=castig2[j];
                }
            }
            else
            {
                if(gr[i]<=j)
                {
                    if(castig1[j]<castig1[j-gr[i]]+c[i])
                    {
                        castig2[j]=castig1[j-gr[i]]+c[i];
                    }
                    else
                    {
                        castig2[j]=castig1[j];
                    }
                }
                else
                {
                    castig2[j]=castig1[j];
                }
            }
        }
    }
    if(n%2==1)
        out<<castig1[g];
    else
        out<<castig2[g];
    return 0;
}