AT_abc322_e [ABC322E] Product Development

题目描述

AtCoder 社正在开发一款新产品。该产品有 $K$ 个参数，目前所有参数的值均为 $0$。AtCoder 社的目标是让所有参数的值都达到 $P$ 以上。

现在有 $N$ 个开发方案。执行第 $i$ 个开发方案后，对于每个 $1 \leq j \leq K$，第 $j$ 个参数会增加 $A_{i,j}$，但执行该开发方案需要花费 $C_i$ 的成本。

同一个开发方案不能执行一次以上。请判断 AtCoder 社能否达成目标，如果可以，求出达成目标所需的最小总成本。

输入格式

输入以如下格式从标准输入给出。

$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。

输入输出样例 #1

输入 #1

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

输出 #1

9

输入输出样例 #2

输入 #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 \leq N \leq 100$
• $1 \leq K, P \leq 5$
• $0 \leq A_{i,j} \leq P\ (1 \leq i \leq N, 1 \leq j \leq K)$
• $1 \leq C_i \leq 10^9\ (1 \leq i \leq N)$
• 所有输入均为整数

样例解释 1

如果执行第 $1$、$3$、$4$ 个开发方案，则各参数分别为 $3+2+0=5, 0+4+1=5, 2+0+4=6$，均达到 $5$ 以上，因此目标可以达成。此时总成本为 $5+3+1=9$。无法以总成本 $8$ 或更低达成目标，因此答案为 $9$。

样例解释 2

无论如何都无法达成目标，因此输出 -1。

由 ChatGPT 4.1 翻译