AT_abc167_c [ABC167C] Skill Up

题目描述

高桥君刚开始学习竞赛编程，他有 $M$ 个想要学习的算法。最初，每个算法的理解度都是 $0$。

有一天，高桥君去书店，发现有 $N$ 本参考书在售。第 $i$ 本参考书（$1\leq i\leq N$）售价为 $C_i$ 日元，购买并阅读后，对于每个 $j$（$1\leq j\leq M$），第 $j$ 个算法的理解度会提升 $A_{i,j}$。除此之外，没有其他方式可以提升理解度。

高桥君的目标是让所有 $M$ 个算法的理解度都达到至少 $X$。请判断高桥君是否有可能达成目标，如果可以，请计算达成目标所需的最小金额。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$ $X$
$C_1$ $A_{1,1}$ $A_{1,2}$ $\cdots$ $A_{1,M}$
$C_2$ $A_{2,1}$ $A_{2,2}$ $\cdots$ $A_{2,M}$
$\vdots$
$C_N$ $A_{N,1}$ $A_{N,2}$ $\cdots$ $A_{N,M}$

输出格式

如果高桥君无法达成目标，输出 -1；否则，输出达成目标所需的最小金额。

输入输出样例 #1

输入 #1

3 3 10
60 2 2 4
70 8 7 9
50 2 3 9

输出 #1

120

输入输出样例 #2

输入 #2

3 3 10
100 3 1 4
100 1 5 9
100 2 6 5

输出 #2

-1

输入输出样例 #3

输入 #3

8 5 22
100 3 7 5 3 1
164 4 5 2 7 8
334 7 2 7 2 9
234 4 7 2 8 2
541 5 4 3 3 6
235 4 8 6 9 7
394 3 6 1 6 2
872 8 4 3 7 2

输出 #3

1067

说明/提示

限制条件

• 所有输入均为整数。
• $1\leq N,\ M\leq 12$
• $1\leq X\leq 10^5$
• $1\leq C_i\leq 10^5$
• $0\leq A_{i,j}\leq 10^5$

样例解释 1

如果购买第 $2$ 和第 $3$ 本参考书，则只需花费 $120$ 日元就能让所有算法的理解度都达到 $10$ 以上，这也是所需的最小金额。

样例解释 2

即使购买所有参考书，第 $1$ 个算法的理解度也无法达到 $10$。

由 ChatGPT 4.1 翻译