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 \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 翻译