说明

阿丽莎和鲍勃成为了电视竞猜的获胜者，他们现在要选择奖品。共有 $n$ 个奖品，编号从 $1$ 到 $n$。

奖品分配规则如下： 组织者给出一个正整数 $k$（$1 \leq k \leq n / 3$）。首先，阿丽莎选择 $k$ 个连续的奖品编号。然后，鲍勃选择 $k$ 个连续的奖品编号，但不能选择阿丽莎已经选中的编号。之后，获胜者们领取他们选择的奖品。

阿丽莎非常了解鲍勃，并且她知道每个奖品对鲍勃的价值是多少（这是一个正整数）。阿丽莎不喜欢鲍勃，她希望选择奖品时，使得鲍勃选择的奖品总价值尽可能小。阿丽莎不关心自己得到哪些奖品。

任务：编写程序，根据奖品的价值和 $k$ 的值，确定阿丽莎能做到的最小总价值 $x$，使得鲍勃选择的奖品总价值不会超过 $x$。

输入格式

输入文件的第一行包含两个整数：$n$ —— 奖品总数，$k$ —— 每个获胜者必须选择的连续奖品数（$3 \leq n \leq 100 000，1 \leq k \leq n / 3$）。

第二行包含 $n$ 个整数：$a_1, a_2, ..., a_n$，表示每个奖品对鲍勃的价值（$1 \leq a_i \leq 10^9$）。

输出格式

输出文件应包含一个整数 —— 最小的 $x$，使得阿丽莎能够让鲍勃选择的奖品总价值不超过 $x$。

10 2
1 2 4 5 2 4 2 2 1 6

7

提示

示例说明

在这个示例中，阿丽莎可以选择第 $4$ 和第 $5$ 个奖品。此时，鲍勃可以选择第 $9$ 和第 $10$ 个奖品，获得的总价值为 $7$。

任务评价系统与子任务说明

子任务 1（30分）

$3 \leq n \leq 50$，$1 \leq a_i \leq 10^5$

子任务 2（30分）

$3 \leq n \leq 5000$，$1 \leq a_i \leq 10^5$

子任务 3（40分）

$3 \leq n \leq 100 000$，$1 \leq a_i \leq 10^9$

翻译来源：GPT 5.2。