Product Development

题目描述

AtCoder 公司计划开发一款产品。该产品有 $K$ 个参数，当前所有参数的值均为零。公司目标是将所有参数的值提高到至少 $P$。 有 $N$ 个开发方案。执行第 $i$ 个开发方案（$1 \le i \le N$）会以代价 $C_i$ 将第 $j$ 个参数的值增加 $A_{i,j}$，对所有满足 $1 \le j \le K$ 的整数 $j$ 均适用。 每个开发方案最多只能执行一次。判断公司是否能够实现目标，如果能，求实现目标所需的最小总代价。

输入格式

输入按下述格式从标准输入给出： $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 公司可以实现目标，输出实现目标所需的最小总代价；否则，输出 $-1$。

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

9

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

-1

提示

$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)$ 所有输入值均为整数。如果你执行第 1、3、4 个开发方案，则各参数将为 $3+2+0=5,0+4+1=5,2+0+4=6$，均至少为 $5$，因此目标达成。在这种情况下总代价为 $5 + 3 + 1 = 9$。 不可能以总代价不超过 $8$ 达成目标。因此，答案为 $9$。
无论如何都无法达成目标。因此，输出 $-1$。

标签: AtCoder|abc322E

来源

AtCoder|abc322E