← 返回题目列表

AtCoder · abc322_e

H. 产品开发

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

分数: 475 点

问题陈述

AtCoder Inc. 正计划开发一种产品。该产品有 K 参数,其值当前全部为零。该公司的目标是将所有参数值至少提高到 P.

有 N 发展计划。执行 i第3期发展计划(1 \le i \le N) 增加了 j-第参数 A_{i,j} 对于每个整数 j 这样 1 \le j \le K,代价是 C_i.

开发计划不能执行多次。确定公司是否能够实现其目标,如果可以,求出实现目标所需的最小总成本。

约束

  • 1 \le N \le 100
  • 1 \le K,P \le 5
  • 0 \le A_{i,j} \le P(1 \le i \le N,1 \le j \le K)
  • 1 \le C_i \le 10^9(1 \le i \le N)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N K P
C_1 A_{1,1} A_{1,2} \dots A_{1,K}
C_2 A_{2,1} A_{2,2} \dots A_{2,K}
\dots
C_N A_{N,1} A_{N,2} \dots A_{N,K}

输出

如果AtCoder Inc.能够实现其目标,请打印实现该目标所需的最低总成本;否则,打印 -1.


示例输入 1

4 3 5
5 3 0 2
3 1 2 3
3 2 4 0
1 0 1 4

示例输出 1

9

如果执行第一个、第三个、第四个开发计划,每个参数都会 3+2+0=5,0+4+1=5,2+0+4=6,所有这些至少 5,这样目的就达到了。这种情况下的总成本是 5 + 3 + 1 = 9.

总成本不可能达到 8 或更少。因此,答案是 9.


示例输入 2

7 3 5
85 1 0 1
37 1 1 0
38 2 0 0
45 0 2 2
67 1 1 0
12 2 2 0
94 2 2 1

示例输出 2

-1

无论你做什么都无法实现目标。因此,打印 -1.