A wall in your room can be considered as a two dimensional matrix of \(n\) rows and \(m\) columns.

Initally, the wall is painted white and repainting any cell \((i,\ j)\) has a cost \(a_{ij}\). You want to paint a HackerEarth logo of dimension two rows and \(k\) columns \((2 \times K)\) in the minimum cost possible.The logo can be painted either horizontally or vertically. You are required to determine the minimum cost you must pay to get the wall painted.

If there is no possible way to get the wall painted, then print \(-1\). Otherwise, print the minimum cost.

Note: The logo can be painted in form of \(2 \times K\) or \(K \times 2\) that provides you the minimum cost.

Input forrmat

• First line: A single integer \(T\) denoting the number of test cases
• For each test case:
  • First line: Three integers \(n,\ m,\ and\ k\)
  • Next \(n\) lines contains \(m\) space-separated numbers denoting the cost of repainting any cells

Output format

For each test case, print the minimum cost to repaint the wall. If it is not possible to repaint a wall, then print \(-1\).

Constraints

\(1\le T\le 3\\ 1\le n,\ m,\ k\le 1000\\ 0\le a_{ij}\le 100000\ for\ all\ i\ from\ [1,\ n]\ and\ for\ all\ j\ from\ [1,\ m]\\ \)