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
| Kotlin Heroes: Episode 8 |
|---|
| Закончено |
