#include <bits/stdc++.h>

using namespace std;

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

int dp[5005][10004];
int w[5005], p[5005];

int main()
{
    int n, g, i, j;

    fin >> n >> g;
    for(i = 1; i <= n; ++i)
        fin >> w[i] >> p[i];

    for(i = 0; i <= n; ++i)
        dp[i][0] = 0;
    for(i = 0; i <= g; ++i)
        dp[0][i] = 0;

    for(i = 1; i <= n; ++i)
    {
        for(j = 1; j <= g; ++j)
        {
            if(w[i] > j)
                dp[i][j] = dp[i-1][j];
            else{
                int ax;
                ax = dp[i-1][j-w[i]] + p[i];
                ax = max(ax, dp[i-1][j]);
                dp[i][j] = ax;
            }
        }
    }

    fout << dp[n][g];

    return 0;
}