sequence

题目描述

给一个序列 $A$ ，你可以进行 $k$ 次交换操作，最大化最大子段和。

输入格式

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

第二行一共 $n$ 个数，表示序列 $A$ 。

输出格式

第一行两个数，表示最大字段和的最大值，以及你进行的交换次数 $p$ 。要求 $p \leq k$ 。

接下来 $p$ 行每行两个数，表示交换的下标。

最后一行两个数，表示和最大的子段的左右端点。

样例

输入

3 3
1 -2 3

输出

4 2
1 2
2 3
2 3

数据范围

$n \leq 10^5, k \leq 10, |A_i| \leq 10^9$ 。

Subtask1 ($20\%$) ： $n \leq 10$ 。

Subtask2 ($30\%$) ： $n \leq 1000$ 。

Subtask3 ($20\%$) ： $k = 1$ 。

Subtask4 ($30\%$) ：无特殊性质。

时间限制：$1s$ 。

空间限制： $256MB$ 。