#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define w first
#define p second

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

const int N = 5005;
const int W = 10005;

int n, mw, t, dp[2][W];
pii v[N];

int main(){
    f >> n >> mw;
    for (int i = 1; i <= n; i++)
        f >> v[i].w >> v[i].p;
		
    for (int i = 1; i <= n; i++, t = !t){
        for (int j = 0; j <= mw; j++){
            dp[!t][j] = dp[t][j];
            if (v[i].w <= j) 
                dp[!t][j] = max(dp[t][j], dp[t][j - v[i].w] + v[i].p);
        }
    }
    g << dp[t][mw];
    
    return 0;
}