Робота в команді
На своє улюблене свято Фермер Джон хоче надіслати подарунки своїм друзям. Для цього він попросив корів допомогти йому з пакуванням подарунків.
n корів Фермера Джона стоять у ряд, пронумеровані від 1 до n. Корова i має рівень майстерності в пакуванні подарунків, позначений як s[i]. Фермер Джон вирішив об'єднати корів у команди. Команда може складатися з будь-якої послідовності корів, але не більше ніж з k корів, і жодна корова не може бути в більш ніж одній команді. Оскільки корови можуть навчатися одна в одної, рівень майстерності кожної корови в команді може бути підвищений до рівня наймайстернішої корови в цій команді.
Допоможіть Фермеру Джону визначити максимально можливу суму рівнів майстерності, яку він може отримати, оптимально сформувавши команди.
Вхідні дані
Перша стрічка містить n (1 ≤ n ≤ 10^4) і k (1 ≤ k ≤ 1000). Наступні n стрічок містять рівні майстерності n корів у порядку, в якому вони стоять. Кожен рівень майстерності — це додатне ціле число, не більше 10^5.
Вихідні дані
Виведіть найбільшу можливу суму рівнів майстерності, яку може отримати Фермер Джон, згрупувавши корів у команди.
Приклад
У цьому прикладі оптимальним рішенням є згрупувати перші 3 корови і останні 3 корови, залишивши середню корову окремо. Нагадаємо, що команди можуть бути меншими за k. Рівні майстерності зростуть до 15, 15, 15, 9, 10, 10, 10, що дає суму 84.