题目描述

强哥刚接触编程竞赛，他有 $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$

样例解释 1

如果购买第 $2$ 本和第 $3$ 本教材，那么只需花费 $120$ 元就能让所有算法的熟练度都达到 $10$ 以上，这也是所需的最小金额。

样例解释 2

即使购买所有教材，第 $1$ 个算法的熟练度也无法达到 $10$，因此目标无法实现。