21657번 - Парк аттракционов 스페셜 저지다국어

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

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

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

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

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

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

Числа ti лежат в пределах от 1 до 100, N > M.