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 want to plan the trip to take the fewest number of days as
possible.

Under these constraints, you want to find a schedule that has a nice
balance between the attractions visited each day. To be precise, we
assign a score \(a_i\) to attraction
\(i\). Given a schedule, each day is
given a score equal to the maximum score of all attractions visited that
day. Finally, the scores of each day are summed to give the total score
of the schedule. What is the maximum possible total score of the
schedule, using the fewest days possible?

\((1\le K\le N\le 10^6)\)
\((1\le a_i\le 10^9)\)
\(2K\ge N\)
\(K\le 100\)
\(N\le 10^5\)

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.

생성자가 기록되지 않았습니다.

출처 CCC 2019 Senior