我们要把身高最高的大猩猩放在被最多子方块覆盖的单元格中，这样才能使得答案最大
因此问题可以转化为寻找nxm的矩阵中每一个单元格被kxk方块覆盖的次数，这也是本道题目的难点。

#include<iostream>
#include<algorithm>
#include<vector> 
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
vector<LL> s;
int a[N];
int n, m, k, w;
int t;
void solution()
{ 
    s.clear();
    LL sum = 0;

    //寻找每一个单元格可被方块覆盖的次数：
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            int x0, x1, y0, y1, x, y;
            x0 = min(i, n - i + 1);
            x1 = min(k, n - k + 1);
            x = min(x0, x1);
            y0 = min(j, m - j + 1);
            y1 = min(k, m - k + 1);
            y = min(y0, y1);
            sum = x * y;
            s.push_back(sum);
        }
    }

    /*for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < m; j ++)
        {
            cout << s[i * m + j] << " ";
        }
        cout << endl;
    }*/
    sort(a, a + w, greater<int>());
    sort(s.begin(), s.end(), greater<int>());
}
int main()
{
    cin >> t;
    while(t --)
    {
        memset(a, 0, sizeof a);
        scanf("%d%d%d%d", &n, &m, &k, &w);
        for(int i = 0; i < w; i ++) scanf("%d", &a[i]);
        solution();
        LL sum = 0;
        for(int i = 0; i < w; i ++)
        {
            sum += a[i] * s[i];
        }
        cout << sum << endl;
    }
    return 0;
}