#include <bits/stdc++.h>
using namespace std;
const int nmax = 5e3;
const int gmax = 1e4;

int w[nmax+5], c[nmax+5];
int dp[nmax+5][gmax+5];

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

    int n, mx; f >> n >> mx;
    for(int i=1; i<=n; i++) 
        f >> w[i] >> c[i];

    for(int i=1, t=1; i<=n; i++, t^=1) 
        for(int j=0; j<=mx; j++) {
            dp[t][j] = max(dp[t][j], dp[1^t][j]);
            if(j >= w[i]) dp[t][j] = max(dp[t][j], dp[1^t][j-w[i]] + c[i]);
        }
    g << dp[n%2][mx];
    return 0;
}