Optimal Clustering of Polling Data

You are given the results from a political poll of \(n\) people. For the \(i^\text{th}\) person you are given:

• \(a_i\) – the number of digits of \(\pi\) they have memorized,
• \(b_i\) – the number of hairs on their head,
• \(c_i\) – a boolean value indicating whether they will vote for Candidate X (represented as 1 for true and 0 for false).

You are to choose two real numbers \(S\) and \(T\), and sort the poll results by the measure \[ r_i = a_i \cdot S + b_i \cdot T. \] The sorted order is used to form a "cluster" of the results with \(c_i = 1\). Formally, if in the sorted order the first occurrence of a result with \(c_i=1\) is at position \(j\) and the last at position \(k\), the cluster size is \(k - j + 1\).

Because some choices of \(S\) and \(T\) may cause ties in the scores \(r_i\), assume that in the event of ties the worst‐possible ordering (i.e. the one that maximizes the cluster size) is used.

Your task is to choose \(S\) and \(T\) so that the true results (those with \(c_i=1\)) are as tightly clustered as possible. Output the minimum possible cluster size. Note that if there are no true responses, the answer is 0.

inputFormat

The first line of input contains a single integer \(n\) (the number of people). Each of the next \(n\) lines contains three space‐separated integers: \(a_i\), \(b_i\), and \(c_i\), where \(c_i\) is either 0 or 1.

outputFormat

Output a single integer: the minimum possible cluster size of the true responses, computed under worst-case tie breaking.

sample

3
3 10 1
5 2 0
2 3 1

2