#include <stdio.h>

#define newline '\n'
#define uns unsigned

const uns NMAX = 5005;
const uns MAXG = 10005;

struct Item
{
    int w, prof;
};

int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    int dp[2][MAXG];
    int n, g;
    scanf("%d %d", &n, &g);

    struct Item e[NMAX];
    for (int i = 1; i <= n; i++)
        scanf("%d %d", &e[i].w, &e[i].prof);

    int line = 0;
    for (int i = 1; i <= n; i++, line = 1 - line)
    {
        for (int cw = 0; cw <= g; cw++)
        {
            dp[1 - line][cw] = dp[line][cw];
            if (cw >= e[i].w)
            {
                dp[1 - line][cw] = (dp[line][cw] > dp[line][cw - e[i].w] + e[i].prof) ? dp[line][cw] : dp[line][cw - e[i].w] + e[i].prof;
            }
        }
    }

    printf("%d", dp[line][g]);
    return 0;
}