← 返回题目列表

Codeforces · 1571/F

F. 科特林之力

中文机器翻译题面 查看原题

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