#include <fstream>

unsigned int dp[2][int(1e4)+1], n, g;

int main()
{
    std::fstream fin("rucsac.in", std::ios::in);
    std::fstream fout("rucsac.out", std::ios::out);

    fin>>n>>g;

    for(unsigned int i = 1; i <= n; i++){

        unsigned int w, p;

        fin>>w>>p;

        for(unsigned int j = 1; j < w; j++)
            dp[i % 2][j] = dp[(i + 1) % 2][j];

        for(unsigned int j = w; j <= g; j++)
            dp[i % 2][j] = std::max(dp[(i + 1) % 2][j], p + dp[(i + 1) % 2][j - w]);
    }

    fout<<std::max(dp[0][g], dp[1][g]);
}