T3. 爱上火车

题目信息

时间限制：4s

空间限制：512MB

输入文件：division.in

输出文件：division.out

测试点数量：20

题目类型：传统题

测评方式：文本比较，忽略行末空格和文末空白

题目描述

一条单向环形铁路上有 $k$ 个城市，分别标号为 $0,1,\dots ,k-1$。其中，第 $i$ 个城市可以乘火车到达第 $(i+1)\bmod k$ 个城市。城市的个数很少。

LCR 想要在这些城市中进行为期 $n$ 天的观光。第 $1$ 天清晨，LCR 从自家坐火车到达 $0$ 号城市出发开始观光。每天白天，每个城市都会举行一些特定的活动，如果第 $t$ 天的白天 LCR 在 $i$ 号城市里，那么她会获得 $a_{i,t} (0\le i< k, 1\le t\le n)$ 的效用，效用是一个非负整数。除了最后一天之外，每天傍晚，LCR 可以选择留在当前城市，或者乘火车移动到下一个相邻城市（从城市 $i$ 移动到城市 $(i+1)\bmod k$）。整个观光旅程的总效用为 $n$ 个白天的效用之和。

LCR 希望她在旅途中恰好坐了特定次数的火车（从家到 $0$ 号城市的一次也算）。因此，她会询问 $q$ 次，每次给出一个正整数 $m$，你需要帮她计算出在恰好坐了 $m$ 次火车的情况下，观光旅程总效用可能的最大值。

输入格式

第一行三个正整数 $n,k,q$ 表示天数、城市个数和询问次数。

接下来 $k$ 行，每行 $n$ 个非负整数表示一个城市每天的效用。其中第 $i$ 行第 $j$ 个数为 $a_{i-1,j}$。

接下来 $q$ 行，每行一个正整数 $m$ 表示询问恰好坐 $m$ 次火车情况下最大可能的总效用。

输出格式

输出 $q$ 行，其中第 $i$ 行一个非负整数表示第 $i$ 次询问的坐火车次数对应的最大可能的总效用。

注意，最开始从家到 $0$ 号城市的火车也算一次，但最后一天（第 $n$ 天）傍晚不能再坐火车。

样例

样例输入 1

10 3 1
9 1 2 3 4 5 6 7 8 0
0 5 8 7 4 4 2 1 3 9
2 3 1 5 6 1 5 1 5 6
5

样例输出 1

70

样例解释 1

(9) 1  2  3  4 (5)(6)(7)(8) 0
 0 (5)(8)(7) 4  4  2  1  3 (9)
 2  3  1  5 (6) 1  5  1  5  6

最优方案为参与括号内的活动。容易证明这是最优的，因为每一天都参加了那天效用最大的活动。注意最后一天（第 $n$ 天）傍晚不能坐火车。

样例输入 2

6 2 6
9 2 3 3 5 2
6 5 4 6 6 4
1
2
3
4
5
6

样例输出 2

24
34
32
33
31
32

样例 3、4、5、6

见附加文件。

数据范围与提示

对于 $100\%$ 的数据，$1\le m,q\le n\le 10^5, 2\le k\le 5, k\le n, 0\le a_{i,j}\le 10^9$。

一共有 $20$ 个测试点。部分测试点满足的性质如下：

• $1$ 号：$n\le 20, a_{i,j}\le 10^6$；
• $2,3$ 号：$n\le 500, a_{i,j}\le 10^6$；
• $4,5$ 号：$n\le 3000$；
• $6,7,8,9,10$ 号：$k=2$；
• $9,10,11,12,13,14$ 号：$q\le 5$；