D - Goin' to the Zoo https://atcoder.jp/contests/abc404/tasks/abc404_d

abc404_d.py

N, M = map(int, input().split())
C = list(map(int, input().split()))
A = []
zoo = [[] for _ in range(N)]  # i番目の動物園で見ることができる動物
for i in range(M):
    _, *a = list(map(int, input().split()))
    a = list(map(lambda x: int(x) - 1, a))
    for j in a:
        zoo[j].append(i)


ans = float("inf")
for i in range(2, 3**N):        # 全探索
    pat = [0] * N
    num = i
    j = 0
    while num:                  # 3進数へ
        pat[j] = num % 3
        num //= 3
        j += 1
    animals = [0] * M           # i番目の動物を何回見たか。
    for k in range(N):
        # k番目の動物園にpat[k]回行った。
        for z in zoo[k]:
            animals[z] += pat[k]
    ok = all(a >= 2 for a in animals)
    if ok:
        cost = sum(pat[m] * C[m] for m in range(N))
        ans = min(ans, cost)
print(ans)