Computer

#include <iostream>

using namespace std;

const int N = 20;
const int M = 30;

int numDevices, numPackages, numNeeded;
int devicePrices[N], deviceCount[N], deviceNeeded[N];
int price = 0;

struct Package {
    int price;
    int num;
    int deviceList[N];
};

Package packageList[N + M];

void init() {
    for (int i = 1; i <= N; i++) {
        deviceCount[i] = 0;
    }
    price = 0;
}

void input() {
    
    cin >> numDevices;
    for (int i = 1; i <= numDevices; i++) {
        cin >> devicePrices[i];
    }
    
    cin >> numPackages;
    for (int i = 1; i <= numPackages; i++) {
        cin >> packageList[i].price;
        cin >> packageList[i].num;
        for (int j = 1; j <= packageList[i].num; j++) {
            cin >> packageList[i].deviceList[j];
        }
    }
    
    cin >> numNeeded;
    deviceCount[0] = numNeeded;
    for (int i = 1; i <= numNeeded; i++) {
        cin >> deviceNeeded[i];
        deviceCount[deviceNeeded[i]] = 1;
    }
}
    
void firstCalculate() {
    for (int i = 1; i <= numNeeded; i++) {
        price += devicePrices[deviceNeeded[i]];
    }
}

void mergePack() {
    for (int i = 1; i <= numDevices; i++) {
        int index = i + numPackages;
        packageList[index].price = devicePrices[i];
        packageList[index].num = 1;
        packageList[index].deviceList[1] = i;
    }
    numPackages += numDevices;
}

int check(int idPack) {
    int flag = 0;
    for (int i = 1; i <= packageList[idPack].num; i++) {
        if (deviceCount[packageList[idPack].deviceList[i]] == 1) {
            flag = 1;
            deviceCount[0]--;
        }
        deviceCount[packageList[idPack].deviceList[i]]--;
    }
    if (flag == 1) return 1;
    return 0;
}

void backTrack(int x, int currentPrice) {
    
    if (deviceCount[0] == 0) {
        if (price > currentPrice) {
            price = currentPrice;
        }
        return;
    }
    
    x++;
    if (x > numPackages) return;
    
    for (int i = x; i <= numPackages; i++) {
        int backedDeviceCount[N];
        for (int i = 0; i <= numDevices; i++) {
            backedDeviceCount[i] = deviceCount[i];
        }
        
        if (check(i) == 1) {
            backTrack(i, currentPrice + packageList[i].price);
        }
        
        for (int i = 0; i <= numDevices; i++) {
            deviceCount[i] = backedDeviceCount[i];
        }
    }
}

int main(){
    int t = 1;
    for (int tc = 1; tc <= t; tc++) {
        init();
        input();
        firstCalculate();
        mergePack();
        backTrack(0, 0);
        cout << price << endl;
    }
    return 0;
}