Задача №3678. Сушка
Тетя Люба только что постирала все белье, и теперь перед ней стоит непростая задача: как его высушить, чтобы ни одна вещь не успела испортиться. Сразу после стирки \(i\)-я постиранная вещь имеет влажность \(w_i\). Если она сушится на веревке, то за минуту ее влажность уменьшается на \(1\), а если на батарее— то на \(r\) (если влажность была меньше \(r\), то она становится равной \(0\)). Причем веревок у тети Любы много (хватает для одновременной сушки всех вещей), а батарея только одна, причем такая маленькая, что на ней нельзя сушить две вещи одновременно. \(i\)-я вещь испортится, если не высохнет за время \(d_i\). Помогите тете Любе составить план, когда какую вещь повесить на батарею.
Первая строка входного файла содержит целые числа \(n\) (\(1 \leq n \leq 10^5\)) (количество мокрых вещей) и \(r\) (\(1 \leq r \leq 10^9\)). Следующие \(n\) строк содержат описания постиранных вещей — пары чисел \(w_i\) и \(d_i\) (\(1 \leq w_i, d_i \leq 10^9\)).
Выведите план сушки в виде пар целых чисел \(t_i\) и \(k_i\), где \(t_i\) — измеренное в минутах время от начала сушки, а \(k_i\) — номер вещи, которую нужно повесить на батарею в этот момент. Выводите пары в порядке увеличения \(t_i\). Пар не должно быть больше \(100\,000\). Не выводите числа больше \(10^9\).
Если высушить все вещи невозможно, выведите слово Impossible.
3 3 2000 1000 2000 2000 2500 1500
0 1 500 3
3 3 2000 1000 2000 1000 2000 1000
Impossible