#include <cstdio>
#include <algorithm>
#include <vector>

#define in "rucsac.in"
#define out "rucsac.out"
#define NMAX (5000 + 7)
#define GMAX (10000 + 7)

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

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], &p[i]);
    for(int i = 1; i <= n; ++i)
    {
        int line = i&1;
        int update = 1- line;
        for(int j = 1; j<= g; ++j)
        {
            if(j < w[i])
            {
                dp[line][j] = dp[update][j];
                continue;
            }
            dp[line][j] = max(dp[update][j], dp[update][j-w[i]] + p[i]);
            maxim = max(maxim, dp[line][j]);
        }
    }
    printf("%d\n", maxim);
    return 0;
}