Вы очень любите горилл, поэтому решили устроить им фотосессию. Гориллы обитают в джунглях. Джунгли представляют собой клетчатое поле из \(n\) строк и \(m\) столбцов. В фотосессии согласились принять участие \(w\) горилл, горилла с номером \(i\) (\(1 \le i \le w\)) имеет рост \(a_i\). Вы хотите расставить всех горилл в клетки поля так, чтобы в каждой клетке стояло не более одной гориллы.
Зрелищность расстановки равна сумме зрелищностей всех подквадратов поля с длиной стороны \(k\).
Зрелищность подквадрата равна сумме ростов горилл в нём.
Из всех подходящих расстановок выберите расстановку с максимальной зрелищностью.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — максимальную зрелищность подходящей расстановки.
Примечание
В первом наборе входных данных первого теста суммируются зрелищности следующих подквадратов:
Жёлтый цвет соответствует подквадратам, зелёный — остальным клеткам поля. На картинке представлено оптимальное расположение горилл. Зрелищность расстановки равна \(4 + 4 + 3 + 3 + 4 + 3 = 21\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|