Ram wants to upsolve problems so that he becomes better in competitive programming. To do so he knows that he needs to know M concepts. He picks up N problems. He knows that he needs to devote t_i amount of time to finish the i-th problem. When he solves the i-th problem his understanding in the j-th concept increases by a_i,j. He wants his understanding of all of the concepts to be atleast X. Help him to find out if this is possible or not and if possible find the minimum time required for him to achieve this.

Constraints:

1<=N, M<=12

1<=X<=10¹²

1<=t_i<=10⁹

0<=A_i,j<=10⁹

Input:

The first line of input consists of 3 integers N, M and X

This is followed by N lines each line consist of M+1 integers in the format t_i  A_I,1  A_{i, 2} ... A_{i, M}

Output:

If impossible then print -1 else print the minimum time required to achieve the required understanding in the concepts.