#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int s,n;
int 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 <= n; ++i) {
        for(j = s; j >= 1; --j) {
            if (w[i] <=j )
            dp[j] = max(dp[j], dp[j - w[i]] +p[i]);
        }
    }
    g<<dp[s];
    return 0;
}