题目描述

在今天的体育课上，老师和同学们做了一个有趣的游戏，老师拿出了一堆硬币，选出一个 “挑战者”出列，很不幸，今天小 $C$ 成了其中一个“挑战者”， 然后老师让其他的同学排 $n$ 行 $m$ 列，然后现在给第 $i$ 行第 $j$ 列的同学发 $a_{i,j}$ 个硬币，然后让“挑战者”进行 $k$ 个回合的游戏，每个回合，“挑战者”可以选择一行或一列的同学拿走他们的硬币，在 $k$ 个回合拿走的硬币总数就是“挑战者”整个游戏的得分，现在每一个“挑战者”都想要在 $k$ 个回合结束后使得自己的分数 $score$ 最大（每个”挑战者“的队伍会进行变换，硬币也会重新分配），假如你是”挑战者“，怎样才能使得自己的分数最大呢？

输入格式

第一行三个整数 $n,m,k$，表示每次游戏队伍的行，列和游戏的回合数

接下来的 $n$ 行每行 $m$ 个整数，表示队伍中每个同学手上的硬币数 $a_{i,j}$

输出格式

输出 $1$ 行，每行表示该挑战者能获得的最大分数 $score$。

样例#1

输入样例#1

3 3 2
101 1 102
1 202 1
100 8 100

输出样例#1

414

提示

数据与模的规定

$1 \leq n,m \leq 12$ ,

$1 \leq k \leq n\times m$,

$1 \leq a_{i,j} \leq 10^5$