I. Wigz
time limit per test
6 seconds
memory limit per test
256 megabytes
input
wigz.in
output
standard output

"Wigz is here" said Badran.

Omda wants to make a feature with Wigz. However, Wigz has a condition for them to make a feat.

Omda needs to pick some Wigz for Wigz to wear.

Given a carton of Wigz represented by a grid of $$$N$$$ rows and $$$M$$$ columns where the Wig at row $$$i$$$ and column $$$j$$$ has a value $$$G_{i,j}$$$.

Omda has an integer $$$K$$$ he needs to choose a set of rows $$$R$$$ and a set of columns $$$C$$$ such that $$$|R| + |C| \leq K$$$ and $$$ \sum_{i \in R \space or \space j \in C} G_{i,j} $$$ is maximum.

Can you get help Omda to get the maximum sum for the above problem?

Input

The first line contains the number of test cases $$$T$$$ $$$(1 \leq T \leq 50)$$$.

The first line of each test case contains $$$3$$$ integers $$$N$$$, $$$M$$$, and $$$K$$$ $$$(1 \leq N \times M \leq 500) (1 \leq K \leq N+M)$$$.

Each of the next $$$N$$$ lines contains $$$M$$$ integers $$$A_{ij}(0 \leq A_{ij} \leq 1000)$$$.

It is guaranteed that the sum of $$$N \times M$$$ over all test cases doesn't exceed $$$500$$$

Output

For each test case, print one integer which is the answer for this problem.

Example
Input
1
3 3 2
1 3 1
2 4 1
3 3 2
Output
16