#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][2 * NMAX];

int main() {

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

    for(int i = 1;i <= N;++i) {

        int t = i % 2;

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

    }

    g << dp[N % 2][WEIGHT];

    return 0;
}