#include <bits/stdc++.h>

using namespace std;

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

int n, g, w, p, d[3][10005];

int main()
{
    F >> n >> g;
    for(int i = 1; i <= n; ++ i)
    {
        F >> w >> p;
        if(i%2)
        {
            for(int j = 1; j <= g; ++ j)
                if(j < w) d[0][j]=d[1][j];
                else d[0][j]=max(d[1][j], d[1][j-w]+p);
        }
        else
        {
            for(int j = 1; j <= g; ++ j)
                if(j < w) d[1][j]=d[0][j];
                else d[1][j]=max(d[0][j], d[0][j-w]+p);
        }
    }
    G << d[1][g];
    return 0;
}