题目描述
给定 $n$ 行 $m$ 列的矩阵，每一列的所有数数值相同，要求从第一列的某个数选起选出 $k$ 个数。每次在上一个数的基础上向上下左右四个方向移动，在某一列的第一行向上移动可到达该列的最后一行。被选过的数不可重复选取，求选出的数的最大和。
输入
第一行三个数 $n,m,k$， 含义如题。
接下来 $m$ 个数表示矩阵的第一行。
输出
输出一行一个数表示最大和。
样例输入输出
提示
对于 $20\%$ 的数据，$1 \leq k \leq 12$
对于 $70\%$ 的数据，$1 \leq n,m \leq 1000$。
对于 $100\%$ 的数据，$1\leq n,m \leq 10^6$，$1 \leq k \leq nm$，数值在 $10^6$ 以内。