在一张无尽的方格纸上,选择 $$$n$$$ 单元格并用三种颜色着色,其中 $$$n$$$ 可以被 $$$3$$$ 整除。事实证明,三种颜色中的每一种都恰好有 $$$\frac{n}{3}$$$ 标记的单元格!
找到最大的 $$$k$$$ 以便可以选择每种颜色的 $$$\frac{k}{3}$$$ 单元格,删除所有其他标记的单元格,然后选择三个边与网格线平行的矩形,以便满足以下条件:
- 两个矩形不能相交(但它们可以共享边界的一部分)。换句话说,任意两个矩形的交集面积必须为$$$0$$$。
- 第 $$$i$$$ 个矩形包含所有选定的第 $$$i$$$ 颜色的单元格,并且不包含其他颜色的选定单元格,因为 $$$i = 1, 2, 3$$$。
输入
输入的第一行包含一个整数 $$$n$$$ — 标记单元格的数量($$$3 \leq n \le 10^5$$$,$$$n$$$ 可以被 3 整除)。
以下 $$$n$$$ 行中的第 $$$i$$$ 包含三个整数 $$$x_i$$$、$$$y_i$$$、$$$c_i$$$ ($$$|x_i|,|y_i| \leq 10^9$$$; $$$1 \leq c_i \leq 3$$$),其中$$$(x_i, y_i)$$$ 是第 $$$i$$$ 个标记单元格的坐标,$$$c_i$$$ 是其颜色。
保证输入中的所有单元格 $$$(x_i, y_i)$$$ 都是不同的,并且每种颜色恰好有 $$$\frac{n}{3}$$$ 个单元格。
输出
输出一个整数 $$$k$$$ — 您可以留下的最大单元格数。
示例
输入 #1
9 2 3 1 4 1 2 2 1 3 3 4 1 5 3 2 4 4 3 2 4 1 5 2 2 3 5 3
输出 #1
6
输入 #2
3 1 1 1 2 2 2 3 3 3
输出 #2
3
注意
在第一个示例中,可以保留索引为 $$$1, 5, 6, 7, 8, 9$$$ 的 $$$6$$$ 单元格。
在第二个示例中,可以保留索引为 $$$1, 2, 3$$$ 的 $$$3$$$ 单元格。