#include <bits/stdc++.h>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n, g, P[5005], G[5005], dp[2][10005], sol;

int main()
{
    int i, j, start;
    fin >> n >> g;
    for(i = 1;i <= n;i++)
        fin >> G[i] >> P[i];
    for(i = 1;i <= n;i++)
    {
        for(j = 0;j + G[i] <= g;j++)
            dp[1][j + G[i]] = max(dp[0][j + G[i]], dp[0][j] + P[i]), sol = max(sol, dp[1][j + G[i]]);
        for(j = 0;j <= g;j++)
            dp[0][j] = max(dp[0][j], dp[1][j]);
    }
    fout << sol << "\n";
    fout.close();
    return 0;
}