Maximum Flower Beauty Sum

You are given an integer n representing the number of flowers, an integer k, and an array a of n integers where each a_i denotes the beauty value of the i-th flower. In one operation, you can choose any contiguous segment of exactly k flowers and rearrange (i.e., permute) the elements within that segment arbitrarily. You may perform any number of such operations.

The goal is to obtain the maximum possible sum of the beauty values of all flowers after performing these operations. Note that, since the operation only rearranges the values, the sum of the array remains invariant. Hence, the answer is simply

Note: When k equals 1, no reordering is possible, so the output is just the sum of the array as it is. For any other valid k, the maximum achievable sum will not change, and the answer remains the sum of all elements.

inputFormat

The input consists of two lines:

1. The first line contains two integers n and k separated by a space, where n is the number of flowers and k is the length of each segment that can be rearranged.
2. The second line contains n space-separated integers representing the beauty values of the flowers.

You should read the input from standard input (stdin).

outputFormat

Output a single integer representing the maximum possible sum of the beauty values after performing the operations. This output should be written to standard output (stdout).

6 2
3 1 6 5 2 4

21