ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

NEERC 2011, Четвертьфинал Восточного подрегиона

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

K. Бифштексы на борту

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Авиакомпания Oceanic Airlines объявила, что с нового года у всех пассажиров трансатлантических рейсов будет возможность попробовать во время полёта знаменитые уральские бифштексы. В отличие от стандартных обедов, эти бифштексы будут готовиться прямо во время полёта, а значит, будут свежими, горячими и вкусными.
Каждый пассажир во время регистрации на рейс может указать точное время, когда ему нужно подать готовый бифштекс. Чтобы приготовить один бифштекс, нужно непрерывно жарить каждую из двух его сторон на сковороде в течение одной минуты. При этом бифштекс нельзя начать готовить раньше, чем за x минут до того, как он должен быть подан, — иначе он уже не будет таким вкусным.
К сожалению, в самолётах Oceanic Airlines есть всего одна электрическая плита и одна сковорода, на которой одновременно можно готовить не более k бифштексов. Пока на плите ничего не готовится, её можно выключить. Повар хочет выполнить заказы всех пассажиров вовремя, минимизировав время, в течение которого включена плита. Помогите ему в этом.

Исходные данные

В первой строке записаны целые числа x и k (2 ≤ x ≤ 1 000; 1 ≤ k ≤ 50). Во второй строке записано целое число n — количество заказанных бифштексов (1 ≤ n ≤ 50). В третьей строке записаны целые числа t1, …, tn, задающие моменты времени, когда должны быть поданы бифштексы (2 ≤ ti ≤ 1 000). Моменты времени упорядочены по неубыванию и отсчитываются от начала полёта.

Результат

Если повару удастся выполнить все заказы вовремя, выведите в первой строке минимальное количество минут, которое должна работать электроплита. В i-й из следующих n строк выведите два неотрицательных целых числа — моменты времени, когда нужно положить i-й бифштекс на сковороду первой и второй стороной соответственно. Бифштексы следует описывать в том же порядке, в котором они даны на входе. Если возможных ответов несколько, выведите любой из них. Если выполнить все заказы вовремя невозможно, выведите «-1».

Примеры

исходные данныерезультат
10 2
3
2 16 25
5
0 1
11 15
15 17
10 2
4
7 8 9 10
4
3 6
4 5
3 6
4 5
2 1
2
2 2
-1
Автор задачи: Алексей Самсонов
Источник задачи: NEERC 2011, Четвертьфинал Восточного подрегиона
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1895. Бифштексы на борту