← 返回题目列表

AtCoder · awc0050_e

E. 最低成本保护计划

中文机器翻译题面 查看原题

分数: 433 分

问题陈述

高桥是负责的经理 M 设施。为了给所有设施分配安全保障,他计划选择一些设施并与其签订合同。 N 保安公司。

各保安公司 i (1 \leq i \leq N) 有合同成本 C_i。另外,还有一个值 给出的 E_{i,j} 表明是否有保安公司 i 可以看守设施 j。当 E_{i,j} = 1,保安公司 i 可以看守设施 j,当 E_{i,j} = 0,它不能。

高桥选择 1 或更多公司 N 与之签订合同的公司。但是,同一家公司不能被多次选择。让 S 是选定的保安公司的集合。对于每个设施 j (1 \leq j \leq M),其中必须至少有一家公司 S 可以守护设施 j.

在所有的选择方式中 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}
  • 第一行包含保安公司数量 N 和设施数量 M,用空格分隔。
  • 第二行包含合同成本 每个保安公司的 C_1, C_2, \ldots, C_N ,以空格分隔。
  • 从第 3 行到 (N+2)第行,每行包含 E_{i,1}, E_{i,2}, \ldots, E_{i,M} 以空格分隔,表示是否为保安公司 i (1 \leq i \leq N)可以守卫各个设施。

输出

一行输出在所有选择能够保护所有设施的保安公司的方式中最小的总合同成本。如果不存在有效选择,则输出 -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