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

ifstream f("rucsac.in");
ofstream g("rucsac.out");
struct obiect
{
    int greutate, profit;
};
int n,i,j,gmax, a[10001], b[10001];
obiect x[10001];
int main()
{
   f>>n>>gmax;
   for(i=1;i<=n;i++)
   f>>x[i].greutate>>x[i].profit;
   for(i=1;i<=n;i++)
    for(j=1;j<=gmax;j++)
        if(i%2==1)
        {
            if(j<x[i].greutate)
                    a[j]=b[j];
            else
                a[j]=max(b[j], x[i].profit+b[j-x[i].greutate]);

        }
        else
        {  if(j<x[i].greutate)
                    b[j]=a[j];
            else
                b[j]=max(a[j], x[i].profit+a[j-x[i].greutate]);
        }
   if(n%2==0)
    g<<b[gmax];
   else
    g<<a[gmax];
   f.close();
   g.close();
    return 0;
}