Spin Doctor

You work for a polling company, where the job is to take complicated real world questions and boil them down to a few numbers. It is not always easy. A big election is coming, and at the request of Candidate X you have just polled $n$ people. For the $i$-th person you wrote down three values:

• $a_i$, the number of digits of $\pi$ that person has memorized
• $b_i$, the number of hairs on that person's head
• $c_i$, which is $1$ if the person will vote for Candidate X and $0$ otherwise

By now you doubt that these were the most useful questions to ask. The data shows no correlation between $a$, $b$ and $c$. Contradicting the client is a good way to lose the job, so instead you look for a weighting that makes the numbers look meaningful.

Pick two real numbers $S$ and $T$ and sort the $n$ records by the measure $a_i S + b_i T$. The sorted list looks best when the people who will vote for Candidate X sit close together. Let $j$ and $k$ be the positions of the first and the last record with $c_i = 1$ in the sorted list. The cluster size is $k - j + 1$, and you want it as small as possible.

Some choices of $S$ and $T$ give several records the same measure. Records with the same measure can appear in any relative order, so assume the worst case happens: for that pair $(S, T)$ you get the ordering that makes the cluster size as large as possible.

Find the smallest cluster size over all pairs $(S, T)$.

The first line contains $n$ ($1 \le n \le 250000$), the number of people polled. Each of the next $n$ lines contains three integers $a_i$ ($0 \le a_i \le 2000000$), $b_i$ ($0 \le b_i \le 2000000$) and $c_i$, where $c_i$ is $1$ if that person will vote for Candidate X and $0$ otherwise. At least one of the polled people will vote for Candidate X.

Print the smallest cluster size over all pairs of real numbers $(S, T)$.