#include #include #include using namespace std; int subjects, people; struct professor { int salary; int n; vector subject; }; professor candidate[205]; int candidates; int dp[201][1 << 8][1 << 8]; int rec(int at, int bitmask1, int bitmask2) { if((__builtin_popcount(bitmask1) == subjects) and (__builtin_popcount(bitmask2) == subjects)) { return 0; } if(at == candidates) { // cout << bitmask1 << " " << bitmask2 << endl; return 1e8; } if(dp[at][bitmask1][bitmask2] != -1) { return dp[at][bitmask1][bitmask2]; } int new_mask1 = bitmask1; int new_mask2 = bitmask2; for(int i = 0; i < candidate[at].n; i++) { int p = candidate[at].subject[i]; if(new_mask1 & (1 << p)) { new_mask2 |= (1 << p); } else { new_mask1 |= (1 << p); } } int result = 1e8; result = min(result, rec(at + 1, new_mask1, new_mask2) + candidate[at].salary); result = min(result, rec(at + 1, bitmask1, bitmask2)); return dp[at][bitmask1][bitmask2] = result; } int main() { memset(dp, -1, sizeof dp); cin >> subjects >> people; professor initial[people + 1]; int initial_salary = 0; int mask1 = 0, mask2 = 0; for(int i = 0; i < people; i++) { cin >> initial[i].salary >> initial[i].n; initial_salary += initial[i].salary; for(int j = 0; j < initial[i].n; j++) { int p; cin >> p; p--; initial[i].subject.push_back(p); if(mask1 & (1 << p)) { mask2 |= (1 << p); } else { mask1 |= (1 << p); } } } cin >> candidates; for(int i = 0; i < candidates; i++) { cin >> candidate[i].salary >> candidate[i].n; for(int j = 0; j < candidate[i].n; j++) { int p; cin >> p; candidate[i].subject.push_back(p - 1); } } cout << rec(0, mask1, mask2) + initial_salary << endl; return 0; } // 011