яркое, солнечное и невинное......
У Тенцинга есть красивое ожерелье. Ожерелье состоит из \(n\) жемчужин, пронумерованных от \(1\) до \(n\), с нитками, соединяющими жемчужины \(i\) и \((i \text{ mod } n)+1\) для всех \(1 \leq i \leq n\).
Однажды Тенцинг захотел разделить ожерелье на несколько частей, перерезав несколько нитей. На каждой связной части ожерелья должно быть не более \(k\) жемчужин. Время, необходимое для разрезания каждой нити, может быть неодинаковым. Тенцинг должен потратить \(a_i\) минут, чтобы перерезать нить между жемчужинами \(i\) и \((i \text{ mod } n)+1\).
Тенцинг хочет узнать минимальное время в минутах, которое требуется, чтобы разрезать ожерелье так, чтобы в каждой связной части было не более \(k\) жемчужин.
Выходные данные
Для каждого набора входных данных выведите минимально необходимое общее время в минутах.
Примечание
В первом наборе ожерелье будет разрезано на \(3\) части: \([1,2][3,4][5]\), поэтому общее время составит \(3\).
Во втором наборе ожерелье будет разрезано на \(3\) части: \([5,1][2][3,4]\). Тенцинг разрежет нитки, соединяющие \((1,2), (2,3)\) и \((4,5)\), поэтому общее время составит \(a_1+a_2+a_4=7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 2
1 1 1 1 1
5 2
1 2 3 4 5
6 3
4 2 5 1 3 3
10 3
2 5 6 5 2 1 7 9 7 2
|
3
7
5
15
|