Maximizing Sightseeing Score

You are visiting n attractions numbered from 1 to n in order. Due to constraints, you can visit at most k attractions per day. The score for a day is defined as the maximum attractiveness value among the attractions visited that day. Since you want to finish as fast as possible, you must complete the tour in the minimum number of days, namely \[ t=\lceil\frac{n}{k}\rceil, \] by partitioning the attractions into exactly t contiguous segments (each of size at least 1 and at most k). Your task is to choose a partition so that the sum of the daily scores is maximized. In other words, given an array \(a_1,a_2,\dots,a_n\) of attractiveness values, partition the array into exactly \(t\) segments (each segment has length \(\le k\)) and maximize the sum of the maximum values in each segment.

Input Format: The first line contains two integers \(n\) and \(k\). The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\).

Output Format: Output a single integer, the maximum achievable total score by partitioning the attractions into exactly \(t=\lceil\frac{n}{k}\rceil\) days.

inputFormat

The input begins with a line containing two integers n and k.

The second line contains n integers: a₁, a₂, ..., a_n.

outputFormat

Output a single integer representing the maximum total score achievable.

sample

5 2
1 2 3 4 5

11