假设给定一个含有 $N$ 个整数的数组 $A$，一个含有 $N + 1$ 个介于区间 $[1, N - 1]$ 内整数的数组 $ID$，以及一个整数 $R$。

我们按照以下方式对数组 $A$ 进行“Warshall-Turing-Fourier 变换”^1：

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

给你数组 $A$ 和常数 $R$，但你并不知道数组 $ID$ 的具体内容。在执行上述算法后，变量 sum 的最大可能值是多少？

输入格式

第一行包含两个整数 $N$ 和 $R$（$2 \le N \le 3000$，$1 \le R < N$）。

第二行包含数组 $A$ 的元素，依次为 $A[1]$ 到 $A[N]$。这些是介于 $[-10^4, 10^4]$ 区间内的整数。

输出格式

第一行必须包含 sum 的最大值。

第二行必须包含一个由 $N + 1$ 个介于 $[1, N - 1]$ 区间内的整数组成的数组 $ID$，使得该算法输出最大和。如果存在多个这样的数组，输出其中任意一个。

如果只有第一行正确（无论是否输出了第二行），你将获得该测试点 50% 的分数。

数据范围

• 对于 20% 的数据，满足 $N \le 7$。
• 对于 60% 的数据，满足 $N \le 300$。

样例

输入样例 1

5 3
1 -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