#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

ifstream f("rucsac.in"); ofstream g("rucsac.out");

int n, s, dp[10005], w[5005], p[5005];

int main() {
    int i,j;
    f>>n>>s;
    for(i = 1; i <= n; ++i) {
        f>>w[i]>>p[i];
    }
    for(i = 1; i <= s; ++i) {
        if (w[1] <= i) {
            dp[i] = p[1];
        }
        else {
            dp[i] = 0;
        }
    }
    for(i = 2; i <= n; ++i) {
        for(j = s; j >= 1; --j) {
            if (w[i] <= j) {
                dp[j] = max(dp[j - w[i]] + p[i], dp[j]);
            }
        }
    }
    g<<dp[s];
    return 0;
}