Problem

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.

Constraints

• All values in input are integers.
• $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$

Input

Input is given from Standard Input in the following format:

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}

Output

If the objective is not achievable, print -1; otherwise, print the minimum amount of money needed to achieve it.