题目描述

Takahashi, who is a novice in competitive programming, wants to learn $M$ algorithms. Initially, his understanding level of each of the $M$ algorithms is $0$.

Takahashi is visiting a bookstore, where he finds $N$ books on algorithms. The $i$-th book ($1\leq i\leq N$) is sold for $C_i$ yen (the currency of Japan). If he buys and reads it, his understanding level of the $j$-th algorithm will increase by $A_{i,j}$ for each $j$ ($1\leq j\leq M$). There is no other way to increase the understanding levels of the algorithms.

Takahashi's objective is to make his understanding levels of all the $M$ algorithms $X$ or higher. Determine whether this objective is achievable. If it is achievable, find the minimum amount of money needed to achieve it.

高桥是竞技编程的新手，他想学习 $M$ 种算法。最初，他对每种 $M$ 算法的了解程度是 $0$ 。

高桥访问了一家书店，在那里他找到了 $N$ 本关于算法的书籍。这本 $i$ （ $1\leq i\leq N$ ）售价为 $C_i$ 日元（日本货币）。如果他购买并阅读这本书，那么他对第 $j$ 种算法的理解水平每提高 $j$ ( $1\leq j\leq M$ )就会提高 $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$ 解释

购买第二本书和第三本书，使他对所有算法的理解程度达到或超过 $10$ ，成本尽可能低。

样例 $2$ 解释

购买所有书籍仍不足以使他对所有算法的理解水平达到 $10$ 或更高。