#include <iostream>
#include <stdio.h>

#define NMAX 5001
#define WMAX 10001

using namespace std;

int N, W;
int dp[NMAX][WMAX];

int price, weight;

int main() {
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    cin >> N >> W;    

    // Base cases; NOTE: they were already taken care by declaring dp as global
    for (int i = 0; i <= N; ++i) {
        dp[i][0] = 0;
    }

    for (int j = 0; j <= W; ++j) {
        dp[0][j] = 0;
    }


    // General cases
    for (int i = 1; i <= N; ++i) {
        cin >> weight >> price;

        for (int j = 1; j <= W; j++) {
            // Setting point of reference
            dp[i][j] = dp[i - 1][j];

            for (int k = 1; k < j; k++) {
                if (k + weight <= j && dp[i - 1][k] + price > dp[i][j]) {
                    dp[i][j] = dp[i - 1][k] + price;
                }
            }
        }
    }

    // Write result
    cout << dp[N][W];

    // DEBUGGING
    // for (int i = 0; i <= N; i++) {
    //     for (int j = 0; j <= W; j++) {
    //         cout << dp[i][j] << '\t';
    //     }
    //     cout << '\n';
    // }

    return 0;
}