1118: ShadowDrunk的手办

众所周知，$ShadowDrunk$身为一个资深二刺螈，喜欢收集二次元手办，为了向集训队另外一个二刺螈$590$炫耀自己难评的审美，所以他决定把所有手办放进有$n\cdot m$个小格子的箱子中拍照，但这箱子不是一般的箱子，它每个小格子由于位置不同都会有不同的价值（具体由它被多少个$k\cdot k$的小矩形覆盖而决定）。本来$ShadowDrunk$想换掉箱子，但这个箱子是他的一生挚爱$OMoonStar$送给他的，所有他不能换。且每个手办对于$ShadowDrunk$的价值不同，为了达到最大的意义，$ShadowDrunk$需要将他所有的手办好好摆放一下。由于$ShadowDrunk$昨天和$OMoonStar$玩了一整天，所以需要聪明的你来帮他，为了惩罚$ShadowDrunk$，你只需要告诉他最大价值就可以了（每个有手办的格子的意义为格子价值与手办价值的乘积）。

第一行$t$表示样例的个数。其中$t<10^3$。

第二行$n,m,k$三个数字，其中$1<n\cdot m<=2\cdot 10^5,1<k<=min(n,m)$。

第三行$sz$表示$ShadowDrunk$手办的个数$1<=sz<=n\cdot m$。

接下来$sz$个数字表示每个手办的价值。每个手办的价值$<=10^9$。

保证同一测试点所有样例$\sum n*m$<=2e5

输出每个测试点的最大的摆放价值。

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

21
49000083104
12
319