Amphiphilic Carbon Molecules

Shanghai Hypercomputers, the world's largest computer-chip manufacturer, has invented a new class of nanoparticles called Amphiphilic Carbon Molecules (ACMs). ACMs are semiconductors, so each one can act as either a conductor or an insulator of electrons — a property that is very valuable to the chip industry. They are also amphiphilic: part of every molecule is hydrophilic while the rest is hydrophobic. Hydrophilic ACMs dissolve in polar solvents (such as water) but not in nonpolar solvents (such as acetone). Hydrophobic ACMs behave in the opposite way — they dissolve in acetone but not in water. An ACM dissolved in either solvent can be used in the chip-manufacturing process.

As a materials engineer, your job is to dissolve as many ACM particles as possible from a batch scattered on your workbench. To keep the two solutions from mixing, you place a single straight Insulating Carbon Partition Card (ICPC) on the bench; it is long enough to completely separate the particles into two sides. You then pour water on one side of the card and acetone on the other side.

Fig. 1

A particle dissolves when:

• it is a hydrophilic particle lying on the water side, or
• it is a hydrophobic particle lying on the acetone side, or
• it lies exactly on the partition card — a particle directly under the card sits on the border and dissolves regardless of its type.

A hydrophilic particle on the acetone side, or a hydrophobic particle on the water side, does not dissolve.

A digital camera above the bench reports the exact position and type of every particle as points in a 2D picture, and the partition card appears as a single straight line. Decide where to place the line so that the number of dissolved particles is as large as possible.

Fig. 2

The input contains several test cases. Each test case begins with a line containing an integer $N$, the number of ACM particles. Each of the next $N$ lines contains three integers $x$, $y$, $r$: $(x, y)$ is the position of a particle in the 2D picture, and $r$ is its type — $0$ for hydrophilic or $1$ for hydrophobic. The absolute values of $x$ and $y$ are at most $10000$, and $N$ is at most $1000$. There are at most $10$ test cases. A line containing $N = 0$ marks the end of the input and is not processed.

Figure 2 above shows the particle positions and an optimal partition-card placement for the third example below.

For each test case, print a single line containing one integer: the maximum possible number of dissolved ACM particles.