Kotlinforces 是一个举办编程竞赛的网络平台。
Kotlinforces 的工作人员被要求在接下来的 $$$m$$$ 天安排 $$$n$$$ 编程比赛。每场比赛分多个阶段进行;第$$$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$$$。如果有多个答案,请打印其中任何一个。
示例
输入 #1
3 7 3 2 2 2 2 2
输出 #1
2 5 1
输入 #2
1 7 4 2
输出 #2
1
输入 #3
1 7 5 2
输出 #3
-1
输入#4
2 4 2 1 2 2
输出#4
-1
输入 #5
2 5 2 1 2 2
输出 #5
4 1