#include <iostream>
#include <fstream>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

const int NMAX = 5001;
int N, WEIGHT, weight[NMAX], power[NMAX], dp[2 * NMAX];

int main() {

    f >> N >> WEIGHT;
    for(int i = 1;i <= N;++i) f >> weight[i] >> power[i];

    dp[0] = 1;
    for(int i = 1;i <= N;++i) {
        for(int j = WEIGHT;j >= weight[i];--j)
            if(dp[j - weight[i]])
                dp[j] = max(dp[j], dp[j - weight[i]] + power[i]);
    }

    g << dp[WEIGHT] - 1;

    return 0;
}