#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <random>

using namespace std;

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

int n, maxWeight;
//int maxProfit = -1;
vector<pair<int, int>> backpack;

const int GMAX = 10010;
const int NMAX = 5001;

//int dp[NMAX][GMAX];

// (3, 1) => 5;
// (greutate totala, indicele ultimului obiect selectat) -> stare
//
//void backtracking(int lastIndex , int sumWeight , int sumProfit, int mat[][GMAX]) {
//    if (sumWeight > maxWeight) {
//        return;
//    }
//    if (mat[lastIndex][sumWeight] != -1 && mat[lastIndex][sumWeight] >= sumProfit) {
//        return;
//    }
//    mat[lastIndex][sumWeight] = sumProfit;
//
//    maxProfit = max(maxProfit, sumProfit);
//
//    for (int i = lastIndex; i < (int) backpack.size(); ++i) {
//        backtracking(i + 1, sumWeight + backpack[i].first, sumProfit + backpack[i].second, mat);
//    }
//}

int maxProfit[GMAX], prevMaxProfit[GMAX];

int main() {
    fin >> n >> maxWeight;
    int weight[n + 1], profit[n + 1];
//    int mat[n + 1][maxWeight + 1];

//    for (int i = 0; i < n; ++i) {
//        for (int j = 0; j < maxWeight; ++j) {
//            mat[i][j] = -1;
//        }
//    }

    for (int i = 0; i < n; ++i) {
        fin >> weight[i] >> profit[i];
//        backpack.emplace_back(weight, profit);
        for (int j = weight[i]; j <= maxWeight; ++j) {
            maxProfit[j] = max(prevMaxProfit[j], prevMaxProfit[j - weight[i]] + profit[i]);
        }

        for (int k = 0; k <= maxWeight; ++k) {
            prevMaxProfit[k] = maxProfit[k];
        }
    }

//    for (int i = 1; i <= n; ++i) {
//        for (int j = 1; j <= maxWeight; ++j) {
//            if (weight[i - 1] <= j) {
//                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + profit[i - 1]);
//            } else {
//                dp[i][j] = dp[i - 1][j];
//            }
//        }
//    }

//    backtracking(0, 0, 0, mat);

    fout << maxProfit[maxWeight];

    return 0;
}
/*
6 10
3 7
3 4
1 2
1 9
2 4
1 5
 */