You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目信息

时间限制：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$；