Statement is not available in English language
G. Покупка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы пришли в магазин карандашей. Перед вами на витрине находятся $$$n$$$ карандашей, $$$i$$$-й карандаш имеет стоимость $$$a_i$$$. Все карандаши одинаковы. Вы хотите купить ровно $$$k$$$ карандашей. При этом по какой-то причине вы обязательно хотите купить карандаш с номером $$$n$$$ среди $$$k$$$ купленных. Покупка происходит следующим образом: вы просматриваете карандаши слева направо(от номера $$$1$$$ к номеру $$$n$$$) и для каждого карандаша говорите продавщице, будете или нет вы покупать данный карандаш. Если вы покупаете данный карандаш, продавщица помимо цены карандаша просит вас заплатить еще и налог, который равен номеру предыдущего купленного карандаша(если он есть, если его нет, то налог равен $$$0$$$). Последний карандаш вы должны купить обязательно. Найдите минимальную стоимость, которую вы можете заплатить за покупку $$$k$$$ карандашей.

Входные данные

В первой строке вам даны числа $$$1 \le n \le 10^5$$$ и $$$1 \le k \le n$$$ – количество карандашей в магазине и количество карандашей, которые вам нужно купить. В следующей строке вам даны числа $$$1 \le a_i \le 10^5$$$ – стоимости карандашей слева направо.

Выходные данные

Выведите ответ на задачу.

Пример
Входные данные
5 3
5 3 2 4 6
Выходные данные
16
Примечание

Рассмотрим первый пример. Нам нужно купить $$$3$$$ карандаша. Последний нужно купить обязательно. Пусть мы не будем покупать первый карандаш, купим второй карандаш(заплатим $$$3$$$ + налог, который равен $$$0$$$, так как до этого мы ничего не покупали), третий карандаш не будем покупать, купим четвертый карандаш(заплатим налог $$$2$$$, так как последний карандаш, который мы до этого покупали, был второй) и купим пятый карандаш(заплатим налог $$$4$$$, так как до этого мы покупали $$$4$$$-й карандаш). Получается, для данного выбора мы заплатим $$$17$$$. Обратите внимание, что это не оптимальное решение.