Background

Warning: Abusing this problem’s judging system will result in an account ban.

Shuchong and you are having fun visiting Luogu’s famous attractions.
But he stood you up because he is not good enough.
So you have to visit Luogu’s famous attractions by yourself.

Problem Description

You are visiting $n$ attractions, numbered from $1$ to $n$. Due to the strict requirement of 3k, you must visit them in the order from $1$ to $n$. You can visit at most $k$ attractions per day. Since you need to spend the remaining time on solving hard problems, you want to finish visiting these attractions as soon as possible.
Each attraction has a different level of attractiveness. The attractiveness of attraction $i$ is $a_i$. The official rating for a day is the maximum $a_i$ among the attractions visited that day. In the end, you sum up the official ratings of all days to get the final score.
Because you are in a hurry to solve hard problems, you have already calculated the minimum number of days needed to visit all attractions (call it $t$). You want to know:

• Visit in $t$ days.
• Satisfy that you visit at most $k$ attractions per day.
• What is the maximum possible final score.

Input Format

The first line contains two integers $n, k$, representing the number of attractions and the maximum number of attractions you can visit per day.
The second line contains $n$ integers $a_i$, representing the attractiveness of each attraction.

Output Format

Output one integer on a single line, representing:

• Visit in $t$ days.
• Satisfy that you visit at most $k$ attractions per day.
• The maximum possible final score.

($t$ is the minimum number of days needed to visit all attractions.)

5 3
2 5 7 1 4

12

Hint

Sample Explanation

For Sample $1$:

• It is easy to see that at least $2$ days are needed to visit all attractions.
• But we cannot visit all attractions in one day ($n > k$).
• If we split the attractions as evenly as possible, there are two cases:
  • If we visit $2$ attractions on the first day and $3$ on the second day, the final score is $5 + 7 = 12$.
  • If we visit $3$ attractions on the first day and $2$ on the second day, the final score is $7 + 4 = 11$.
• Therefore, the answer is $\max(12, 11) = 12$.

Constraints and Notes

This problem uses bundled testdata.

• Subtask 1 (20 pts): $2k \ge n$.
• Subtask 2 (20 pts): $k \le 100$, $n \le 10^5$.
• Subtask 3 (60 pts): No additional constraints.

For $100\%$ of the testdata, $1 \le k \le n \le 10^6$, $1 \le a_i \le 10^9$.

Notes

Translated from CCC 2019 Senior T4 Tourism.
Translator: @一只书虫仔。

Translated by ChatGPT 5