Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Сушка

(Время: 1 сек. Память: 16 Мб Сложность: 59%)

Тетя Люба только что постирала все белье и теперь перед ней стоит непростая задача - как его высушить, чтобы ни одна вещь не успела испортиться. Сразу после стирки, i-я постиранная вещь имеет влажность wi. Если она сушится на веревке, то за минуту ее влажность уменьшается на 1, а если на батарее - то на r (если влажность была меньше r, то она становится равной 0). Причем веревок у тети Любы много (хватает для одновременной сушки всех вещей), а батарея только одна, причем такая маленькая, что на ней нельзя сушить две вещи одновременно. i-я вещь испортится, если не высохнет за время di. Помогите тете Любе составить план, когда какую вещь повесить на батарею.

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

Первая строка входного файла INPUT.TXT содержит целые числа n (1 ≤ n ≤ 105) - количество мокрых вещей, и r (1 ≤ r ≤ 109). Следующие n строк содержат описания постиранных вещей – пары чисел wi и di (1 ≤ wi, di ≤ 109).

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

В выходной файл OUTPUT.TXT выведите план сушки в виде пар целых чисел ti и ki, где ti - время в минутах от начала сушки, а ki - номер вещи, которую нужно повесить на батарею в этот момент. Выводите пары в порядке увеличения ti. Пар не должно быть больше 105. Не выводите числа больше 109. Если высушить все вещи невозможно, выведите слово «Impossible».

Примеры

INPUT.TXTOUTPUT.TXT
13 3
2000 1000
2000 2000
2500 1500
0 3
500 1
1000 3
23 3
2000 1000
2000 1000
2000 1000
Impossible

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483