← 返回题目列表

Codeforces · 1608/E

E. 纸上的细胞

中文机器翻译题面 查看原题

在一张无尽的方格纸上,选择 $$$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$$$ 单元格。