#include <bits/stdc++.h>
using namespace std;

#define w first
#define p second

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

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

int n, mx, dp[2][W];
pair<int, int> v[N];

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