题目描述

你有一个长度为 $n$ 的数组 $\textbf A$，一个值域为 $[1,n-1]$ 的长度为 $n+1$ 的数组 $\textbf{ID}$ 和一个整数 $r$。

我们通过以下伪代码对数组 $\textbf A$ 进行 Warshall-Turing-Fourier 变换 $^\textsf{[1]}$：

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)

其中：

• $\texttt{Change}(\textbf A)$ 表示把数组 $\textbf A$ 中所有元素分别改成它们的相反数。
• $\texttt{Rorate}(\textbf A,r)$ 表示把数组 $\textbf A$ 复制两遍得到数组 $\textbf B$，取 $\textbf B[n-r+1,2n-r]$ 代替数组 $\textbf A$。
  即向右旋转 $R$ 个位置。

你已经知道数组 $\textbf A$ 和整数 $r$，但你并不知道数组 $\textbf{ID}$。

你需要求出 WTF 变换后伪代码中 $\text{sum}$ 可能的最大值。

$\textsf{[1]}$：实际上并不存在，当然也可以叫做「Sept 变换」。

输入格式

第一行两个整数 $n,r$。

接下来一行 $n$ 个整数，表示数组 $\textbf A$。

输出格式

第一行一个整数，即伪代码中 $\text{sum}$ 可能的最大值。

第二行 $n+1$ 个整数，即使得 $\text{sum}$ 值最大的 $\textbf{ID}$ 数组。

如果存在多组解，输出任意一种。

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

提示

判分方式

如果输出只有第一行正确，可以得到 $50\%$ 的分数。

但你必须保证第二行有 $\bm{n+1}$ 个符合要求的数。

数据规模与约定

本题采用 Special Judge。

• 对于 $20\%$ 的数据，有 $n\le 7$。
• 对于 $60\%$ 的数据，有 $n\le 300$。
• 对于 $100\%$ 的数据，有 $2\le n\le 3\times 10^3$，$1\le r\le n$，$\textbf A[i]\in[-10^4,10^4]$。

你需要保证你构造的 $\textbf{ID}[i]\in[1,n-1]$。

说明

按原题配置，满分 160 分。

译自 COCI 2014-2015 Contest #6 Task F WTF。