Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Уважаемые участники, убедитесь, что вы прочитали руководство (и особенно раздел «Полезные советы и важные замечания»)!
Максим выиграл бонус в коллекционной карточной игре, и теберь он может выбрать новые карты для своей колоды. Разумеется, он хочет получить как можно более ценные карты.
Сейчас перед Максимом N карт, ценность i-й из которых равна A[i]. Максиму разрешается забрать себе не более K карт, расположенных подряд; такую операцию Максим может проделать два раза. Можно считать, что после того, как Максим возьмёт часть карт в первый раз, оставшиеся карты «придвинутся» друг к другу, и в ряду карт вновь не будет промежутков.
Помогите Максиму узнать максимальную общую ценность карт, которые он может забрать.
Входные данные
Входной поток в первой строке содержит целые числа N и K (2 <= N <= 2 × 10^5, 1 <= K <= 2 × 10^5) — соответсвенно общее количество карт и количество подряд расположенных карт, которые Максим может забрать себе.
Вторая строка содержит N целых чисел Ai (1 <= A[i] <= 5000) — ценность каждой из карт.
Выходные данные
Выведите одно целое число — максимальную общую ценность карт, которые Максим может забрать себе.
Примеры
| Входные данные | Выходные данные |
6 2
1 2 3 1 11 2 | 18 |
5 3
20 20 20 30 10 | 100 |
Для отправки решений необходимо выполнить вход.
|