结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

某电子厂质检科管理一条产线的出厂检测记录。一条产线当班共产出 $n$ 件产品，按产出先后编号 $1 \sim n$，第 $i$ 件产品的检测值为 $a_i$。每季度末，质检科要把当班记录切成若干连续段归档，每段装订成一卷。

归档卷的装订规则如下：切段必须按顺序进行，即每卷内的产品编号连续，且每件产品恰好属于一卷；出于装订规格限制，每卷收录的产品件数至少为 2 且不超过 $L$。

质检科用"波动成本"衡量一卷记录的归档质量：一卷的波动成本定义为卷内产品检测值的最大值与最小值之差。全部卷宗的波动成本之和称为本季度的总归档成本。

请帮质检科计算：在满足装订规则的所有切分方案中，总归档成本的最小值。

输入格式

从文件 segcost.in 中读入数据。

• 第一行两个整数 $n, L$，表示产品件数与每卷收录件数的上限；
• 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，依次表示各件产品的检测值。

输出格式

输出到文件 segcost.out 中。

输出一行一个整数，表示总归档成本的最小值。

样例

6 4
3 1 4 1 5 9

7

样例 1 解释

把 $6$ 件产品按规则切分，段长只能是 $2$、$3$ 或 $4$，共四种切法。逐种核算：

• $[3,1]\ [4,1,5,9]$：$(3-1)+(9-1)=2+8=10$；
• $[3,1,4]\ [1,5,9]$：$(4-1)+(9-1)=3+8=11$；
• $[3,1,4,1]\ [5,9]$：$(4-1)+(9-5)=3+4=7$；
• $[3,1]\ [4,1]\ [5,9]$：$(3-1)+(4-1)+(9-5)=2+3+4=9$。

最小值为 $7$，对应切成长度 $4$ 与长度 $2$ 的两卷。

8 3
1 20 19 14 6 12 9 7

29

样例 2 解释

一种总成本为 $29$ 的切法：$[1,20,19]\ [14,6,12]\ [9,7]$，成本 $(20-1)+(14-6)+(9-7)=19+8+2=29$。若全部按最短长度切，$[1,20]\ [19,14]\ [6,12]\ [9,7]$ 的成本为 $19+5+6+2=32$。

8 3
2 4 5 9 10 15 16 21

10

数据范围

对于所有测试数据，保证：

• $2 \le n \le 10^5$，$2 \le L \le n$；
• $0 \le a_i \le 10^9$；
• 至少存在一种满足装订规则的切分方案。

各测试点的约束如下：

• 特殊性质 A：检测值单调不减，即 $a_1 \le a_2 \le \cdots \le a_n$。