该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

我们通过以下伪代码对数组 $\textbf 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)

其中：

• $\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}$。

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

输入格式

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

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

输出格式

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

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

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

输入输出样例 #1

输入 #1

5 3
1 -1 1 -1 1

输出 #1

10
1 1 1 2 2 3

输入输出样例 #2

输入 #2

6 5
2 5 4 1 3 5

输出 #2

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]$。