题目内容

以 $Stable/ Diffusion$ 为代表的图像和视频生成模型，通常通过重复执行同一个核心算法完成逐步优化：从初始随机噪声出发，经过多次迭代后得到清晰的图像或视频。设整个优化过程共包含 $T$ 个步骤。随着生成质量要求提高、生成视频时长增加，核心算法需要执行的迭代步骤数也不断增多。由于整体计算量与步骤数成正比，这会显著增加计算负载，从而给实际应用部署带来困难。

一种降低计算量的方法是采用“缓存复用”策略。研究发现，相邻步骤产生的特征通常较为相似，因此，当第 $t$ 步与第 $t+1$ 步的特征高度相似时，可以在第 $t+1$ 步直接复用第 $t$ 步的计算结果，而不再执行第 $t+1$ 步对应的计算。若在总计 $T$ 步的优化过程中跳过 $k$ 步，则所需计算量将降低为原来的 $(T-k)/T$。

缓存复用虽然能够减少计算，但被跳过的步骤会造成图像或视频生成质量的损失。现给定一个长度为 $T-1$ 的损失值列表，用于描述跳过各步骤时产生的损失。其中，第 $t$ 个元素（$0 \le t < T$）表示在第 $t+1$ 步复用第 $t$ 步的计算结果，也就是跳过第 $t+1$ 步计算时产生的损失值。

为了保证最终生成质量，跳过步骤时还必须满足限制：不能连续跳过 $2$ 个及以上步骤，即不能发生连续复用。

请设计一个函数。给定总迭代步骤数 $T$、必须跳过的步骤数 $k$ 以及损失值列表 loss，从所有满足上述限制的跳过方案中确定最优策略，并输出对应的最小总损失值。如果不存在能够恰好跳过 $k$ 步且满足要求的方案，则按照输出规则处理。

输入描述

1. $T$：正整数，表示总迭代步骤数，满足 $1 < T \le 1000$。
2. $k$：正整数，表示需要跳过的步骤数，满足 $0 \le k < T$。
3. loss：由空格分隔的 $T-1$ 个正整数组成的损失值列表。第 $t$ 个值（$0 \le t < T$）表示跳过第 $t+1$ 步，即在该步骤复用第 $t$ 步计算结果时产生的损失值。每个损失值均为小于 $1000$ 的正整数。

输出描述

output：如果不存在满足条件的跳过方案，输出 $-1$；否则输出能够达到的最小总损失值。

样例1

输入

5
2
3 5 4 2

输出

5

说明

可跳过步骤编号为 1 到 4。需要选择 2 个互不相邻的步骤。

所有可行的组合为：

• 选择 1 和 3，损失为 $3+4=7$；
• 选择 1 和 4，损失为 $3+2=5$；
• 选择 2 和 4，损失为 $5+2=7$。

其中最小损失为 5，因此输出 5。

样例2

输入

4
0
10 20 30

输出

0

说明

总迭代步骤数为 4，可跳过位置有 3 个。目标跳过步数 $k=0$，表示不跳过任何步骤。

此时没有选择任何可跳过步骤，总损失为 0，因此输出 0。

样例3

输入

4
3
2 4 6

输出

-1

说明

共有 3 个可跳过步骤，编号为 1 到 3。由于不能连续跳过，最多只能选择 2 个互不相邻的步骤，例如第 1 和第 3 个。

目标需要跳过 3 步，已经超过了最大可选数量，因此不存在合法方案，输出 -1。

样例4

输入

10
4
8 3 6 1 9 2 7 4 5

输出

10

说明

需要从可跳过的步骤中选择 $4$ 个步骤，并且任意两个被跳过的步骤不能连续。

选择跳过第 $2$、第 $4$、第 $6$、第 $8$ 个步骤时，对应的损失值分别为 $3$、$1$、$2$、$4$，总损失为：

$3 + 1 + 2 + 4 = 10$

该方案满足不存在连续跳过的步骤，并且在所有合法的跳过方案中，总损失值最小，因此输出 $10$。