В сверхсекретную военную часть под командованием полковника Зуева скоро приедет комиссия из министерства обороны. Согласно уставу, в каждой сверхсекретной военной части должна быть сверхсекретная рота, которая должна заниматься... а чем именно — не скажем, на то она и сверхсекретная. Проблема заключается в том, что в части Зуева такой роты почему-то нет.
Полковник решил разобраться с этой проблемой незамедлительно и приказал построить на плацу в одну шеренгу всех n солдат вверенной ему части. Известно, что болтливость i-го слева солдата равна qi. Зуев хочет, чтобы сверхсекретная рота состояла из k первых солдат шеренги, а их суммарная болтливость была как можно меньше (чтобы рота оставалсь сверхсекретной). Для этого он собирается не более s раз поменять местами двух соседних солдат. Заметим, что любой солдат может участовать в таком обмене позициями сколько угодно раз. Задача оказалась нетривиальной, и полковник Зуев обратился к вам за помощью. Определите, какую минимальную суммарную болтливость первых k солдат шеренги можно достичь, если провести не более s операций обмена соседних солдат.
Выходные данные
Выведите единственное целое число — минимальную возможную суммарную болтливость сверхсекретной роты.
Примечание
В первом примере полковнику достаточно поменять местами второго и третьего солдата и не использовать второй обмен. Итоговое положение солдат: (2, 1, 4). Минимальная возможная суммарная болтливость сверхсекретной роты равна 3.
Во втором примере полковник будет производить обмены в следующей последовательности :
- (10, 1, 6 — 2, 5)
- (10, 1, 2, 6 — 5)
Итоговое положение солдат (10, 1, 2, 5, 6).
Минимальная суммарная болтливость роты равна 18.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2 2
2 4 1
|
3
|
|
2
|
5 4 2
10 1 6 2 5
|
18
|
|
3
|
5 2 3
3 1 4 2 5
|
3
|