Kotlinforces
Contest: Kotlin Heroes: Episode 8
Difficulty rating: 2000
Tags: *special, constructive algorithms, dp

Kotlinforces is a web platfrom that hosts programming competitions.

The staff of Kotlinforces is asked to schedule $$$n$$$ programming competitions on the next $$$m$$$ days. Each competition is held in multiple stages; the regulations of the $$$i$$$-th competition state that this competition should consist of exactly $$$k_i$$$ stages, and each stage, starting from the second one, should be scheduled exactly $$$t_i$$$ days after the previous stage. In other words, if the first stage of the $$$i$$$-th competition is scheduled on day $$$x$$$, the second stage should be scheduled on day $$$x+t_i$$$, the third stage — on day $$$x+2t_i$$$, ..., the $$$k_i$$$-th stage (which is the last one) — on day $$$x+(k_i-1)t_i$$$.

All $$$n$$$ competitions should be scheduled in such a way that they start and finish during the next $$$m$$$ days, and on any of these $$$m$$$ days, at most one stage of one competition is held (two stages of different competitions should not be scheduled on the same day).

Is it possible to schedule all $$$n$$$ competitions to meet these constraints?

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 5000$$$) — the number of competitions and the number of days, respectively.

Then $$$n$$$ lines follow, each describing a competition which should be scheduled. The $$$i$$$-th line contains two integers $$$k_i$$$ and $$$t_i$$$ ($$$2 \le k_i \le 5000$$$; $$$1 \le t_i \le 2$$$) — the parameters of the $$$i$$$-th competition.

Output format:
If it is impossible to schedule all $$$n$$$ competitions on the next $$$m$$$ days so that there is at most one stage during each day, print -1.

Otherwise, print $$$n$$$ integers. The $$$i$$$-th integer should represent the day when the first stage of the $$$i$$$-th competition is scheduled; days are numbered from $$$1$$$ to $$$m$$$. If there are multiple answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
3 7
3 2
2 2
2 2

Example output:
2 5 1

Example input:
1 7
4 2

Example output:
1

Editorial:
Notice that it doesn't make sense to not put the competitions with $$$t=1$$$ not next to each other or start them from day $$$1$$$.
So the problem is to place competitions with $$$t=2$$$ over the remaining $$$m - cnt_1$$$ days.
Any competition with $$$t=2$$$ takes up either consecutive odd days or consecutive even days. We can count the number of remaining odd and even days.
The issue is to decide for each competition which of these two it should take up. So we want the total length of the competitions in the odd days to not exceed $$$\mathit{cnt}_{odd}$$$ and the total length of the competitions in the even days to not exceed $$$\mathit{cnt}_{even}$$$.
If the total length of the competitions exceeds $$$\mathit{cnt}_{odd} + \mathit{cnt}_{even}$$$, then there is no way for sure. Otherwise, you can fill up the odd days as much as possible and leave the remaining competitions for the even days.
That can be done with a $$$dp_{i,j}$$$ — is it possible to fill $$$j$$$ odd days with some subset of the first $$$i$$$ competitions. You should get AC with $$$O(nm)$$$ memory, but it's possible to make it $$$O(m)$$$.
Overall complexity: $$$O(nm)$$$.