10706번 - WTF 스페셜 저지다국어

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 transformation¹ 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

change the signs of all elements in A

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

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?

¹This doesn’t really exist.

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⁴, 10⁴].

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.