P11546 [BalticOI 2009] 糖果机器 (Day1)

**译自 [BalticOI 2009](http://www.csc.kth.se/contest/boi/tasks.php) Day1 T2「[Candy Machine](http://www.csc.kth.se/contest/boi/candy.pdf)」** 在糖果工厂中，有一台神秘的机器。它生产许多美味的糖果，每一个都与众不同。这个机器有一排输出槽，编号为 $1$ 到 $n$，糖果加工完毕就会从里面出来。没有人真正知道它的工作原理，但是在每一次产品计划之前，它会打印一个列表告诉老板每个糖果会在何时从哪个槽出来。 现在，老板可以安装自动收集车在每个槽下移动，以收集掉落的糖果。当然，糖果不能掉到地上，不然就会碎裂。然而，安装自动收集车的成本极其高昂，老板想尽量少安装自动收集车。 写一个程序计算接住所有糖果需要的自动收集车的数量，它应当尽可能小。此外，你的程序还需要输出每颗糖果会被哪辆收集车接住。收集车每秒可以从一个槽移动到另一个相邻的槽。在生产过程开始前，每辆收集车可以移动到他应当收集的第一个糖果的位置。

第一行，一个整数 $n$，表示将要生产的糖果的数量。 以下 $n$ 行，每行两个整数 $s_i$ 和 $t_i$，表示第 $i$ 颗糖果的输出槽和输出时间。每一组 $(s_i,t_i)$ 互不相同。

第一行，一个整数 $w$，表示接住所有糖果需要的收集车的数量（尽量小）。 收集车被编号为 $1$ 到 $w$。 以下 $n$ 行描述每颗糖果会被哪辆收集车接住。 出于此目的，这 $n$ 行每行三个整数：第 $j$ 颗糖果的输出槽 $s_j$ 和输出时间 $t_j$ 和收集车的编号 $w(j)$。表示在时刻 $t_j$ 收集车 $w(j)$ 会在槽 $s_j$ 下并接到糖果。

### 数据范围： | 数据百分比 | 限制 | | :----------: | :----------: | | $20 \%$ | $n \le 85, w \le 4$ | | $60 \%$ | $n \le 8 × 10 ^ {3}$ | | $100 \%$ | $1 \le n \le 10 ^ {5}, 0 \le s_i, t_i \le 10 ^ {9}$ |