题目描述

给定一个长度为 $n$ 的正整数数组 $a_1, a_2, \dots, a_n$，以及一个正整数 $k$。

有两个玩家 Alice 和 Bob，他们将按以下规则在数组中选择元素：

1. 首先，Alice 在数组中选择一个长度为 $k$ 的连续区间。
2. 然后，Bob 在数组中选择一个长度为 $k$ 的连续区间，并且 Bob 选择的区间不能与 Alice 选择的区间有任何重叠部分。

Bob 的目标是最大化他所选择的区间内所有元素的和。 Alice 知道 Bob 的策略，因此她的目标是最小化 Bob 最终能够获得的区间和。

请你计算，在 Alice 采取最优策略的情况下，Bob 最终获得的区间元素之和最大是多少。

输入格式

第一行包含两个整数 $n$ 和 $k$ —— 分别表示数组的长度和每次必须选择的连续区间长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ —— 表示数组的元素。

输出格式

输出一行，一个整数，表示在 Alice 采取最优策略下，Bob 所能选择的区间元素之和的最大值。

样例输入 1

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

样例输出 1

7

说明

样例解释

在给定的数组中，Alice 采取的最优策略是选择第 $4$ 和第 $5$ 个元素（值为 $5$ 和 $2$）。 此时，Bob 为了最大化自己的收益，会在剩余不重叠的合法部分中选择第 $9$ 和第 $10$ 个元素（值为 $1$ 和 $6$），获得的总和为 $1 + 6 = 7$。 可以证明，无论 Alice 选择其他哪个长度为 $2$ 的区间，Bob 都能找到一个和不小于 $7$ 的不重叠区间。

数据范围

对于所有测试点，保证：

• $3 \le n \le 100000$。
• $1 \le k \le \lfloor n / 3 \rfloor$。
• $1 \le a_i \le 10^9$。
• 保证所有的输入数值均为整数。

各子任务的附加限制如下：

• 子任务 $1$（$30$ 分）：$3 \le n \le 50$，$1 \le a_i \le 10^5$。
• 子任务 $2$（$30$ 分）：$3 \le n \le 5000$，$1 \le a_i \le 10^5$。
• 子任务 $3$（$40$ 分）：无特殊限制。