#include <fstream>
 
using namespace std;

 
int n, G, p[5000], g[5000];
int dp[3][10001];
 
void rucsac()
{
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= G; j++)
            if (j < g[i])
                dp[(i + 1) % 2][j] = dp[i % 2][j];
            else
                dp[(i + 1) % 2][j] = max(dp[i % 2][j], p[i] + dp[i % 2][j - g[i]]);
    }
}

int main()
{
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
    fin >> n >> G;
    for(int i = 0; i < n; i++) {
        fin >> g[i];
        fin >> p[i];
    }
    rucsac();
    fout << dp[n % 2][G];
    fin.close();
    fout.close();
    return 0;
}