Задан целочисленный массив \(a\) размера \(n\).
Вы можете выполнить следующую операцию: выбрать элемент массива и заменить его значением любого из его соседей.
Например, если \(a=[3, 1, 2]\), вы можете получить один из массивов \([3, 3, 2]\), \([3, 2, 2]\) и \([1, 1, 2]\) за одну операцию, но не \([2, 1, 2\)] и \([3, 4, 2]\).
Ваша задача — посчитать минимально возможную сумму массива, если вы можете выполнить вышеописанную операцию не более \(k\) раз.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимально возможную сумму массива, если вы можете выполнить вышеописанную операцию не более \(k\) раз.
Примечание
В первом примере одна из возможных последовательностей операций: \([3, 1, 2] \rightarrow [1, 1, 2\)].
Во втором примере не нужно применять операцию.
В третьем примере одна из возможных последовательностей операций: \([2, 2, 1, 3] \rightarrow [2, 1, 1, 3] \rightarrow [2, 1, 1, 1]\).
В четвертом примере одна из возможных последовательностей операций: \([4, 1, 2, 2, 4, 3] \rightarrow [1, 1, 2, 2, 4, 3] \rightarrow [1, 1, 1, 2, 4, 3] \rightarrow [1, 1, 1, 2, 2, 3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 1
3 1 2
1 3
5
4 2
2 2 1 3
6 3
4 1 2 2 4 3
|
4
5
5
10
|