F. Kotlinforces
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Kotlinforces — веб-платформа, на которой проводятся соревнования по программированию.

На Kotlinforces планируется провести $$$n$$$ соревнований по программированию в следующие $$$m$$$ дней. Каждое соревнование проводится в несколько этапов; регламент $$$i$$$-го соревнования гласит, что оно проводится в $$$k_i$$$ этапов, и каждый этап, начиная со второго, должен пройти ровно на $$$t_i$$$ дней позже предыдущего. То есть, если первый этап $$$i$$$-го соревнования проводится в день $$$x$$$, второй этап будет проводиться в день $$$x+t_i$$$, третий — в день $$$x+2t_i$$$, ..., $$$k_i$$$-й этап (он же последний) — в день $$$x+(k_i-1)t_i$$$.

Все $$$n$$$ соревнований необходимо распланировать так, чтобы они прошли за следующие $$$m$$$ дней, и в каждый из этих $$$m$$$ дней проводилось не более одного этапа одного соревнования (два этапа разных соревнований не могут проводиться в один и тот же день).

Возможно ли провести все $$$n$$$ соревнований и соблюсти все условия?

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

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 5000$$$) — количество соревнований и количество дней, соответственно.

Затем следуют $$$n$$$ строк, в каждой из которых описывается соревнование. В $$$i$$$-й строке заданы два целых числа $$$k_i$$$ и $$$t_i$$$ ($$$2 \le k_i \le 5000$$$; $$$1 \le t_i \le 2$$$) — параметры $$$i$$$-го соревнования.

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

Если невозможно запланировать все $$$n$$$ соревнований на следующие $$$m$$$ дней так, что ни в один день не проводится более одного этапа, выведите -1.

Иначе выведите $$$n$$$ целых чисел; $$$i$$$-е из них должно быть номером дня, в который будет проводиться первый этап $$$i$$$-го соревнования, дни пронумерованы с $$$1$$$ до $$$m$$$. Если существует несколько подходящих ответов, выведите любой из них.

Примеры
Входные данные
3 7
3 2
2 2
2 2
Выходные данные
2 5 1
Входные данные
1 7
4 2
Выходные данные
1
Входные данные
1 7
5 2
Выходные данные
-1
Входные данные
2 4
2 1
2 2
Выходные данные
-1
Входные данные
2 5
2 1
2 2
Выходные данные
4 1