// === Problem Information ===
// Name:
// Statement URL:

// === Solution Information ===
// Copyright (C) 2025 Nicolas Dumitru
// SPDX-License-Identifier: GPL-3.0-or-later
// Submission URL:
// Verdict:

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <istream>
#include <ostream>
#include <utility>
#include <vector>

// TODO: fast
using usize = std::size_t;
using isize = std::ptrdiff_t;
using u8 = std::uint8_t; // std input streams treat this as char
using i8 = std::int8_t;  // std input streams treat this as char
using u16 = std::uint16_t;
using i16 = std::int16_t;
using u32 = std::uint32_t;
using i32 = std::int32_t;
using u64 = std::uint64_t;
using i64 = std::int64_t;

using std::cerr;

template <typename T>
inline auto read(std::istream &input = std::cin) -> T {
    T value;
    input >> value;
    return value;
}

template <typename T>
inline auto read_vector(usize n, std::istream &input = std::cin)
    -> std::vector<T> {
    std::vector<T> v(n);
    for (auto &&x : v) {
        x = read<T>(input);
    }
    return v;
}

struct Item {
    usize weight;
    u32 value;

    Item() : weight(0), value(0) {}

    friend std::istream &operator>>(std::istream &input, Item &item) {
        input >> item.weight >> item.value;
        return input;
    }
};

auto knapsack(std::vector<Item> &items, usize max_weight) -> u32 {
    std::vector<std::vector<usize>> val(2,
                                        std::vector<usize>(max_weight + 1, 0));
    usize prev = 1;
    usize curr = 0;

    for (usize i = 0; i < items.size(); i += 1, std::swap(prev, curr)) {
        const auto w = items[i].weight;
        const auto v = items[i].value;
        for (usize cw = 0; cw <= max_weight; cw += 1) {
            if (w <= cw) {
                val[curr][cw] = std::max(val[prev][cw], val[prev][cw - w] + v);
            } else {
                val[curr][cw] = val[prev][cw];
            }
        }
        for (auto &&x : val[curr]) {
            cerr << x << " ";
        }
        cerr << "\n";
    }

    return val[prev][max_weight];
}

auto main() -> int {
    // std::ios::sync_with_stdio(false);

    std::ifstream knapsack_in("rucsac.in");

    const auto n = read<usize>(knapsack_in);
    const auto w = read<usize>(knapsack_in);

    auto items = read_vector<Item>(n, knapsack_in);

    std::ofstream knapsack_out("rucsac.out");
    cerr << knapsack(items, w) << std::endl;

    return 0;
}