#include <bits/stdc++.h>
#define lim 5005

using namespace std;

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

int n, weight_max, mat[5][lim*2];

struct object
{
    int val, w;
};

object v[lim];

void read()
{
    in>>n>>weight_max;
    for(int i=1; i<=n; ++i)
    {
        in>>v[i].w>>v[i].val;
    }
}

void solve()
{
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=weight_max; ++j)
        {
            if(i%2==1)
            {
                if(j>=v[i].w)
                {
                    mat[1][j]=max(mat[2][j],mat[2][j-v[i].w]+v[i].val);
                }
                else
                    mat[1][j]=mat[2][j];
                    //cout<<mat[1][j]<<" ";
            }
            else
            {
                if(j>=v[i].w)
                {
                    mat[2][j]=max(mat[1][j], mat[1][j-v[i].w]+v[i].val);
                }
                else
                    mat[2][j]=mat[1][j];
                //cout<<mat[2][j]<<" ";
            }
        }
       // cout<<'\n';
    }
    out<<max(mat[1][weight_max], mat[2][weight_max]);
}

int main()
{
    read();
    solve();
    return 0;
}