题目描述

题目译自 PA 2020 Runda 3 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\le n\le 5\cdot 10^5)$，表示送货计划个数。

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

输出格式

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

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

1