Tourism

You are planning a trip to visit $N$ tourist attractions. The attractions are numbered from $1$ to $N$ and must be visited in this order. You can visit at most $K$ attractions per day, and you want to finish the trip in as few days as possible.

Each attraction $i$ has a score $a_i$. For a given schedule, each day scores the maximum score among the attractions visited that day. The total score of the schedule is the sum of the daily scores. Find the maximum total score among the schedules that use the fewest possible days.

The first line contains two space-separated integers $N$ and $K$ ($1 \le K \le N \le 10^6$).

The next line contains $N$ space-separated integers $a_i$ ($1 \le a_i \le 10^9$).

For 3 of the 15 available marks, $2K \ge N$. For an additional 3 of the 15 available marks, $K \le 100$ and $N \le 10^5$.

Output a single integer, the maximum possible total score.