//sj 가 아직 ..

Assume you are given an array A of N integers, array ID of N + 1 integers from the interval [1, N -1] and an integer R.

We are doing a Warshall-Turing-Fourier transformation1 on array A in the following way:

sum = 0
   for i = 1 to N
   index = min{ ID[i], ID[i+1] }
   sum = sum + A[index]
   rotate array A to the right by R places

for i = 1 to N
   index = max{ ID[i], ID[i+1] }
   index = index + 1
   sum = sum + A[index]

You are given the array A and constant R, but you are not familiar with the array ID. What is the largest possible value of variable sum after execution of the above algorithm?

입력

• The first line of input contains the integers N and R (2 <= N <= 3 000, 1 <= R < N) from the task.
• The second line of input contains the elements of array A, respectively from A[1] to A[N]. These are integers from the interval [-10^4 , 10^4].

출력

• The first line of output must contain the maximal value of sum.
• The second line of output must contain the array ID of N + 1 integers from the interval [1, N - 1] for which the algorithm outputs the maximal sum. If there are multiple such arrays, output any.

입출력 예

입력

5 3
1 -1 1 -1 1

출력

10
1 1 1 2 2 3

입력

6 5
2 5 4 1 3 5

출력

16
3 2 1 1 5 4 1

출처:coci_2013-2014_contest6 6/6