Hugo has recently bought a plot of land with $N$ rows and $M$ columns and has planted a flower on every tile. The flower on the top-left tile is denoted as $(1, 1)$.
The flower of the $i$-th row and $j$-th column on the plot of land has a beauty value $A[i][j]$.

Hugo intends to install $K$ sprinklers, where the sprinkler on the $y$th row and $x$th column increases his happiness by $(\sum_{i=1}^N A[i][x]) + (\sum_{i=1}^M A[y][i])$.
He wishes that each sprinkler occupies a unique row and column in order to not damage other sprinklers.

Help Hugo find the maximum happiness he can obtain.

Input

The first line contains three integers $N$, $M$, $K$.
The following $N$ lines contains $M$ integers, where the $j$-th integer on the $i+1$-th line is $A[i][j]$, describing the beauty value of each tile.

Output

The output consists of a single integer, the maximum happiness after installing $K$ sprinklers.

Constraints

For all subtasks:

• $1 \le N,M \le 1000$
• $1 \le K \le min(N, M)$
• $A[i][j] \le 10^9$

Subtask 1 (20%): $K = 1$
Subtask 2 (40%): $K,N,M \le 100$
Subtask 3 (40%): No additional constraints