I. Тенцинг и ожерелье
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод
яркое, солнечное и невинное......

У Тенцинга есть красивое ожерелье. Ожерелье состоит из $$$n$$$ жемчужин, пронумерованных от $$$1$$$ до $$$n$$$, с нитками, соединяющими жемчужины $$$i$$$ и $$$(i \text{ mod } n)+1$$$ для всех $$$1 \leq i \leq n$$$.

Однажды Тенцинг захотел разделить ожерелье на несколько частей, перерезав несколько нитей. На каждой связной части ожерелья должно быть не более $$$k$$$ жемчужин. Время, необходимое для разрезания каждой нити, может быть неодинаковым. Тенцинг должен потратить $$$a_i$$$ минут, чтобы перерезать нить между жемчужинами $$$i$$$ и $$$(i \text{ mod } n)+1$$$.

Тенцинг хочет узнать минимальное время в минутах, которое требуется, чтобы разрезать ожерелье так, чтобы в каждой связной части было не более $$$k$$$ жемчужин.

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

Каждый тест содержит несколько наборов входных данных. Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов. Далее следует описание наборов.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2\leq n\leq 5\cdot 10^5$$$, $$$1\leq k <n$$$).

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i\leq 10^9$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$5 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите минимально необходимое общее время в минутах.

Пример
Входные данные
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
Примечание

В первом наборе ожерелье будет разрезано на $$$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$$$.