#include <fstream>

using namespace std;

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

const int DIM = 5001;
const int GMAX = 10001;

int N, W;
int dp[2][GMAX];
struct object {
    int w, p;
} v[DIM];

int main() {
    fin >> N >> W;
    for (int i = 1; i <= N; i++)
        fin >> v[i].w >> v[i].p;

    int line = 1;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= W; j++) {
            int maxProfit = dp[1 - line][j];
            if (j - v[i].w >= 0)
                maxProfit = max(maxProfit, dp[1 - line][j - v[i].w] + v[i].p);
            dp[line][j] = maxProfit;
        }
        line = 1 - line;
    }

    int solution = 0;
    for (int i = 1; i <= W; i++)
        solution = max(solution, dp[1 - line][i]);
    fout << solution;

    return 0;
}