Description

一条名为 迷人街道 的街道被划分为 $N$ 个长度相等的街区。对于每个街区 $i$（$1 \leq i \leq N$），如果 $i > 1$，则其左侧有街区 $i-1$；如果 $i < N$，则其右侧有街区 $i+1$。

与其名字不同，这条街道在夜晚以黑暗和阴森著称。为了解决这个问题，Robert 决定在一些街区安装路灯。为第 $i$ 个街区安装路灯的成本是 $W_i$，总成本是每个安装成本的总和。安装后，每个街区要么自身有路灯，要么其左侧或右侧的街区有路灯。

Robert 还有一些技巧来降低成本。在安装路灯之前，Robert 选择两个不同的街区 $i$ 和 $j$，并交换它们的位置。操作后，安装成本也会交换。换句话说，该操作只是交换 $W_i$ 和 $W_j$ 的值。这个操作没有成本，但 Robert 最多只能执行 $K$ 次。

现在，给定数组 $W$ 和最大可能的操作次数 $K$，你需要找到照亮整条街道的最小成本。

Input Format

第一行包含两个以空格分隔的整数 $N, K$。$N$ 是街区的数量，$K$ 是最大可能的操作次数（$1 \leq N \leq 250000$，$0 \leq K \leq 9$）。

第二行包含 $N$ 个以空格分隔的整数 $W_1, W_2 \cdots W_N$，其中 $W_i$ 是为第 $i$ 个街区安装路灯的成本（$0 \leq W_i \leq 10^9$）。

Output Format

输出一个整数，表示照亮整条街道的最小成本。

5 0
1 3 10 3 1

4

5 1
1 3 10 3 1

2

12 0
317 448 258 208 284 248 315 367 562 500 426 390

1525

12 2
317 448 258 208 284 248 315 367 562 500 426 390

1107

Hint

翻译由 DeepSeek V3 完成