问题

Takahashi 是一个刚开始进行竞技编程的新手，他想要学习 $M$ 种算法。一开始，他对这 $M$ 种算法的“理解水平”都是 $0$。

Takahashi 正在书店里游览，发现有 $N$ 本关于算法的书籍。第 $i$ 本书（$1\leq i\leq N$）售价为 $C_i$ 日元（日本的货币单位）。如果他购买并阅读这本书，他对第 $j$ 种算法的理解水平将会增加 $A_{i,j}$，其中 $j$ 的取值范围为 $1\leq j\leq M$。没有其他方法可以提高算法的理解水平。

Takahashi 的目标是使他对这 $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；否则，输出实现目标所需的最小金额。

示例输入 1

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

示例输出 1

120

购买第二本书和第三本书的最低成本就可以使得他对所有算法的理解水平达到 $10$ 或更高。

示例输入 2

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

示例输出 2

-1

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

示例输入 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