| Codeforces Round 966 (Div. 3) |
|---|
| Закончено |
Вы очень любите горилл, поэтому решили устроить им фотосессию. Гориллы обитают в джунглях. Джунгли представляют собой клетчатое поле из $$$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$$$.
Для каждого набора входных данных выведите единственное целое число — максимальную зрелищность подходящей расстановки.
53 4 291 1 1 1 1 1 1 1 12 1 125 720 15 794 1 4 5 6 1 1000000000 898 7771984 1 145 4 1499 20049 5 566 7 14 16 16 6
21 12 49000083104 3512 319
В первом наборе входных данных первого теста суммируются зрелищности следующих подквадратов:
Жёлтый цвет соответствует подквадратам, зелёный — остальным клеткам поля. На картинке представлено оптимальное расположение горилл. Зрелищность расстановки равна $$$4 + 4 + 3 + 3 + 4 + 3 = 21$$$.
