P6313 [eJOI 2018] 护照

Gleb 是来自 Innopolis 的著名编程老师，他计划接下来参加 $n$ 场编程训练营。每场训练营会在不同的国家举办。他要申请每个国家的签证。 对于第 $i$ 场训练营，Gleb 知道出发日期 $s_i$，持续时长 $len_i$，和在该国申请签证需要的时间 $t_i$。Gleb 有 $P$ 本有效的护照并且他需要决定用哪本护照来申请签证。 第 $i$ 场训练营 Gleb 将在第 $s_i$ 天早上出发，在第 $s_i+len_i-1$ 天傍晚返回。 如果要在第 $d$ 天申请签证，Gleb 当天中午必须在 Innopolis。这意味着 Gleb 在参加训练营期间不能申请签证，包括第一天和最后一天。如果一场训练营结束后紧接着 Gleb 要去参加第二场训练营，他也无法在此期间申请签证。Gleb 最早可以申请签证的时间是第 $1$ 天。 在第 $d$ 天申请完第 $i$ 个国家的签证后，Gleb 会在第 $d+t_i$ 天中午获得该国的护照（即使当天 Gleb 不在 Innopolis）。 如果第 $s_i$ 天早上 Gleb 没有相应国家的护照，他就无法参加第 $i$ 场训练营。**注意，当时护照不能在办理签证的使馆里面。** 请你帮助 Gleb 找到一种申请签证的方案，使他可以顺利参加所有的训练营。

无

无

#### 【样例解释】 #### 样例一解释  每个单元格代表一天。矩形代表某一次训练营，从某一天早上开始，在某一天晚上结束。带角的矩形某一次申请签证的过程，从某一天中午开始，在某一天中午结束。一场训练营与他对应的申请签证的过程颜色相同。 #### 样例二解释  #### 样例三解释  上面代表第一个护照，下面代表第二个护照。 --- #### 【数据规模与约定】 **本题采用多测试点捆绑测试，共 9 个子任务**。 - Subtask 1（5 pts）：$n\leq 2$，$s_i,len_i,t_i\leq 100$，所有 $t_i$ 均相等，$P=1$； - Subtask 2（8 pts）：$n\leq 10$，$s_i,len_i,t_i\leq 100$，所有 $t_i$ 均相等，$P=1$； - Subtask 3（7 pts）：$n\leq 10$，$s_i,len_i,t_i\leq 100$，所有 $t_i$ 均相等； - Subtask 4（12 pts）：$n\leq 16$，$s_i,len_i,t_i\leq 100$，$P=1$； - Subtask 5（13 pts）：$n\leq 16$，$s_i,len_i,t_i\leq 100$； - Subtask 6（15 pts）：$n\leq 16$，$s_i,len_i,t_i\leq 10^7$，$P=1$； - Subtask 7（15 pts）：$n\leq 16$，$s_i,len_i,t_i\leq 10^7$； - Subtask 8（15 pts）：$n\leq 20$； - Subtask 9（10 pts）：无特殊限制。 对于全部的测试点，保证 $1\leq n\leq 22$，$1\leq P\leq 2$，$1\leq s_i,len_i,t_i\leq 10^9$。 --- 来源：[eJOI2018](http://ejoi2018.org/) Problem B「Passports」。 说明：翻译自翻。