E. 大猩猩的拍照安排

每个测试点时间限制：$2$ 秒
每个测试点内存限制：$256$ 兆字节

你非常喜欢大猩猩，所以决定为它们组织一次拍照活动。
大猩猩生活在丛林中。丛林被表示为一个有 $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, \dots, a_w$（$1 \le a_i \le 10^9$）—— 大猩猩的身高。

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

输出格式

对于每个测试用例，输出一个整数 —— 最大可能的观赏值。

示例

输入：

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

输出：

21
12
49000083104
3512
319

说明

在第一个测试用例中，需要求和所有边长为 $k$ 的子正方形的观赏值。

黄色格子对应被计入的子正方形，绿色格子对应网格的其他部分。
图示展示了大猩猩的最优安排，该安排的观赏值为 $4+4+3+3+4+3=21$。