「PA 2020」Samochody dostawcze

题目描述

Byteasar 是一家向商店运送物资的公司的后勤人员。在他公司所在的城市里，道路网由横向的街（从西到东）和纵向的道（从南到北）组成。每一对相邻的街和相邻的道都相距一公里。我们把街按从南到北的顺序编号，把道按从西到东的顺序编号。我们将第 $i$ 条道和第 $j$ 条街的交叉点记为 $(i,j)$。你可以假设，对于任何一个整数，都存在一条街的编号为 $j$ 和一条道的编号为 $i$。

Byteasar 明天安排了 $n$ 次送货；第 $i$ 次送货将由一辆货车在时刻 $t_i$ 离开车库，以每时间单位一公里的恒定速度沿街或道行驶。每次送货可以是两种类型中的一种：

• 对于送货类型一，车库在路口 $(w_i,0)$，货车沿道 $w_i$ 向北行驶；
• 对于送货类型二，车库在路口 $(0,w_i)$，货车沿街 $w_i$ 向东行驶。

根据计划，每个车库在任何时刻最多只有一辆车离开。

货车不必停下来——驶过收货地点时，司机只需放下要送的包裹。然而，有一个问题，如果两辆货车发现他们同一时刻在同一个十字路口，就很可能会发生碰撞。Byteasar 非常希望避免这种情况。不幸的是，他唯一能做的就是取消一些送货计划。因此，他希望取消尽可能少的送货计划，以便剩下的车中没有任何两辆车同一时刻在同一个十字路口。

输入格式

第一行一个整数 $n$ ($1 \leq n \leq 5 \cdot 10^5$)，表示送货计划个数。

接下来 $n$ 行，每行三个整数 $r_i, w_i, t_i$ ($r_i \in \{1,2\}, 1 \leq w_i \leq 10^6, 0 \leq t_i \leq 10^6$)，分别表示类型，车库位置和出发时间。

输出格式

输出一个整数，表示最少取消的送货计划数。

样例

输入

4
1 5 2
2 3 0
2 3 6
1 7 4

输出

1

如果四份货物都送出，则第一和第二辆车会在时刻 $5$，在路口 $(5,3)$ 相撞。如果取消第一个送货计划，则第二和第四辆车会在时刻 $7$，在路口 $(7,3)$ 相撞。如果取消第二个送货计划，那么所有车都不会相撞了。