一条名为 Fascination Street 的街道被划分为 $N$ 个长度相等的街区。对于每个街区 $i$ ($1 \le i \le 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$，你应该求出照亮整条街道的最小总费用。

输入格式

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

第二行包含 $N$ 个空格分隔的整数 $W_1, W_2 \dots W_N$，其中 $W_i$ 是在第 $i$ 个街区安装路灯的费用。($0 \le W_i \le 10^9$)

输出格式

输出一个整数，表示照亮整条街道的最小总费用。

样例

输入样例 1

5 0
1 3 10 3 1

输出样例 1

4

输入样例 2

5 1
1 3 10 3 1

输出样例 2

2

输入样例 3

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

输出样例 3

1525

输入样例 4

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

输出样例 4

1107