#include <fstream>

#define NMAX 5001
#define WMAX 10001

using namespace std;

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

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

int price, weight;

int main() {
    in >> N >> W;  

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

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

            for (int k = 0; 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
    out << dp[N][W];

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

    return 0;
}