#include <bits/stdc++.h>

using namespace std;

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

struct Object {
    int w;
    int p;
};

int main() {
    int N, W;
    int i;

    fin >> N >> W;

    vector<Object> objs(N + 1);
    vector<vector<long long>> dp(2, vector<long long>(W + 1, 0));

    for (i = 1; i <= N; ++i) {
        fin >> objs[i].w >> objs[i].p;
    }

    int prev, curr, cap;
    prev = 0;
    for (i = 1; i <= N; ++i) {
        curr = 1 - prev;
        for (cap = 1; cap <= W; ++cap) {
            dp[curr][cap] = dp[prev][cap];

            int diff = cap - objs[i].w;
            
            // check if the current object
            // can be contained in the knapsack
            if (diff >= 0) {
                dp[curr][cap] = max(dp[curr][cap], 0LL + dp[prev][diff] + objs[i].p);
            }
        }

        prev = curr;
    }

    fout << dp[curr][W] << "\n";

    return 0;
}