#include <iostream>
#define fi first 
#define se second
using namespace std;

int dp[2][10005];
pair<int, int> w[5005];

int main() {
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    int n, mg; cin >> n >> mg;
    for(int i = 1; i <= n; i ++) {
        cin >> w[i].fi >> w[i].se;
    }
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= mg; j ++) {
            if(j - w[i].fi >= 0)
                dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - w[i].fi] + w[i].se);
            else
                dp[i % 2][j] = dp[(i - 1) % 2][j];
        }
    }
    cout << dp[n % 2][mg];
}