Skill Up

题目描述

输入格式

输入以标准输入按以下格式给出： $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$；否则，输出达到目标所需的最少费用。

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

120

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

-1

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

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$Takahashi 是一名刚接触竞赛编程的新手，想要学习 $M$ 个算法。 起初，他对这 $M$ 个算法的理解度均为 $0$。 Takahashi 逛书店时发现了 $N$ 本算法相关的书。 第 $i$ 本书（$1\leq i\leq N$）的售价为 $C_i$ 日元。如果他购买并阅读该书，他对第 $j$ 个算法的理解度将分别增加 $A_{i,j}$（对所有 $j$，$1\leq j\leq M$）。 没有其他方式可以提高算法的理解度。 Takahashi 的目标是使他对这 $M$ 个算法的理解度都达到 $X$ 或更高。判断该目标是否可实现。如果可实现，求出实现该目标所需的最少费用。购买第 2 本和第 3 本书可以使他对所有算法的理解度都达到至少 $10$，且费用为最少。
购买所有书仍然不足以使他对所有算法的理解度都达到 $10$。

标签: AtCoder|abc167C

来源

AtCoder|abc167C