Кольорове перетворення
Задано масив натуральних чисел \(a\), який містить \(n\) елементів. Спочатку всі елементи масиву зафарбовані у синій колір.
Потрібно вибрати \(k\) елементів масиву і пофарбувати їх у жовтий колір. Потім, якщо є хоча б один елемент синього кольору, то робимо наступне:
вибираємо будь-який елемент синього кольору, який має хоча б одного сусіда жовтого кольору, і фарбуємо його в жовтий колір.
Вартість фарбування масиву визначається як сума перших \(k\) обраних елементів і останнього пофарбованого елемента.
Необхідно визначити максимально можливу вартість фарбування.
Входові дані:
Перший рядок стандартного входового потоку містить два натуральних числа \(n\) та \(k\) \((2 \le n \le 10^5; 1 \le k < n)\).
Другий рядок містить \(n\) натуральних чисел \(a1,a2,…,an\) \(( 1 \le ai \le 10^9)\) – де, \(ai\) – вартість форбування і-го елемента.
Виходові дані:
У стандартний виходовий потік виведіть одне натуральне число, що є максимально можливою вартістю фарбування даного масиву.
Приклад входових даних:
5 2
3 4 2 1 2
Приклад виходових даних:
9
Comments