Problem Description

Takahashi, who has just started competitive programming, has $M$ algorithms he wants to learn. Initially, his understanding level for each algorithm is $0$.

When Takahashi visits a bookstore, he finds $N$ reference books for sale. The $i$-th book ($1 \leq i \leq N$) is sold for $C_i$ yen. By purchasing and reading it, his understanding level for each $j$ ($1 \leq j \leq M$) of the $j$-th algorithm increases by $A_{i,j}$. There is no other way to increase his understanding level.

Takahashi's goal is to have an understanding level of at least $X$ for all $M$ algorithms. Determine if it is possible for Takahashi to achieve his goal and, if possible, calculate the minimum amount of money needed to achieve it.

Input Format

The input is given from the 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 Format

If Takahashi cannot achieve his goal, output -1. Otherwise, output the minimum amount of money needed to achieve the goal.

Sample Input and Output

Sample Input #1

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

Sample Output #1

120

Sample Input #2

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

Sample Output #2

-1

Sample Input #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

Sample Output #3

1067

Notes/Hints

Constraints

• All inputs 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$

Sample Explanation 1

By purchasing the 2nd and 3rd books, Takahashi can achieve an understanding level of at least $10$ for all algorithms for $120$ yen, which is the minimum cost.

Sample Explanation 2

Even if Takahashi purchases all the books, he cannot reach an understanding level of $10$ for the first algorithm.

见题面 Input 部分

见题面 Output 部分