Overview

This problem asks: given “the set of facilities each security company can cover” and “the contract cost,” select companies so that every facility is covered at least once, minimizing the total cost.
Since the number of facilities \(M\) is at most \(18\), it is effective to represent the coverage status of facilities as a bitmask and perform dynamic programming.

Analysis

First, a naive approach would be to exhaustively search all combinations of selecting or not selecting each of the \(N\) companies to find the answer.
However, this method requires examining \(2^N\) combinations, which is impractical when \(N \leq 50\).

On the other hand, the key insight in this problem is that the number of facilities \(M\) is small.
Instead of focusing on “which companies are selected,” if we focus on “which facilities are currently covered,” the number of states is only \(2^M\).

Representing facility sets with bitmasks

We assign 1 bit to each facility.

• Facility \(1\) → bit \(0\)
• Facility \(2\) → bit \(1\)
• …
• Facility \(M\) → bit \(M-1\)

For example, when \(M=4\):

• 0000 : no facilities are covered yet
• 0101 : facilities \(1, 3\) are covered
• 1111 : all facilities are covered

Each security company \(i\) can also have its “set of facilities it can cover” converted into a single bitmask \(b_i\).

DP state

Define \(dp[mask]\) as:

The minimum cost to select companies such that the facility coverage state becomes mask.

The initial state, where nothing is selected, is:

• \(dp[0] = 0\)

When we additionally contract company \(i\), the current coverage state mask changes to:

• mask | b_i

Here | is the bitwise OR.
This means the state becomes the union of “facilities covered so far” and “facilities that company \(i\) can newly cover.”

Therefore, the transition is:

\[ dp[mask \mid b_i] = \min(dp[mask \mid b_i],\ dp[mask] + C_i) \]

Why does this yield the minimum?

By processing each company in order and reflecting whether to “use it / not use it,” all possible selections are eventually considered.
Since we only need to keep the minimum cost for each mask, the problem can be solved with DP.

Infeasibility check

If even combining all companies cannot cover some facility, the answer is \(-1\).
In the code, we compute total_cover by OR-ing the coverage sets of all companies, and check:

• whether total_cover == full

Here full = (1 << M) - 1 represents the state where “all facilities are covered.”

Algorithm

1. Read the input.
2. For each security company, convert its coverable facility set into a bitmask cover[i].
3. Take the OR of all companies. If not all facilities can be covered, output -1 and terminate.
4. Initialize dp[mask] as “the minimum cost to achieve state mask.”
   • dp[0] = 0
   • All others are a sufficiently large value INF
5. For each company (C_i, cover[i]), for all mask:
   • nmask = mask | cover[i]
   • Update dp[nmask] = min(dp[nmask], dp[mask] + C_i)
6. The value at the final state full is the answer.

Example

For instance, suppose \(M=3\) and the current state is mask = 010 (only facility 2 is covered).
If a company can cover facilities 1 and 3, its mask is 101.

Contracting this company gives:

\[ 010 \mid 101 = 111 \]

This results in a state where all 3 facilities are covered.

Complexity

• Time complexity: \(O(NM + N2^M)\)
• Space complexity: \(O(2^M)\)

Since \(M \leq 18\), we have \(2^M \leq 262144\).
Therefore, even with \(N \leq 50\), the solution runs sufficiently fast.

Implementation Notes

• By converting each company’s coverable facilities into a bitmask, set union can be performed efficiently with just the | operation.

• INF should be set to a sufficiently large value. Since the maximum possible cost is at most \(50 \times 10^9\), using 10**30 is safe.

• In the code, the DP is stored as a 1-dimensional array.
  This is to save memory, and it works correctly without using a 2-dimensional DP.

• Although the same company cannot be used twice, this transition causes no issues.
  This is because if a company is used again after already being used, $\( (mask \mid b) \mid b = mask \mid b \)$ the state does not change, and only the cost increases.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)

    C = [next(it) for _ in range(N)]
    cover = []
    total_cover = 0

    for _ in range(N):
        mask = 0
        for j in range(M):
            if next(it):
                mask |= 1 << j
        cover.append(mask)
        total_cover |= mask

    full = (1 << M) - 1
    if total_cover != full:
        print(-1)
        return

    INF = 10**30
    dp = [INF] * (1 << M)
    dp[0] = 0

    for c, b in zip(C, cover):
        for mask in range(1 << M):
            cur = dp[mask]
            if cur == INF:
                continue
            nmask = mask | b
            nc = cur + c
            if nc < dp[nmask]:
                dp[nmask] = nc

    ans = dp[full]
    print(ans if ans < INF else -1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.