[ABC167C] Skill Up

题面翻译

小高是一个编程竞赛新手，他想学习 M 种算法。最初，他对每种算法的理解程度都是0。

小高在一家书店里，那里有 N 本关于算法的书。第 $i(1\le i \le N)$本书的售价是$C_i$元。如果他购买并阅读这本书，他对第$j$ 种算法的理解程度将增加 $A_{i,j}$（对于每个$j,1\le j \le 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；否则，输出实现目标所需的最小金额。

题目描述

競技プログラミングを始めた高橋くんは、学びたいアルゴリズムが $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$

Sample Explanation 1

购买第二本和第三本书的话，120元就可以使他对所有算法的理解程度达到或超过 10，这是可能的最小花费。

Sample Explanation 2

即使购买所有的书，也不足以使他对所有算法的理解程度达到或超过 10。