There are $N$ shops each selling $M$ different kinds of items. The $i$^th store sells the $j$^th item for $C$_ij dollars. You decide to buy $M-1$ different type of items from each shop. If you want to have all $M$ kinds of items in your shopping bag, then what is the minimum amount that you need to spend?

Input format

• First line: An integer $T$ representing the number of test cases
• First line of every test case: Two integers $N$ and $M$ representing the number of submissions 
• Next $N$ lines:  $M$ space-separated integers representing the cost of $i$^th ($i \leq N$) item in the $j$^th ($j \leq M$) store - $C$_ij

Output format

For each test case, print the minimum cost required as described in the problem statement in a new line. Print -1 if it is not possible to have all $M$ different kinds of items.

Constraints

     $1$ $\leq$  $T$  $\leq$  $10$

     $1$ $\leq$  $N$ $\leq$  $1000$

     $1$ $\leq$  $M$ $\leq$  $1000$

     $1$ $\leq$  $C$_ij $\leq$  $10^9$