#include <fstream>

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

int dp[3][10010], w[5010], p[5010], lin1, lin2,n,g;

int main()
{
    fin >> n >> g;

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

    lin1 = 2;
    lin2 = 1;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= g; j++){
            dp[lin1][j] = dp[lin2][j];

            if(j - w[i] >= 0 && p[i] + dp[lin2][j - w[i]] > dp[lin1][j]){
                dp[lin1][j] = p[i] + dp[lin2][j - w[i]];
            }
        }

        swap(lin1, lin2);
    }

    fout << dp[lin2][g];

    return 0;
}