#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 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 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 << dp[n][maxWeight];

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