#include <bits/stdc++.h>
#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];
        swap(l1,l2);

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

    return 0;
}