#include <bits/stdc++.h>
#define newline '\n'
#define ll long long
#define uns unsigned
#define deb(x) cerr << x << ' '
#define debnewL(x) cerr << x << newline
using namespace std;
///************************************
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
///************************************

const uns NMAX(5005), MAXG(10005);
struct
{
    int w, prof;
} e[NMAX];
int dp[2][MAXG];
int n, g;

int main()
{
    fin >> n >> g;
    for (int i = 1; i <= n; i++)
        fin >> 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] = max(dp[line][cw], dp[line][cw - e[i].w] + e[i].prof);
            }
        }

    fout << dp[line][g];
    fout.close();
    return 0;
}