← 返回题目列表

Codeforces · 2000/E

E. 为大猩猩拍摄照片

中文机器翻译题面 查看原题

你真的很喜欢大猩猩,所以你决定为它们组织一次拍摄。大猩猩生活在丛林中。丛林被表示为由 $$$n$$$ 行和 $$$m$$$ 列组成的网格。 $$$w$$$ 大猩猩同意参加拍摄,索引为 $$$i$$$ ($$$1 \le i \le w$$$) 的大猩猩身高为 $$$a_i$$$。您希望将所有大猩猩放置在网格的单元格中,以便每个单元格中不超过一只大猩猩。

排列的眼镜度等于边长为 $$$k$$$ 的网格中所有子方格眼镜度的总和。

子正方形的奇观等于其中大猩猩的高度之和。

从所有合适的排列中,选择具有最大奇观的排列。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。

测试用例的描述如下。

第一行包含整数 $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$, $$$1 \le n \cdot m \le 2 \cdot 10^5$$$, $$$1 \le k \le \min(n, m)$$$) - 维度网格的长度和正方形的边长。

第二行包含一个整数 $$$w$$$ ($$$1 \le w \le n \cdot m$$$) — 大猩猩的数量。

第三行包含 $$$w$$$ 整数 $$$a_1, a_2, \ldots, a_w$$$ ($$$1 \le a_i \le 10^9$$$) — 大猩猩的高度。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$2 \cdot 10^5$$$。同样的保证适用于 $$$w$$$。

输出

对于每个测试用例,输出一个整数 - 合适排列的最大景观。

示例

输入 #1

5
3 4 2
9
1 1 1 1 1 1 1 1 1
2 1 1
2
5 7
20 15 7
9
4 1 4 5 6 1 1000000000 898 777
1984 1 1
4
5 4 1499 2004
9 5 5
6
6 7 14 16 16 6

输出 #1

21
12
49000083104
3512
319

注意

在第一个输入集的第一个测试用例中,对以下子方块的奇观进行求和:

黄色对应于子方块,绿色对应于网格方块的其余部分。

图为大猩猩的最优排列。排列的奇观是$$$4 + 4 + 3 + 3 + 4 + 3 = 21$$$。