#include <bits/stdc++.h>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n, G;
int c[5005], g[5005], dp[5005][10005];
int main()
{
    int i, j, mx = 0;
    fin >> n >> G;
    for(i = 1; i <= n; i++)
        fin >> g[i] >> c[i];
    dp[1][g[1]] = c[1];
    dp[1][0]= 0;
    for(i = 2; i <= n; i++)
    {
        for(j = 0; j <= G; j++)
            if(j >= g[i])
                dp[i][j] = max(dp[i - 1][j - g[i]] + c[i], dp[i - 1][j]);
            else dp[i][j] = dp[i - 1][j];
    }
    for(i = 0; i <= G; i++)
        mx = max(mx, dp[n][i]);
    fout << mx;
    return 0;
}