题目背景

警告：滥用本题评测将被封号！

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 Senior T4 Tourism。
翻译者：@一只书虫仔。