给定一个长度为 $N$ 的整数数组 $A_i$，你需要在这个数组中找到一个区间，使得该区间内元素的和最大。然而，在选择区间之前，你最多可以进行 $K$ 次交换操作。每次交换操作可以使数组中的两个元素交换位置。

数组中的区间是指其任意连续元素的集合。

输入格式

输入的第一行包含两个整数：$N$ — 数组中的元素个数（$1 \le N \le 100\,000$），$K$ — 最大允许的交换次数（$0 \le K \le 10$）。

第二行依次列出数组 $A_i$ 的元素。所有的 $A_i$ 均为整数，其绝对值不超过 $10^9$。

保证 $A_i$ 中至少包含一个正数。

输出格式

输出的第一行必须包含两个整数：$S$ — 区间内元素的最大和，以及 $M$ — 实际进行的交换次数（$0 \le M \le K$）。

接下来的 $M$ 行必须按执行顺序描述所有的交换操作。对于第 $j$ 次交换，输出两个整数 $u_j$ 和 $v_j$，表示要交换值的数组中的两个位置（$1 \le u_j \ne v_j \le N$）。数组中的位置从 $1$ 开始连续编号。

最后一行必须包含计算出最大和的区间，用两个整数描述：$L$ 表示属于该区间的数组最左侧位置的索引，$R$ 表示属于该区间的数组最右侧位置的索引（$1 \le L \le R \le N$）。

样例

输入样例 1

3 2
1 2 3

输出样例 1

6 0
1 3

输入样例 2

3 3
1 -2 3

输出样例 2

4 2
1 2
2 3
2 3

输入样例 3

3 0
1 -2 3

输出样例 3

3 0
3 3