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$$