Skill Up

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.

Examples

Input

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

Output

120

Input

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

Output

-1

Input

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

Output

1067

inputFormat

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}

outputFormat

Output

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

Examples

Input

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

Output

120

Input

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

Output

-1

Input

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

Output

1067

样例

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

-1