题目描述

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

输入格式

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

输出格式

在一行上输出一个整数，代表jiangys可以获得的最大得分。

输入样例#1

3 4 2
10 10 10 10
1 1 1 10
1 1 1 10

输出样例#1

60

输入样例#2

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

输出样例#2

414

说明/提示

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