Maximum Sum after the Warshall–Turing–Fourier Transform

You are given an array \(A\) of length \(n\), an unknown array \(ID\) of length \(n+1\) whose elements are integers from \(1\) to \(n-1\), and an integer \(r\). We apply the following pseudo‐code (called the Warshall–Turing–Fourier (WTF) transform^[1]) on \(A\):

sum = 0
for i = 1 to n
    index = min{ ID[i], ID[i+1] }
    sum = sum + A[index]
    Rorate(A, r)
Change(A)
for i = 1 to n
    index = max{ ID[i], ID[i+1] }
    index = index + 1
    sum = sum + A[index]
    Rorate(A, r)

The operations are defined as follows:

• Change(A) changes every element of \(A\) to its opposite (i.e. multiplies each by \(-1\)).
• Rorate(A, r) is defined by concatenating two copies of \(A\) to form an array \(B\) and then setting \(A = B[ n - r + 1,\; 2n - r ]\); that is, rotate \(A\) to the right by \(r\) positions.

You know the array \(A\) and the integer \(r\) but you do not know \(ID\). However, you are allowed to choose the values of \(ID\) arbitrarily (as long as every element of \(ID\) is in \([1, n-1]\)). Determine the maximum possible value of sum after the WTF transform.

[1] Note: The transform is fictitious and is also known as the "Sept transform".

Hint: In the pseudo‐code, the contribution in each iteration depends on the element selected from \(A\) (or its negation after the Change step) and the rotation shifts the positions of \(A\). In the first loop, at every iteration we can choose ID so that the index equals the one giving the maximum value from the first \(n-1\) positions of the rotated array \(A\). In the second loop (where \(A\) has been negated), we choose the pair so that after adding \(1\) the index falls in \(\{2,3,\ldots,n\}\) and picks the maximal element (which is \(-\min A\) in the negated array). Note that the unknown \(ID\) links adjacent iterations but an appropriate construction always exists. Also, note that the right rotation by \(r\) positions changes the excluded position in the array and hence the attainable maximum may occasionally drop to the second best. Use these observations to calculate the answer efficiently.

inputFormat

The first line contains two integers \(n\) and \(r\) (where \(n \ge 1\) and \(1 \le r \le n\)).

The second line contains \(n\) integers \(A[1], A[2], \dots, A[n]\) separated by spaces.

outputFormat

Output a single integer: the maximum possible value of sum after performing the WTF transform.

sample

5 1
1 2 3 4 5

90