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

Открытый чемпионат УрГУ 2010

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

A. Парикмахер армии магов

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Пётр, избранный лидером новой армии магов, столкнулся с проблемой. У всех магов, призванных в армию, были шикарные бороды, что совершенно неприемлемо для солдат. Поэтому Пётр приказал всем новобранцам как можно быстрее сбрить бороду. Конечно, все маги отказались сделать это, сославшись на то, что им неизвестно ни одно заклинание бритья. К счастью, в Королевстве нашёлся маг-парикмахер Цирюльникус, согласившийся побрить всех новобранцев.
С помощью заклинания «Fusion Power» Цирюльникус за одну минуту может сбрить бороду не более чем у k магов. Для достижения полного эффекта каждый маг должен попасть под действие заклинания два раза: первое заклинание бреет чисто, второе — ещё чище. Пётр назначил каждому новобранцу время, когда тот обязан явиться к Цирюльникусу. Увы, дисциплина в новой армии пока хромает, поэтому каждый маг, хоть и придёт вовремя, но просидит у Цирюльникуса ровно столько, на сколько ему хватит терпения, а затем исчезнет.
Определите, сможет ли Цирюльникус сбрить бороду у всех магов новой армии, прежде чем они исчезнут.

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

В первой строке через пробел записаны целые числа n и k (1 ≤ n, k ≤ 100) — количество новобранцев в армии и количество магов, к которым Цирюльникус может одновременно применить своё заклинание. В i-й из следующих n строк через пробел записаны целые числа ti и si (0 ≤ ti ≤ 1000; 2 ≤ si ≤ 1000) — время в минутах, к которому i-й маг должен явиться к Цирюльникусу, и время в минутах, которое он готов там провести, включая время бритья.

Результат

Если Цирюльникус сможет сбрить бороду у всех магов, выведите в первой строке «Yes», а в i-й из следующих n строк выведите пару целых чисел pi, qi — моменты времени, в которые Цирюльникус должен применить заклинание к i-му магу (tipi < qiti + si − 1). Если хотя бы один маг исчезнет раньше, чем будет полностью побрит, выведите в единственной строке «No».

Примеры

исходные данныерезультат
3 2
1 3
1 3
1 3

Yes
1 2
1 3
2 3
2 1
1 3
1 3
No
Автор задачи: Магаз Асанов
Источник задачи: XV Открытый командный чемпионат УрГУ по программированию
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1774. Парикмахер армии магов