你真的很喜欢大猩猩,所以你决定为它们组织一次拍摄。大猩猩生活在丛林中。丛林被表示为由 $$$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$$$。