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

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


int elements;
int capacity;
vector<int> profit;
vector<int> cost;


int DP[10000][5000];


void read() {
    in >> elements >> capacity;
    profit.resize(elements);
    cost.resize(elements);


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


    for (int i = 0; i < 10000; i++) {
        for (int k = 0; k < 5000; k++)
            DP[i][k] = -1;
    }


}


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];


}

void knapsack() {


}

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