题目描述

​ 鱼与鸟是好朋友。

​ 但是由于鱼吃醋了，所以鸟只好擅自一个人去里世界寻找她失踪的老师冴月。

​ 鸟遇到了一个麻烦的 $\mathtt{glitch}$ ，这个 $\mathtt{glitch}$ 是一个巨大的矩阵，由有 $n$ 行 $m$ 列格子组成，每个格子上面存在一个整数 $a_{i,j}$

​ 鸟明白，自己一共可以选择至多 $k$ 个不同的格子，每次选择鸟可以获得这个格子所在行，所在列所覆盖的所有格子上的整数之和，作为鸟的分数。

​ 为了突破这个 $\mathtt{glitch}$ ，鸟需要获得尽可能多的分数。

​ 你能帮帮她吗，作为报答，醋鱼会更快地找到鸟。

输入格式

​ 第一行三个整数 $n,m,k$

​ 第 $2\sim n+1$ 行每行 $m$ 个整数，第 $i+1$ 行第 $j$ 个整数表示矩阵中第 $i$ 行第 $j$ 列的元素 $a_{i,j}$

输出格式

​ 一行一个整数 $s$ ，表示鸟能够获得的最大分数

输入输出样例

Input

4 4 2
-1 3 -7 12
9 -3 7 -1
-1 2 1 -9
-6 9 -3 -2

Output

41

数据范围与提示

对于 $100\%$ 的测试点，满足 $1\le n,m\le 3\times 10^3,|a_{i,j}|\le10^9,0\le k\le n\times m\le 10^6$

本题共有 $20$ 个测试点，每个测试点分值相等

样例解释：

​ 如下图，鸟选择第一行第二列获得分数 $15$ ，选择第二行第二列获得分数 $26$，可以得到最大分数 $41$