B. Башни
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Как известно, все дети в Берляндии любят играть с кубиками. У маленького Пети имеется n башен, состоящих из кубиков одинакового размера. Башня под номером i представляет собой ai кубиков, поставленных друг на друга. Неустойчивостью набора башен Петя называет величину, равную разности высот самой высокой и самой низкой башни. К примеру, если Петя построил из кубиков пять башен с высотами (8, 3, 2, 6, 3), то неустойчивость этого набора равна 6 (самая высокая башня имеет высоту 8, самая низкая — высоту 2).

Мальчик хочет, чтобы неустойчивость его набора башен была как можно меньше. Все, что он может сделать, это несколько раз проделать следующую операцию: взять верхний кубик с какой-то из башен и положить его сверху на какую-то другую башню из своего набора. Обратите внимание, что Петя никогда не будет класть кубик на ту же башню, с которой тот был снят, потому что считает это пустой тратой времени.

Прежде чем отправиться в школу, мальчик успеет произвести не более k таких операций. Петя не хочет опоздать на урок, поэтому вам придется помочь ему выполнить эту задачу.

Входные данные

В первой строке через пробел записаны два целых положительных числа n и k (1 ≤ n ≤ 100, 1 ≤ k ≤ 1000) — количество башен в имеющемся наборе и максимальное число операций, которые Петя может произвести. Во второй строке через пробел записаны n целых положительных чисел ai (1 ≤ ai ≤ 104) — исходные высоты башен.

Выходные данные

В первой строке выведите через пробел два целых неотрицательных числа s и m (m ≤ k). Первое из чисел — это величина минимально возможной неустойчивости, которую можно достичь, применив не более k операций, а второе — количество операций, необходимых для этого.

Затем в m строках выведите описание каждой из операций в виде двух целых положительных чисел i и j, каждое из которых лежит в пределах от 1 до n. Они обозначают, что Петя переложил верхний кубик с i-й башни на j-ю (i ≠ j). Обратите внимание, что в процессе выполнения операций высоты некоторых башен могут стать равны нулю.

Если существует несколько корректных последовательностей операций, при которых достигается минимально возможная неустойчивость, разрешается вывести любую из них.

Примеры
Входные данные
3 2
5 8 5
Выходные данные
0 2
2 1
2 3
Входные данные
3 4
2 2 4
Выходные данные
1 1
3 2
Входные данные
5 3
8 3 2 6 3
Выходные данные
3 3
1 3
1 2
1 3
Примечание

В первом примере осуществляется два перекладывания, со второй башни на третью и со второй на первую. После этого высоты башен становятся одинаковыми и равными 6.