E - 最小コスト警備計画 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 433 点

問題文

高橋君は M 箇所の施設を管理する責任者です。すべての施設に警備をつけるため、N 社の警備会社の中からいくつかを選んで契約しようとしています。

各警備会社 i（1 \leq i \leq N）には契約費用 C_i が定められています。また、警備会社 i が施設 j を警備できるかどうかを表す値 E_{i,j} が与えられます。E_{i,j} = 1 のとき警備会社 i は施設 j を警備でき、E_{i,j} = 0 のとき警備できません。

高橋君は N 社の中から 1 社以上を選んで契約します。ただし、同じ会社を重複して選ぶことはできません。選んだ警備会社の集合を S としたとき、すべての施設 j（1 \leq j \leq M）に対して、S の中に施設 j を警備できる会社が少なくとも 1 つ存在しなければなりません。

この条件を満たす S の選び方のうち、契約費用の合計 \displaystyle\sum_{i \in S} C_i の最小値を求めてください。条件を満たす選び方が存在しない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 50
  • 1 \leq M \leq 18
  • 1 \leq C_i \leq 10^9（1 \leq i \leq N）
  • E_{i,j} \in \{0, 1\}（1 \leq i \leq N, 1 \leq j \leq M）
  • 入力はすべて整数である

入力

N M
C_1 C_2 \ldots C_N
E_{1,1} E_{1,2} \ldots E_{1,M}
E_{2,1} E_{2,2} \ldots E_{2,M}
\vdots
E_{N,1} E_{N,2} \ldots E_{N,M}
  • 1 行目には、警備会社の数 N と施設の数 M がスペース区切りで与えられる。
  • 2 行目には、各警備会社の契約費用 C_1, C_2, \ldots, C_N がスペース区切りで与えられる。
  • 3 行目から N+2 行目までの各行には、警備会社 i（1 \leq i \leq N）が各施設を警備できるかどうかを表す E_{i,1}, E_{i,2}, \ldots, E_{i,M} がスペース区切りで与えられる。

出力

すべての施設を警備できる警備会社の選び方における契約費用の合計の最小値を 1 行で出力せよ。条件を満たす選び方が存在しない場合は -1 を出力せよ。

入力例 1

4 3
4 6 5 11
1 1 0
0 1 1
1 0 0
1 1 1

出力例 1

10

入力例 2

4 4
5 2 7 4
1 0 0 0
0 1 1 0
1 0 1 0
0 1 0 0

出力例 2

-1

入力例 3

7 6
8 5 6 7 4 9 3
1 0 1 0 0 0
0 1 0 1 0 0
0 0 1 1 1 0
1 1 0 0 0 1
0 0 0 1 0 1
1 0 0 0 1 0
0 1 0 0 1 1

出力例 3

13

入力例 4

12 10
14 9 20 11 8 7 13 6 15 10 12 5
1 0 1 0 0 1 0 0 0 0
0 1 0 1 0 0 1 0 0 0
1 1 0 0 1 0 0 1 0 0
0 0 1 1 0 1 0 0 1 0
1 0 0 0 1 0 1 0 0 1
0 1 1 0 0 0 0 1 1 0
0 0 0 1 1 1 0 0 0 1
1 0 0 0 0 0 1 1 0 0
0 1 0 1 0 1 0 1 0 1
0 0 1 0 1 0 1 0 1 0
1 0 0 1 0 0 1 0 1 0
0 1 0 0 1 0 0 1 0 1

出力例 4

22

入力例 5

1 1
1000000000
1

出力例 5

1000000000

Score : 433 pts

Problem Statement

Takahashi is the manager responsible for M facilities. To assign security to all facilities, he plans to select and contract with some of the N security companies.

Each security company i (1 \leq i \leq N) has a contract cost C_i. Additionally, a value E_{i,j} is given that indicates whether security company i can guard facility j. When E_{i,j} = 1, security company i can guard facility j, and when E_{i,j} = 0, it cannot.

Takahashi selects 1 or more companies from the N companies to contract with. However, the same company cannot be selected more than once. Let S be the set of selected security companies. For every facility j (1 \leq j \leq M), there must be at least one company in S that can guard facility j.

Among all ways of choosing S that satisfy this condition, find the minimum total contract cost \displaystyle\sum_{i \in S} C_i. If no valid selection exists, output -1.

Constraints

  • 1 \leq N \leq 50
  • 1 \leq M \leq 18
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
  • E_{i,j} \in \{0, 1\} (1 \leq i \leq N, 1 \leq j \leq M)
  • All input values are integers

Input

N M
C_1 C_2 \ldots C_N
E_{1,1} E_{1,2} \ldots E_{1,M}
E_{2,1} E_{2,2} \ldots E_{2,M}
\vdots
E_{N,1} E_{N,2} \ldots E_{N,M}
  • The first line contains the number of security companies N and the number of facilities M, separated by a space.
  • The second line contains the contract costs C_1, C_2, \ldots, C_N of each security company, separated by spaces.
  • From the 3rd line to the (N+2)-th line, each line contains E_{i,1}, E_{i,2}, \ldots, E_{i,M} separated by spaces, indicating whether security company i (1 \leq i \leq N) can guard each facility.

Output

Output in one line the minimum total contract cost among all ways of selecting security companies that can guard all facilities. If no valid selection exists, output -1.

Sample Input 1

4 3
4 6 5 11
1 1 0
0 1 1
1 0 0
1 1 1

Sample Output 1

10

Sample Input 2

4 4
5 2 7 4
1 0 0 0
0 1 1 0
1 0 1 0
0 1 0 0

Sample Output 2

-1

Sample Input 3

7 6
8 5 6 7 4 9 3
1 0 1 0 0 0
0 1 0 1 0 0
0 0 1 1 1 0
1 1 0 0 0 1
0 0 0 1 0 1
1 0 0 0 1 0
0 1 0 0 1 1

Sample Output 3

13

Sample Input 4

12 10
14 9 20 11 8 7 13 6 15 10 12 5
1 0 1 0 0 1 0 0 0 0
0 1 0 1 0 0 1 0 0 0
1 1 0 0 1 0 0 1 0 0
0 0 1 1 0 1 0 0 1 0
1 0 0 0 1 0 1 0 0 1
0 1 1 0 0 0 0 1 1 0
0 0 0 1 1 1 0 0 0 1
1 0 0 0 0 0 1 1 0 0
0 1 0 1 0 1 0 1 0 1
0 0 1 0 1 0 1 0 1 0
1 0 0 1 0 0 1 0 1 0
0 1 0 0 1 0 0 1 0 1

Sample Output 4

22

Sample Input 5

1 1
1000000000
1

Sample Output 5

1000000000