CF1842I Tenzing and Necklace

明亮、阳光且纯真…… Tenzing 有一串漂亮的项链。这串项链由 $n$ 颗珍珠组成，编号从 $1$ 到 $n$，每颗珍珠 $i$ 与珍珠 $((i \bmod n) + 1)$ 之间用一根线相连，对于所有 $1 \leq i \leq n$。 有一天，Tenzing 想通过剪断一些线将项链分成若干部分。但每一部分中，连通的珍珠数量不能超过 $k$。剪断每根线所需的时间可能不同。Tenzing 需要花 $a_i$ 分钟剪断珍珠 $i$ 与 $((i \bmod n) + 1)$ 之间的线。 Tenzing 想知道，最少需要多少分钟，才能将项链剪成每一部分都不超过 $k$ 颗珍珠。

每组测试数据包含多个测试用例。输入的第一行为一个整数 $t$（$1 \leq t \leq 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$。

对于每个测试用例，输出使每一部分连通珍珠数不超过 $k$ 所需的最小总时间（分钟数）。

在第一个测试用例中，项链将被切成 $3$ 部分：$[1,2][3,4][5]$，因此总时间为 $3$。 在第二个测试用例中，项链将被切成 $3$ 部分：$[5,1][2][3,4]$，Tenzing 将剪断 $(1,2)$、$(2,3)$ 和 $(4,5)$ 之间的线，因此总时间为 $a_1+a_2+a_4=7$。 由 ChatGPT 4.1 翻译