C - 提高技能

得分：300 分

问题

高桥是竞技规划的新手，想学习 $M$ 种算法。 起初，他对这 $M$ 种算法的理解水平都是 $0$。

高桥去书店，在那里找到了 $N$ 本有关算法的书籍。 第 $i$ 本书（$1\leq i\leq N$）的价格为 $C_i$ 日元（日本的货币单位）。如果他买下并阅读此书，对于第 $j$ 种算法，他的理解水平会增加 $A_{i,j}$（$1\leq j\leq M$）。 没有其他方式可以提高这些算法的理解水平。

高桥的目标是让他对所有 $M$ 种算法的理解水平达到或超过 $X$。要判断这个目标是否可以实现。如果可以实现，求出所需的最小金额。

约束

• 输入中的所有值都是整数。
• $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$

输入

从标准输入中按以下格式输入：

$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

购买第二本和第三本书使他对所有算法的理解水平都达到了 $10$ 或更高，且所花费的金额是最少的。

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

-1

即使购买全部书籍，他对所有算法的理解水平仍然达不到 $10$ 或更高。

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