分数: 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.