#include <iostream>
#include <cstdlib>
using namespace std;

int knapsack_recursive(int weights[], int values[], int i, int weight) {
    if (i == 0) return 0;
    else if (weights[i] > weight) return knapsack_recursive(weights, values, i - 1, weight);
    else return max(knapsack_recursive(weights, values, i - 1 , weight),
                    knapsack_recursive(weights, values, i - 1, weight - weights[i]) + values[i]);
}

int knapsack(int weights[], int values[], int n, int weight) {
    int* e = new int[weight + 1];
    int* c = new int[weight + 1];

    // fill for 1st element
    for (int i = 1; i <= weight; ++i) {
        e[i] = weights[1] <= i ? values[1] : 0;
    }

    // fill for rest of elements
    for (int i = 2; i <= n; ++i) {
        for (int w = weights[i]; w <= weight; ++w) {
            c[w] = max(e[w], e[w - weights[i]] + values[i]);
        }

        for (int w = 0; w <= weight; ++w) {
            e[w] = c[w];
        }
    }

    return e[weight];
}

int main() {
    int n, weight;
    cin >> n >> weight;
    int* weights = new int[n + 1];
    int* values = new int[n + 1];
    for (int i = 1; i <= n; ++i) {
        cin >> weights[i] >> values[i];
    }
    cout << knapsack(weights, values, n, weight) << '\n';
    delete[] weights;
    delete[] values;
    return 0;
}