技能提升

题目描述

开始学习竞技编程的高桥君有 $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; 否则输出达成目标所需金额的最小值。

样例

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

120

购买第 $2, 3$ 本参考书,花 $120$ 日元就能让所有算法的理解度都达到 $10$ 以上,这是最小值。

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

-1

即使购买所有参考书,第 $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

数据范围

• 输入均为整数
• $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$