The Cells on the Paper

题意翻译

- 给定平面上的 $n$ 个点 $(x_i,y_i)$，每个点有一个颜色 $c_i\in\{1,2,3\}$。每种颜色的点恰好各有 $\frac{n}{3}$ 个。 - 找到最大的 $k$，使得恰好能在每个颜色中选出 $\frac{k}{3}$ 个点，可以用三个边与坐标轴平行且交集面积为 $0$ 的矩形完全覆盖每个颜色的 $\frac{k}{3}$ 个点。 - $1 \leq n \leq 10^5,|x_i|,|y_i| \leq 10^9,c_i \in\{1,2,3\},3 | n$。

题目描述

On an endless checkered sheet of paper, $ n $ cells are chosen and colored in three colors, where $ n $ is divisible by $ 3 $ . It turns out that there are exactly $ \frac{n}{3} $ marked cells of each of three colors! Find the largest such $ k $ that it's possible to choose $ \frac{k}{3} $ cells of each color, remove all other marked cells, and then select three rectangles with sides parallel to the grid lines so that the following conditions hold: - No two rectangles can intersect (but they can share a part of the boundary). In other words, the area of intersection of any two of these rectangles must be $ 0 $ . - The $ i $ -th rectangle contains all the chosen cells of the $ i $ -th color and no chosen cells of other colors, for $ i = 1, 2, 3 $ .

输入输出格式

输入格式

The first line of the input contains a single integer $ n $ — the number of the marked cells ( $ 3 \leq n \le 10^5 $ , $ n $ is divisible by 3). The $ i $ -th of the following $ n $ lines contains three integers $ x_i $ , $ y_i $ , $ c_i $ ( $ |x_i|,|y_i| \leq 10^9 $ ; $ 1 \leq c_i \leq 3 $ ), where $ (x_i, y_i) $ are the coordinates of the $ i $ -th marked cell and $ c_i $ is its color. It's guaranteed that all cells $ (x_i, y_i) $ in the input are distinct, and that there are exactly $ \frac{n}{3} $ cells of each color.

输出格式

Output a single integer $ k $ — the largest number of cells you can leave.

输入输出样例

输入样例 #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

说明

In the first sample, it's possible to leave $ 6 $ cells with indexes $ 1, 5, 6, 7, 8, 9 $ . In the second sample, it's possible to leave $ 3 $ cells with indexes $ 1, 2, 3 $ .