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