//
// Created by Vlad-Petru Nitu on 23/09/24.
// Knapsack 0/1: https://www.infoarena.ro/problema/rucsac
//

#include <iostream>
#include <vector>
#include <array>
#include <climits>

#define NMAX 5002
#define WMAX 10002

using namespace std;

std::array<int, NMAX> w;
std::array<int, NMAX> p;
std::array<std::array<int, NMAX>, WMAX> dp;

void solve() {

    int n, W_MAX;
    cin >> n >> W_MAX;

    for (int i = 1; i <= n; ++i) {
        cin >> w[i] >> p[i];
    }

    for (int i = 1; i <= n; ++i)
        for (int used_weight = 1; used_weight <= W_MAX; ++used_weight) {
            dp[i][used_weight] = dp[i-1][used_weight]; // case 1: don't take obj. 'i'
            if (used_weight - w[i] >= 0) { // case 2: take obj 'i', if there's enough "room"(weight) for it left
                dp[i][used_weight] = max(dp[i][used_weight], dp[i - 1][used_weight-w[i]] + p[i]);
            }
        }

    cout << dp[n][W_MAX] << '\n';

}

int main() {
    std::ios_base::sync_with_stdio(false);
    solve();
   return 0;
}