#include <iostream>
#include<fstream>
#include<vector>

using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");


int elements;
int capacity;
int cost[5001];
int profit[5001];


int DP[10001][5001];


void read() {
    in >> elements >> capacity;


    for (int i = 0; i < elements; i++) {
        in >> cost[i] >> profit[i];
    }



}


int knapsack(int capacity, int n) {


    if (n < 0)
        return 0;


    if (DP[capacity][n] == -1) {
        int to_return = 0;

        if (cost[n] > capacity) {
            to_return = knapsack(capacity, n - 1);
        } else {

            int v1 = profit[n] + knapsack(capacity - cost[n], n - 1);
            int v2 = knapsack(capacity, n - 1);
            to_return = max(v1, v2);
        }

        DP[capacity][n] = to_return;
        return to_return;
    }
    return DP[capacity][n];


}


int knapsack2(int capacity, int n) {
    for (int i = 1; i <=capacity; i++) {
        for (int k = 0; k < n; k++) {
            if (cost[k] > i) {
                DP[i][k] =DP[i][k-1];
            }
            else {
                int v1 = profit[k] + DP[i - cost[k]][k - 1];
                int v2 = DP[i][k - 1];

                DP[i][k] = max(v1, v2);
            }
        }
    }
    return DP[capacity][n-1];


}

void knapsack() {


}

int main() {
    read();
    out << knapsack2(capacity, elements);
    return 0;
}