CF2000E Photoshoot for Gorillas

你非常喜欢大猩猩，于是你决定为它们组织一次拍摄活动。大猩猩生活在丛林中，丛林被表示为一个有 $n$ 行 $m$ 列的网格，有 $w$ 个大猩猩同意参与拍摄，第 $i$ 个大猩猩的身高为 $a_i$ .你希望将所有大猩猩放置在网格的单元格中，并且确保每个单元格中最多只有一只大猩猩。 每种方案的壮观程度等于网格中所有以 $k$ 为边长的子正方形的壮观程度的总和。 子正方形的壮观程度等于其中所有大猩猩的身高的总和。 从所有合适的方案中选出最壮观的方案。

第一行包含一个整数 $t$ ，表示共有 $t$ 组测试样例。 测试用例的描述如下。 第一行包含三个整数 $n，m，k$，表示网格的尺寸和子正方形的边长。 第二行包含一个整数 $w$，表示大猩猩的数量。 第三行包含 $w$ 个整数 $a_1，a_2，...，a_w$，表示每个大猩猩的身高。 保证所有测试样例中 $n·m$ 的总和不超过 $2·10^5$，$w$ 的总和也不超过 $2·10^5$。

对于每个测试用例，输出一个整数表示最壮观的方案的壮观程度。

In the first test case of the first input set, the spectacle of the following sub-squares is summed:  Yellow color corresponds to the sub-squares, green — to the rest of the grid squares.The picture shows the optimal arrangement of the gorillas. The spectacle of the arrangement is $ 4 + 4 + 3 + 3 + 4 + 3 = 21 $ .