#include <bits/stdc++.h>
using namespace std;

/**
Problema rucsacului - varianta discreta

Se da un rucsac de capacitate G
Se dau si n obiecte de valori
v1 v2 ..., vn si greutati g1,g2,...gn
Sa se determine vlaorea maxima posibila
care se obtine punand unele obiecte in
rucsac, suma greutatilor obiectelor
puse sa fie <= G.

n=6 G=10
g v
3 7
3 4
1 2  dp[3][7] = 13
1 9  dp[4][8] = dp[3][8-1]+v[4]
2 4
1 5

dp matrice cu n linii si G coloane
dp[i][j] = valoarea maxima care se poate
  obtine din primele i obiecte,
  obiectele alese avand greutatea totala j

Initial:
dp[1][g[1]] = v[1]

Recurente:
dp[i][j] = max(
           dp[i-1][j] (a[i] nu l-am pus)
           dp[i-1][j-g[i]]+v[i] (il pun pe ob. i)
            )
i=2..n, j=1..G



Solutia: dp[n][j], j=1..G
*/
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int G, n, g[5003], v[5003];
int dp[5002][10002];

int main()
{
    int i, j, maxx;
    fin >> n >> G;
    for (i = 1; i <= n; i++)
        fin >> g[i] >> v[i];

    dp[1][g[1]] = v[1];
    for (i = 2; i <= n; i++)
        for (j = 1; j <= G; j++)
        {
            maxx = dp[i-1][j];
            if (j >= g[i])
                maxx = max(maxx,
                            dp[i-1][j-g[i]]+v[i]);
            dp[i][j] = maxx;
        }
    maxx = 0;
    for (j = 1; j <= G; j++)
        maxx = max(maxx, dp[n][j]);
    fout << maxx << "\n";
    fout.close();
    return 0;
}