You are given an array A of size N. You can apply the following operation at most M times:
Select two indices i, j such that (1 <= i < j <= N) and i % M == j % M
Swap Ai and Aj.
After performing all these operations, you have to choose any subarray of size M from this array. And the sum of all elements in this subarray is your strength. Find the maximum strength you can obtain.InputThe first line of the input contains two integers N and K.
The second line of the input contains N space seperated integers.
Constraints:
1 <= K <= N <= 105
1 <= Ai <= 109OutputPrint the maximum strength you can get.ExampleSample Input:
5 2
6 4 8 2 3
Sample Output:
12
Explaination:
We simply take the subarray l = 2, r = 3. Sum = 12
This is the maximum possible.