#include <bits/stdc++.h>
#define INF 2e9

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n, G, dp[2][100005], g[5005], v[5005];

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

    for (i = 1; i <= n; i++)
        for (j = G; j >= 0; j--)
            if (j >= g[i % 2])
                dp[i % 2][j] = max(dp[1 - (i % 2)][j - g[i]] + v[i], dp[1 - (i % 2)][j]);
            else dp[i % 2][j] = dp[1 - (i % 2)][j];
    sol = 0;
    j = 1 - (i % 2);
    for (i = 0; i <= G; i++)
        sol = max(sol, dp[j][i]);
    fout << sol;

    return 0;
}