#include <cstring>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <deque>
#include <queue>
using namespace std;

int coli[]= {0,1,0,-1};
int lini[]= {-1,0,1,0};
struct bob
{
    int wg;
    int val;
} negru[5009],benis;
int n,m,ok,s,x,y,v[3][10002],i,j,nr,aux[300][300],k,maxi,x1,x2;
int main()
{
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");
    in>>n>>m;
    for(i=1; i<=n; i++)
        in>>negru[i].wg>>negru[i].val;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
        {
            if(j-negru[i].wg>=0)
                if(i%2==1)
                    v[i%2][j]=max(v[0][j],v[0][j-negru[i].wg]+negru[i].val);
                else
                    v[i%2][j]=max(v[1][j],v[1][j-negru[i].wg]+negru[i].val);
            else
            {
                if(i%2==0)
                    v[i%2][j]=v[1][j];
                else
                    v[i%2][j]=v[0][j];
            }
        }
    out<<v[n%2][m];




    return 0;

}