E. The Cells on the Paper
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.
Input

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

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

Examples
Input
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
Output
6
Input
3
1 1 1
2 2 2
3 3 3
Output
3
Note

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$$$.