#include <fstream>
#include <iostream>
#define maxim 10009

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");


int n,G;
int ans[2][maxim];

struct
{
 int w,p;
}ob[maxim];


void citire()
{
    f>>n>>G;
    for (int i=1;i<=n;i++)
        f>>ob[i].w>>ob[i].p;
}


int main()
{
    citire();
    int l1=0;
    int l2=1;
    for (int i=1;i<=n;i++)
      {for (int j=0;j<=G;j++)
    {
        if (ob[i].w<=j)
            ans[l2][j]=max(ans[l1][j],ans[l1][j-ob[i].w]+ob[i].p);
        else ans[l2][j]=ans[l1][j];
        //cout<<ans[i][j]<<" ";

    }swap(l1,l2);
      }
    if (n%2==0)
    g<<ans[0][G];
    else g<<ans[1][G];

    return 0;

}