今ある料理 \(p\) が作れるかどうかは、それ以前に作成した料理の集合 \(T\) にのみ依存します。よって、常に今まで作った料理の集合のみを管理しておけばよいため、

「 \(dp[T] =\) 料理の集合 \(T\) は作れるかどうか？」とした dp を考えましょう。

\(dp[T + \{p\}] ~ |= dp[T]\) という遷移が可能かどうかは \(S \subset T\) であって \((p, S)\) が失敗条件であるものがあるかどうかです。

もちろん、毎回これを愚直に \(O(M)\) で確認することはできません。よって「 \(T\) のとき \(p\) は作成可能か？」を前計算しておくことにしましょう。 これは、各 \((p, S)\) について \(S \subset T\) であるような \(T\) を禁止できれば良く、ゼータ変換 と呼ばれるものです。

各 \(p\) について愚直にやれば \(O(N^2 2^N)\) ですが、 演算が or であることを利用して、\(p\) bit目で料理 \(p\) について管理することにして、同時に行えば \(O(N 2^N)\) です。

そして、この前計算を用いて、dp をすれば \(O(N 2^N + M + \sum c_q)\) で計算できます。

実装例 （実装では dp でそのまま満足度を計算しています）

n, m = map(int, input().split())
a = list(map(int, input().split()))
ng = [0] * (1 << n)
for i in range(m):
    p, c, *x = map(int, input().split())
    bit = 0
    for xi in x:
        bit |= 1 << xi - 1
    ng[bit] |= 1 << p - 1

for bit in range(1 << n):
    for i in range(n):
        if bit >> i & 1 == 0:
            ng[bit | 1 << i] |= ng[bit]

dp = [- (1 << 30)] * (1 << n)
dp[0] = 0
for bit in range(1 << n):
    for i in range(n):
        if bit >> i & 1 == 0 and ng[bit] >> i & 1 == 0:
            dp[bit | 1 << i] = dp[bit] + a[i]
print(max(dp))