Вам дан массив \(a\) с \(n\) целыми числами. Вы можете выполнить следующую операцию не более \(k\) раз:
- Выберите два индекса \(i\) и \(j\), в которых \(i \,\bmod\, k = j \,\bmod\, k\). (\(1 \le i < j \le n\)).
- Поменяйте местами \(a_i\) и \(a_j\).
После выполнения всех операций вы должны выбрать \(k\) последовательных элементов, и сумма этих \(k\) элементов станет вашим счетом. Найдите максимальное количество очков, которое вы можете получить.
Здесь \(x \bmod y\) обозначает остаток от деления \(x\) на \(y\).
Выходные данные
Для каждого набора входных данных выведите максимальное количество баллов, которое вы можете получить, по одному в каждой строке.
Примечание
В первом примере мы можем получить счет \(11\), если выберем \(a_1, a_2\) без выполнения операций.
В третьем примере, если мы поменяем местами \(a_1\) и \(a_4\), а потом выберем \(a_3, a_4, a_5\), то мы получим счет \(15\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 2
5 6 0
1 1
7
5 3
7 0 4 0 4
4 2
2 7 3 4
3 3
1000000000 1000000000 999999997
|
11
7
15
10
2999999997
|