Overview

Represent sets of dishes as bits, and use subset DP to determine whether there exists a feasible ordering that completes exactly that set.
Additionally, the key point is to precompute “dishes that cannot be made next” for each set using SOS DP (propagation over subsets).

Discussion

In this problem, not only “which dishes to choose” but also “in what order to make them” matters.
However, since the constraint is \(N \leq 19\), we can use a \(2^N\)-based DP that holds sets of dishes as bitmasks.

1. Feasibility is easier to handle by considering “the last dish made”

Consider whether there exists a feasible ordering that completes all dishes in a set mask.

Here, if the last dish made is \(i\), the set completed just before that is mask \setminus \{i\}.
Therefore,

• mask \setminus \{i\} is feasible
• Dish \(i\) does not fail in that state

Then, by adding \(i\) at the end, mask is also feasible.

Conversely, if mask is feasible, then letting \(i\) be the last dish in the feasible sequence satisfies the above conditions.

Thus, the following transition holds:

\[ feasible[\mathrm{mask}] = \exists i \in \mathrm{mask} \left( feasible[\mathrm{mask} \setminus \{i\}] \land i \text{ can be made after } \mathrm{mask} \setminus \{i\} \right) \]

This reduces the “ordering problem” to a “subset DP”.

---

2. Naively checking failure conditions each time is too slow

The problem is how to efficiently determine “can dish \(i\) be made now?”

A failure condition \((p,S)\) means:

• “If all dishes in \(S\) are already completed when making dish \(p\), it fails”

In other words, if the completed set is \(T\), then:

\[ p \text{ cannot be made} \iff \exists S \subseteq T \text{ such that } (p,S) \text{ exists} \]

If we check all failure conditions for each state,
we would need to examine all conditions for each mask, costing approximately \(O(M2^N)\).
Since \(M \le 10^5\), this clearly won’t fit in time.

---

3. Precompute “dishes that cannot be made” for each set T

Therefore, for each set T, we maintain:

• bad[T] = “the set of dishes that cannot be made next when T is already completed”

as a bitmask.

First, from the failure conditions themselves, we create:

• bad_exact[S] = “dishes whose failure condition is exactly the set \(S\)”

If there is a failure condition \((p,S)\), we add dish \(p\) to bad_exact[S].

However, what we actually want is bad[T], where:

\[ bad[T] = \bigcup_{S \subseteq T} bad\_exact[S] \]

That is, the OR of all failure conditions that appear as subsets of T.

This can be computed in \(O(N2^N)\) using SOS DP (zeta transform over subsets).

---

4. Concrete Example

Suppose the only failure condition is:

• \((3,\{1,2\})\)

This means “if both dishes 1 and 2 are completed when starting dish 3, it fails.”
Therefore,

• When the completed set is \(\{1,2\}\), dish 3 is forbidden
• When the completed set is \(\{1,2,4\}\), dish 3 is also forbidden
• When the completed set is \(\{1,2,5,6\}\), dish 3 is also forbidden

In this way, dish 3 is forbidden for all sets containing \(\{1,2\}\).
SOS DP performs this “propagation from subsets to supersets” all at once.

---

5. Maximum Satisfaction

If feasible[mask] is true, then there exists some ordering to make that set of dishes.
We then keep the total satisfaction of that set:

\[ sum[\mathrm{mask}] = \sum_{i \in \mathrm{mask}} A_i \]

and take the maximum over all mask where feasible[mask] is true.

Since satisfaction can be negative, the option of making nothing is also important.
Therefore, the initial value of the answer should be \(0\).

Algorithm

1. Represent dish sets as \(N\)-bit integers.

   • If bit \(i\) is 1, the set includes dish \(i\).

2. For each failure condition \((p,S)\), create mask(S) and set:

   • bad[mask(S)] |= (1 << p) At this point, bad only holds information for “exactly that set \(S\) being the condition.”

3. Perform SOS DP to transform each set T into:

   • bad[T] = “the set of dishes that cannot be made next when T is completed” With this, whether dish \(i\) can be made next can be determined in \(O(1)\) by checking bit \(i\) of bad[T].

4. Perform subset DP.

   • feasible[0] = True
   • For each non-empty set mask, consider each dish \(i\) in mask as a candidate for the last dish.
   • Let prev = mask \setminus \{i\}, then:
     • If feasible[prev] = True
     • and i is not in bad[prev] then set feasible[mask] = True

This corresponds to the following formula:

$\( feasible[\mathrm{mask}] = \exists i \in \mathrm{mask} \left( feasible[\mathrm{prev}] \land i \notin bad[\mathrm{prev}] \right) \)$

1. Compute the total satisfaction sumv[mask] for each mask, and update the answer if feasible[mask] is true.

Complexity

• Time complexity: \(O(N2^N + M + \sum c_q)\)
• Space complexity: \(O(2^N)\)

※ The feasible transition iterates over the bits contained in each set, totaling \(O(N2^N)\).
The precomputation of bad (SOS DP) is also \(O(N2^N)\).

Implementation Notes

• bad[mask] is a bitmask representing “the set of dishes that cannot be made,” not a “dish set.”

• For failure condition \((p,S)\), first add \(p\) to bad[S], then propagate to all supersets containing \(S\) via SOS DP.

• A failure condition with \(c_q = 0\) means \(S = \varnothing\), so that dish cannot be made in any state. By putting it in bad[0], it correctly propagates to all states after SOS DP.

• Even if all satisfactions are negative, you can achieve \(0\) by “making nothing,” so the answer should initially be set to 0.

• In the code, sumv[mask] is efficiently computed using the lowest set bit: $\( sumv[\mathrm{mask}] = sumv[\mathrm{mask} \setminus \{\text{lsb}\}] + A_{\text{lsb}} \)$

  Source Code

import sys

data = list(map(int, sys.stdin.buffer.read().split()))
ptr = 0

N = data[ptr]
M = data[ptr + 1]
ptr += 2

A = data[ptr:ptr + N]
ptr += N

size = 1 << N
bad = [0] * size

for _ in range(M):
    p = data[ptr] - 1
    c = data[ptr + 1]
    ptr += 2
    mask = 0
    for _ in range(c):
        mask |= 1 << (data[ptr] - 1)
        ptr += 1
    bad[mask] |= 1 << p

for b in range(N):
    bit = 1 << b
    step = bit << 1
    for base in range(0, size, step):
        dst = base + bit
        for off in range(bit):
            bad[dst + off] |= bad[base + off]

feasible = bytearray(size)
feasible[0] = 1
sumv = [0] * size

ans = 0
for mask in range(1, size):
    lsb0 = mask & -mask
    sumv[mask] = sumv[mask ^ lsb0] + A[lsb0.bit_length() - 1]

    m = mask
    while m:
        lsb = m & -m
        prev = mask ^ lsb
        if feasible[prev] and not (bad[prev] & lsb):
            feasible[mask] = 1
            if sumv[mask] > ans:
                ans = sumv[mask]
            break
        m ^= lsb

print(ans)

---

This editorial was generated by gpt-5.4-high.