#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>

using namespace std;

const string IN_FILE = "rucsac.in";
const string OUT_FILE = "rucsac.out";

struct Item {
    int weight, value;
};

int solveKnapsack(const vector<Item>& items, const int capacity) {
    auto dp = vector<int>(capacity + 1, 0);
    for (const auto& item : items) {
        for (int w = capacity; w >= item.weight; w--) {
            dp[w] = max(dp[w], dp[w - item.weight] + item.value);
        }
    }
    return dp[capacity];
}

pair<vector<Item>, int> readInput() {
    ifstream in(IN_FILE);
    int n, capacity;
    in >> n >> capacity;
    auto items = vector<Item>(n);
    for (int i = 0; i < n; i++) {
        in >> items[i].weight >> items[i].value;
    }
    in.close();
    return make_pair(items, capacity);
}

void writeOutput(const int maxValue) {
    ofstream out(OUT_FILE);
    out << maxValue << "\n";
    out.close();
}

int main() {
    vector<Item> items;
    int capacity;
    tie(items, capacity) = readInput();
    const int maxValue = solveKnapsack(items, capacity);
    writeOutput(maxValue);
    return 0;
}