|
Сушка
(Время: 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.TXT | OUTPUT.TXT |
|---|
| 1 | 3 3
2000 1000
2000 2000
2500 1500 | 0 3
500 1
1000 3 |
| 2 | 3 3
2000 1000
2000 1000
2000 1000 | Impossible |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
