题目描述

小 Tyler 几乎通关了他最喜欢的电子游戏，只剩下与最终 Boss 的战斗。

在游戏过程中，他收集了许多不同的英雄。战斗开始前，这些英雄排成一个 $n$ 行 $m$ 列的表格。第 $i$ 行第 $j$ 列英雄的伤害值为 $a_{i,j}$。

战斗开始前，他必须恰好献祭 $k$ 个英雄。所有献祭完成后，每个被献祭的位置都会出现一个魔像。这个魔像的伤害值等于：献祭之后，该位置所在的行和列中剩余英雄伤害值之和。

之后，场上所有角色，包括魔像，都会各攻击一次。

Tyler 还不知道最终 Boss 有多强，所以他想知道自己最多能造成多少总伤害。请你帮他计算。

输入格式

第一行输入三个整数 $n,m,k$，表示表格大小和必须献祭的英雄数量。

接下来 $n$ 行，每行输入 $m$ 个整数。第 $i$ 行第 $j$ 个数为 $a_{i,j}$，表示对应英雄的伤害值。

输出格式

输出一个整数，表示最优选择献祭英雄后，所有角色能造成的最大总伤害。

数据范围

对于所有测试数据：

样例 1

输入

2 3 1
0 6 2
2 3 6

输出

30

样例 2

输入

2 4 2
4 4 1 1
2 2 9 9

输出

72

样例 3

输入

2 2 3
12 6
3 9

输出

36

样例解释

样例 1 中：

• 若献祭位置 $(1,1)$ 的英雄，总伤害为 $29$；
• 若献祭位置 $(2,2)$ 的英雄，总伤害为 $30$。

样例 2 中：

若献祭位置 $(2,1)$ 和 $(2,2)$ 的英雄，则这两个位置上的魔像伤害值都为 $4+9+9=22$，最终表格中所有角色的总伤害为 $72$。

评分方式

测试点分为 7 组。只有通过某一组的全部测试，并通过该组依赖的必要组，才能获得该组分数。注意，部分测试组不要求通过样例组。Offline 检查表示该组结果只会在比赛结束后公布。