#include <bits/stdc++.h>
using namespace std;
 
ifstream in("rucsac.in");
ofstream out("rucsac.out");
#define cin in
#define cout out
#define NMAX 5005
#define GMAX 10005

int N, G, max_profit;
int W[NMAX], P[NMAX];
int dp[2][GMAX];

void rucsac() {
    for(int i = 0; i < N; i++)
        for(int w = 0; w <= G; w++) {
            dp[0][w] = dp[1][w];
            if(W[i] <= w)
                dp[1][w] = max(dp[1][w], dp[0][w - W[i]] + P[i]);
        }
 
    max_profit = dp[1][G];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> G;
    for(int i = 0; i < N; i++)
        cin >> W[i] >> P[i];

    rucsac();
    cout << max_profit;
}