[CCC2019] Tourism

**警告：滥用本题评测将被封号！** Shuchong 和您正在畅玩洛谷著名景点。 但是他因为太菜爽约了。 您只好独自去游览洛谷著名景点。

您正在游览 $n$ 个景点，编号为 $1$ 到 $n$，并且因为 3k 的强硬要求，您必须按照 $1$ 到 $n$ 的顺序浏览。您一天最多可以游览 $k$ 个景点，因为剩下的时间您要用来爆切黑题，所以您想尽快浏览完这些景点。 每个景点对您的吸引度不同，第 $i$ 个景点对您的吸引度为 $a_i$，一天游览的这些景点的官方评分就是这天游览的景点的 $a_i$ 的最大值。最后，您需要把每天的官方评分加起来获得最后的评分。 因为您太着急想爆切黑题了，所以您提前计算好了浏览完所有景点最少需要多少天（假设它为 $t$），您想知道： - 用 $t$ 天浏览 - 满足每天最多游览 $k$ 个景点 - 能得到的最后的评分最大是多少

第一行两个整数 $n,k$ 代表景点数和最多游览景点数。 第二行 $n$ 个整数 $a_i$ 代表每个景点的吸引度。

一行一个整数代表 - 用 $t$ 天浏览 - 满足每天最多游览 $k$ 个景点 - 能得到的最后的评分最大是多少 （$t$ 为浏览完所有景点最少需要多少天）

5 3
2 5 7 1 4

12

#### 样例说明 对于样例 $1$： - 我们很容易就知道至少需要 $2$ 天就可以浏览完所有景点。 - 但是我们不能一天内浏览完所有景点。（$n>k$） - 我们把景点尽量平分，有以下两种情况： - 如果第一天浏览 $2$ 个，第二天浏览 $3$ 个，最终的评分为 $5+7=12$。 - 如果第二天浏览 $3$ 个，第二天浏览 $2$ 个，最终的评分为 $7+4=11$。 - 最后的答案为 $\max(12,11)=12$。 #### 数据规定与说明 **本题采用捆绑测试。** - Subtask 1（20 pts）：$2k \ge n$。 - Subtask 2（20 pts）：$k \le 100$，$n \le 10^5$。 - Subtask 3（60 pts）：无特殊限制。 对于 $100\%$ 的数据，$1 \le k \le n \le 10^6$，$1 \le a_i \le 10^9$。 #### 说明 **翻译自 [CCC 2019](https://cemc.math.uwaterloo.ca/contests/computing/2019/index.html) Senior T4 [Tourism](https://cemc.math.uwaterloo.ca/contests/computing/2019/stage%201/seniorEF.pdf)。** 翻译者：@[一只书虫仔](https://www.luogu.com.cn/user/114914)。