#P1608E. The Cells on the Paper

    ID: 317 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>binary searchimplementationsortings*2800

The Cells on the Paper

Description

On an endless checkered sheet of paper, nn cells are chosen and colored in three colors, where nn is divisible by 33. It turns out that there are exactly n3\frac{n}{3} marked cells of each of three colors!

Find the largest such kk that it's possible to choose k3\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 00.
  • The ii-th rectangle contains all the chosen cells of the ii-th color and no chosen cells of other colors, for i=1,2,3i = 1, 2, 3.

The first line of the input contains a single integer nn — the number of the marked cells (3n1053 \leq n \le 10^5, nn is divisible by 3).

The ii-th of the following nn lines contains three integers xix_i, yiy_i, cic_i (xi,yi109|x_i|,|y_i| \leq 10^9; 1ci31 \leq c_i \leq 3), where (xi,yi)(x_i, y_i) are the coordinates of the ii-th marked cell and cic_i is its color.

It's guaranteed that all cells (xi,yi)(x_i, y_i) in the input are distinct, and that there are exactly n3\frac{n}{3} cells of each color.

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

Input

The first line of the input contains a single integer nn — the number of the marked cells (3n1053 \leq n \le 10^5, nn is divisible by 3).

The ii-th of the following nn lines contains three integers xix_i, yiy_i, cic_i (xi,yi109|x_i|,|y_i| \leq 10^9; 1ci31 \leq c_i \leq 3), where (xi,yi)(x_i, y_i) are the coordinates of the ii-th marked cell and cic_i is its color.

It's guaranteed that all cells (xi,yi)(x_i, y_i) in the input are distinct, and that there are exactly n3\frac{n}{3} cells of each color.

Output

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

Samples

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

Note

In the first sample, it's possible to leave 66 cells with indexes 1,5,6,7,8,91, 5, 6, 7, 8, 9.

In the second sample, it's possible to leave 33 cells with indexes 1,2,31, 2, 3.