#include <cstdio>
#include <algorithm>

#define NMAX 5007
#define GMAX 10007
#define in "rucsac.in"
#define out "rucsac.out"

using namespace std;
int n, g, w[GMAX], v[NMAX], dp[2][GMAX];

int main()
{
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
    scanf("%d %d", &n, &g);
    for(int i = 1; i<= n; ++i) scanf("%d%d", &w[i], &v[i]);
    for(int i = 1; i<= n; ++i)
    {
        int line = i&1, update = (!line);
        for(int j = 1; j<= g; ++j)
        {
            if(w[i] > j)
            {
                dp[line][j] = dp[update][j];
                continue;
            }
            dp[line][j] = max(dp[update][j], dp[update][j - w[i]] + v[i]);
        }
    }
    printf("%d\n", dp[n&1][g]);
    return 0;
}