当前没有测试数据。

2.选数游戏

题目描述

给定$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}$以内。

样例

1 5 3
1 2 3 4 5

6