Bajtazar 是一家配送公司物流专员。他所在城市的道路网由水平街道（从西向东延伸）和垂直大道（从南向北延伸）组成。每相邻的一对街道和大道之间相距一公里。街道按从南到北的顺序用整数编号，大道按从西到东的顺序用整数编号。第 $i$ 条大道和第 $j$ 条街道的交叉口可表示为 $(i, j)$。你可以假设对于任何整数，都存在对应编号的街道和大道。

Bajtazar 计划了明天 $n$ 次配送；第 $i$ 次配送将由一辆车完成，该车在时刻 $t_i$ 从车库出发，并以每单位时间一公里的恒定速度沿街道或大道行驶。配送分为两种类型：第一类配送的车库位于交叉口 $(w_i, 0)$，车辆沿第 $w_i$ 条大道向北行驶；第二类配送的车库位于交叉口 $(0, w_i)$，车辆沿第 $w_i$ 条街道向东行驶。根据计划，每个车库在任何时刻最多只有一辆车出发。

车辆无需停车——在经过相应建筑物时，司机只需抛下包裹即可。但存在一个问题：如果两辆配送车在同一时刻出现在同一个交叉口，则可能会发生碰撞。Bajtazar 非常希望避免这种情况。遗憾的是，他唯一能做的就是完全取消某些配送。因此，他希望选择取消最少数量的配送，使得剩余的配送中，没有任何两辆车会在同一时刻出现在同一个交叉口。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$)，表示计划的配送次数。

接下来的 $n$ 行包含计划配送的描述；第 $i$ 行包含三个整数 $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$)，分别表示第 $i$ 次配送的类型、车库位置和出发时间。

输出格式

输出一个整数，表示需要取消的最少配送次数。

样例

输入 1

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

输出 1

1

说明 1

尝试执行所有四次配送会导致第一辆车和第二辆车在时刻 5 于交叉口 $(5, 3)$ 发生碰撞。取消第一次配送后，第二辆车和第四辆车仍会在时刻 7 于交叉口 $(7, 3)$ 发生碰撞。而取消第二次配送后，剩余的车辆均不会发生碰撞。