#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <climits>
using namespace std;

const int MAX = 5;
const int COMBINATION_SIZE = 5;

struct Supply {
    int value;
    int row;
    int col;
};

int resupply(int shortfall, int supply[MAX][MAX]) {
    vector<Supply> supplies;
    
    // Chuyển ma trận thành vector các ô tiếp tế
    for (int i = 0; i < MAX; ++i) {
        for (int j = 0; j < MAX; ++j) {
            supplies.push_back({supply[i][j], i, j});
        }
    }
    
    // Sắp xếp vector theo giá trị tiếp tế tăng dần
    sort(supplies.begin(), supplies.end(), [](const Supply &a, const Supply &b) {
        return a.value < b.value;
    });
    
    int min_total = INT_MAX;
    vector<int> result_indices;

    // Sử dụng hồi quy để tìm tất cả các tổ hợp hợp lệ và chọn tổ hợp có tổng giá trị nhỏ nhất
    function<void(int, int, int, vector<int>&)> find_combinations = [&](int start, int k, int sum, vector<int>& indices) {
        if (k == 0) {
            if (sum >= shortfall && sum < min_total) {
                min_total = sum;
                result_indices = indices;
            }
            return;
        }

        for (int i = start; i <= supplies.size() - k; ++i) {
            indices.push_back(i);
            find_combinations(i + 1, k - 1, sum + supplies[i].value, indices);
            indices.pop_back();
        }
    };

    vector<int> indices;
    find_combinations(0, COMBINATION_SIZE, 0, indices);

    // Trả về tổng giá trị của 5 ô được chọn
    return min_total;
}

int main() {
    int shortfall = 1050;
    int supply[MAX][MAX] = {
        {150, 200, 180, 90, 110},
        {70, 80, 120, 140, 160},
        {220, 240, 200, 190, 130},
        {100, 110, 300, 280, 320},
        {170, 210, 260, 230, 290}
    };

    int result = resupply(shortfall, supply);
    cout << "Tổng tiếp tế của 5 ô được chọn: " << result << endl;

    return 0;
}