#P1608E. The Cells on the Paper
The Cells on the Paper
Description
On an endless checkered sheet of paper, cells are chosen and colored in three colors, where is divisible by . It turns out that there are exactly marked cells of each of three colors!
Find the largest such that it's possible to choose 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 .
- The -th rectangle contains all the chosen cells of the -th color and no chosen cells of other colors, for .
The first line of the input contains a single integer — the number of the marked cells (, is divisible by 3).
The -th of the following lines contains three integers , , (; ), where are the coordinates of the -th marked cell and is its color.
It's guaranteed that all cells in the input are distinct, and that there are exactly cells of each color.
Output a single integer — the largest number of cells you can leave.
Input
The first line of the input contains a single integer — the number of the marked cells (, is divisible by 3).
The -th of the following lines contains three integers , , (; ), where are the coordinates of the -th marked cell and is its color.
It's guaranteed that all cells in the input are distinct, and that there are exactly cells of each color.
Output
Output a single integer — the largest number of cells you can leave.
Samples
Note
In the first sample, it's possible to leave cells with indexes .
In the second sample, it's possible to leave cells with indexes .