该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

修补围栏

题目描述

你要修理一段由 $n$ 块竖直木板组成的围栏，第 $i$ 块木板的高度为 $h_i$。

为了美观，你需要选择一段长度恰好为 $k$ 的连续区间，并将区间内所有木板的高度变为完全一致。

你可以执行以下操作：

1. 增加高度：你可以花费 1 金币将某块木板的高度增加 1。你可以无限次执行此操作，但不能降低木板高度。
2. 使用“万能木板”：在选定区间并开始修补之前，你必须且只能选择区间内的一块木板，将其移除，并换上一块“万能木板”。万能木板的高度可以由你指定为任意正整数（此替换操作不消耗金币）。

目标：选择一个最佳的区间和最佳的替换策略，使得将该区间（含万能木板）所有 $k$ 块木板变为同一高度的总花费最小。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($2 \le k \le n \le 2 \cdot 10^5$)。

第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$)。

输出格式

输出一个整数，表示最小的总花费。

输入输出样例 #1

输入 #1

5 3
1 10 2 3 5

输出 #1

1

说明/提示

样例解释

我们可以选择最后三个木板组成的区间 [2, 3, 5]（下标 3 到 5）。

在该区间内，我们需要使所有木板高度一致。

策略如下：

1. 替换：选择区间内高度为 5 的木板（最大值），将其替换为万能木板。
2. 此时区间剩余的原始木板为 {2, 3}。
3. 为了花费最小，我们将目标高度设为剩余木板的最大值，即 3。
4. 设定万能木板：将万能木板的高度直接设为 3（花费 0）。
5. 修补：将原本高度为 2 的木板加高到 3（花费 1）。
6. 最终区间变为 [3, 3, 3]，总花费为 $1$。

(注：若选择区间 [1, 10, 2]，移除 10，剩余 {1, 2}，目标设为 2，花费也是 1，结果依然最小。)