A14743 | The Cells on the Paper

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.