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