Конструирование
Ватсону нужно сконструировать наиболее эффективную нейронную сеть. Для этого ему предоставили плату из Nчипов, которые расположены линейно на расстоянии 1 см друг от друга. Каждый чип имеет свою производительность, которая выражается целым числом. Ватсон может сделать произвольное количество нейронов из этих чипов, при этом каждый чип может участвовать не больше, чем в 1 нейроне. Нейрон получается соединением двух чипов, расположенных на расстоянии ровно M см друг от друга. Эффективность нейрона – это сумма производительностей чипов, из которых он состоит. Эффективность нейронной сети – это сумма эффективностей нейронов. В нейронной сети может быть произвольное количество нейронов (даже 0).
Входные данные
В первой строке указано два целых числа N и M.
В следующей строке указано N целых чисел A_i – производительности чипов.
1 ≤ N, M ≤ 10^5, -10^6 < A_i < 10^6
Выходные данные
Наибольшая эффективность нейронной сети, построенной на входной плате.