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