// PULL-DP KNAPSACK

#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

//#define fin cin
//#define fout cout

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

const int MAX_WEIGHT = 10000, MAX_OBJECTS = 5000;

int n,w;
pair<int,int> objects[MAX_OBJECTS + 1];


// dp[weight][numberOfObjects]
int dp[MAX_WEIGHT + 1][MAX_OBJECTS + 1];

int ans = 0;

int main() {

    fin >> n >> w;
    for (int i = 1; i <= n; i++) {
        int a,b;
        fin >> a >> b;
        objects[i] = {a,b};
    }

    for (int it = 1; it <= n; it++) {
        const pair<int,int>& object = objects[it];
        for (int weight = 0; weight <= w; weight++) {
            if (weight - object.first >= 0) {
                dp[weight][it] = max(dp[weight][it], dp[weight - object.first][it - 1] + object.second);
            }
            dp[weight][it] = max(dp[weight][it], dp[weight][it - 1]);
            ans = max(ans, dp[weight][it]);
        }
    }

    fout << ans;

    return 0;
}