#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <vector>

struct Item {
    std::size_t weight;
    long long value;
};

long long add_nonnegative(long long a, long long b) {
    if (a < 0 || b < 0) throw std::invalid_argument("negative value");
    if (a > std::numeric_limits<long long>::max() - b)
        throw std::overflow_error("value sum");
    return a + b;
}

// Positive weights, nonnegative values; each item can be selected once.
// Total weight may be less than capacity; choosing nothing is allowed.
long long knapsack01(const std::vector<Item>& items, std::size_t capacity) {
    for (const auto& item : items)
        if (item.weight == 0 || item.value < 0)
            throw std::invalid_argument("item domain");
    if (capacity == std::numeric_limits<std::size_t>::max())
        throw std::length_error("capacity + 1");
    std::vector<long long> dp(capacity + 1, 0);
    for (const auto& item : items) {
        if (item.weight > capacity) continue;
        // weight > 0 guarantees this loop stops without unsigned wraparound.
        for (std::size_t c = capacity; c >= item.weight; --c) {
            const auto take = add_nonnegative(dp[c - item.weight], item.value);
            dp[c] = std::max(dp[c], take);
        }
    }
    return dp[capacity];
}

// Exponential oracle for the small valid inputs used below.
long long brute(const std::vector<Item>& items, std::size_t index,
                std::size_t remaining) {
    if (index == items.size()) return 0;
    auto best = brute(items, index + 1, remaining);
    const auto& item = items[index];
    if (item.weight <= remaining) {
        const auto take = add_nonnegative(
            item.value, brute(items, index + 1, remaining - item.weight));
        best = std::max(best, take);
    }
    return best;
}

void check(const std::vector<Item>& items) {
    for (std::size_t capacity = 0; capacity <= 10; ++capacity)
        assert(knapsack01(items, capacity) == brute(items, 0, capacity));
}

void enumerate(std::vector<Item>& items, std::size_t remaining) {
    check(items);
    if (remaining == 0) return;
    const Item choices[] = {{1, 0}, {1, 2}, {2, 3}, {3, 4}};
    for (const auto item : choices) {
        items.push_back(item);
        enumerate(items, remaining - 1);
        items.pop_back();
    }
}

int main() {
    assert(knapsack01({}, 0) == 0);
    assert(knapsack01({{2, 3}}, 4) == 3);
    assert(knapsack01({{5, 7}}, 4) == 0);
    assert(knapsack01({{2, 3}, {2, 4}}, 4) == 7);
    assert(knapsack01({{1, 1}, {3, 4}, {4, 5}, {5, 7}}, 7) == 9);
    assert(knapsack01({{1, std::numeric_limits<long long>::max()}}, 1)
           == std::numeric_limits<long long>::max());

    bool rejected_zero = false, rejected_negative = false;
    bool rejected_overflow = false, rejected_capacity = false;
    try { (void)knapsack01({{0, 1}}, 3); }
    catch (const std::invalid_argument&) { rejected_zero = true; }
    try { (void)knapsack01({{1, -1}}, 3); }
    catch (const std::invalid_argument&) { rejected_negative = true; }
    try {
        (void)knapsack01(
            {{1, std::numeric_limits<long long>::max()}, {1, 1}}, 2);
    } catch (const std::overflow_error&) { rejected_overflow = true; }
    try {
        (void)knapsack01({}, std::numeric_limits<std::size_t>::max());
    } catch (const std::length_error&) { rejected_capacity = true; }
    assert(rejected_zero && rejected_negative);
    assert(rejected_overflow && rejected_capacity);

    std::vector<Item> items;
    enumerate(items, 5);
    std::cout << "0/1 knapsack: all assertions passed\n";
}