贪心 · 例5-矩阵消除游戏
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}本题转译自 [牛客练习赛58] 矩阵消除游戏 。
\hspace{15pt}牛妹在一个 n 行 m 列的矩阵上玩一个名为矩阵消除的游戏，矩阵的第 i 行第 j 列的单元格的权值记为 a_{i,j} 。
\hspace{15pt}牛妹一共会进行 k 个回合的游戏，在每个回合，牛妹可以选择一行（或者选择一列），牛妹的分数会加上这一行（或者这一列）中的所有单元格的权值的和，随后，将这一行（或者这一列）的所有单元格中的权值变为 0 。换句话来说，每一个单元格中的权值至多计算一次。
\hspace{15pt}牛妹想最大化她的得分，请你帮助她做出最优决策！

输入描述:

\hspace{15pt}第一行输入三个整数 n, m ,k \left( 1 \leqq n, m \leqq 15;\ 1 \leqq k \leqq n \times m \right) 代表矩阵的行数、矩阵的列数、牛妹游玩的回合数。
\hspace{15pt}此后 n 行，第 i 行输入 m 个整数 a_{i,1},a_{i,2},\cdots,a_{i,m} \left( 1 \leqq a_{i,j} \leqq 10^6 \right) 代表矩阵中每一个单元格的权值。

输出描述:

\hspace{15pt}在一行上输出一个整数，代表牛妹可以获得的最大得分。
示例1

输入

复制 
3 4 2
10 10 10 10
1 1 1 10
1 1 1 10

输出

复制 
60

说明

\hspace{15pt}在这个样例中，最优的选取策略如下：
\hspace{23pt}\bullet\,第一回合选择第一行，得到 10 + 10 + 10 + 10 = 40 分；此时，矩阵变为 \begin{matrix}<br />{\color{orange}{0}} & {\color{orange}{0}} & {\color{orange}{0}} & {\color{orange}{0}} \\<br />1 & 1 & 1 & 10 \\<br />1 & 1 & 1 & 10 \\<br />\end{matrix} ；
\hspace{23pt}\bullet\,第二回合选择第四列，得到 0 + 10 + 10 = 20 分，总得分为 40 + 20 = 60 分。
示例2

输入

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

输出

复制 
414

备注: