Untitled

#include <iostream>
#define MAX_N 20
#define INF 1000000

using namespace std;

struct Gate {
    int soldiers;
    int cost;
};

int N;
Gate gates[MAX_N];
int minCost;

// Hàm để tìm chi phí nhỏ nhất
void findMinCost(int idx, int remainingSoldiers, int currentCost, int soldierUsage[MAX_N]) {
    if (idx == N) {
        if (currentCost < minCost) {
            minCost = currentCost;
        }
        return;
    }

    // Cách 1: Pass (Trả tiền để đi qua cổng)
    findMinCost(idx + 1, remainingSoldiers, currentCost + gates[idx].cost, soldierUsage);

    // Cách 2: Hire (Thuê lính ở cổng đó)
    findMinCost(idx + 1, remainingSoldiers + gates[idx].soldiers, currentCost + 2 * gates[idx].cost, soldierUsage);

    // Cách 3: Battle (Đánh nhau nếu đủ lính)
    if (remainingSoldiers >= gates[idx].soldiers) {
        int originalRemainingSoldiers = remainingSoldiers;
        int originalUsage[MAX_N];

        for (int i = 0; i < N; i++) {
            originalUsage[i] = soldierUsage[i];
        }

        // Tỉ lệ chết 1:1
        for (int i = 0; i < N && remainingSoldiers >= gates[idx].soldiers; i++) {
            if (soldierUsage[i] > 0) {
                int canUse = min(soldierUsage[i], gates[idx].soldiers);
                soldierUsage[i] -= canUse;
                remainingSoldiers -= canUse;
                gates[idx].soldiers -= canUse;

                // Lính đánh quá 3 lần thì giải tán
                if (soldierUsage[i] <= 0) {
                    soldierUsage[i] = 0;
                }
            }
        }

        if (gates[idx].soldiers <= 0) {
            findMinCost(idx + 1, remainingSoldiers, currentCost, soldierUsage);
        }

        for (int i = 0; i < N; i++) {
            soldierUsage[i] = originalUsage[i];
        }
    }
}

int main() {
    int T;
    cin >> T;

    for (int t = 0; t < T; t++) {
        cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> gates[i].soldiers >> gates[i].cost;
        }

        minCost = INF;
        int soldierUsage[MAX_N] = {0};

        findMinCost(0, 0, 0, soldierUsage);

        cout << "#" << t + 1 << " " << minCost << endl;
    }

    return 0;
}