Задача E. Парк аттракционов ≡

Автор:Жюри ROI-2011   Ограничение времени:2 сек
Входной файл:attract.in   Ограничение памяти:256 Мб
Выходной файл:attract.out  
Максимальный балл:100  

Условие

В городе π недавно построили парк аттракционов, в котором есть павильон игровых автоматов. Каждый из автоматов рассчитан на одного человека. В программе Всероссийской олимпиады планируется посещение этого павильона.

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

Время перемещения участников между автоматами, а также между автобусом и павильоном считается равным нулю. Каждый из участников в любой момент времени может как играть на автомате, так и ждать своей очереди, например, гуляя по парку. Для каждого из M (M ≤ N) автоматов известно время игры на нём ti (1 ≤ i ≤ M). Прервать начатую игру на автомате невозможно. Автобус привозит всех участников олимпиады в парк одновременно в нулевой момент времени.

Требуется написать программу, которая по заданным числам N, M и ti определяет оптимальное расписание игры на автоматах для каждого из участников.

Формат входного файла

В первой строке входного файла содержатся два числа: N и M (1 ≤ M ≤ N ≤ 100). Во второй строке заданы M целых чисел ti (1 ≤ ti ≤ 100), каждое из которых задаёт время игры на i-м автомате (1 ≤ i ≤ M). Числа в строке разделяются одиночными пробелами.

Формат выходного файла

В первой строке необходимо вывести одно число — минимально возможное время отправления автобуса из парка аттракционов. Далее необходимо вывести N расписаний игр на автоматах, по одному для каждого из участников. Каждое расписание описывается в (M + 1) строках, первая из которых — пустая, а далее следуют M строк, описывающих автоматы в порядке их посещения этим участником. Посещение автомата описывается двумя целыми числами: номером автомата j (1 ≤ j ≤ M) и временем начала игры участника на этом автомате.

Примеры тестов

№ Входной файл (attract.in) Выходной файл (attract.out)
1 
2 1
2
 
4

1 0

1 2
2 
3 2
2 1
 
6

1 0
2 2

1 2
2 4

2 0
1 4
0.036s 0.006s 15