시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 5 5 5 100.000%

문제

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

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?

1This 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 [−104, 104].

출력

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

예제 입력 2

6 5
2 5 4 1 3 5

예제 출력 2

16
3 2 1 1 5 4 1

힌트