스핀 닥터

당신은 여론조사 회사에서 일한다. 복잡한 현실 문제를 몇 개의 숫자로 줄여 보여 주는 것이 이 일이고, 언제나 쉽지는 않다. 큰 선거를 앞두고 후보 X의 의뢰를 받아 $n$명을 조사했고, $i$번째 사람에게서 세 가지 값을 기록했다.

• $a_i$: 그 사람이 외우고 있는 원주율 $\pi$의 자릿수
• $b_i$: 그 사람의 머리카락 개수
• $c_i$: 그 사람이 후보 X에게 투표하면 $1$, 아니면 $0$

이제 와서 보니 이 질문이 정말 물어야 할 질문이었는지 의심스럽다. 자료에는 $a$, $b$, $c$ 사이의 상관관계가 전혀 없다. 그렇다고 의뢰인의 말을 정면으로 반박하면 일자리를 잃기 딱 좋으니, 결과가 의미 있어 보이도록 가중치를 찾기로 한다.

실수 $S$와 $T$를 하나씩 고르고, $n$개의 기록을 $a_i S + b_i T$ 값으로 정렬한다. 후보 X에게 투표할 사람이 서로 가까이 모일수록 결과가 그럴듯해 보인다. 정렬된 목록에서 $c_i = 1$인 기록 중 첫 번째의 위치를 $j$, 마지막의 위치를 $k$라고 하면 군집 크기는 $k - j + 1$이고, 이 값을 최대한 작게 만들고 싶다.

$S$와 $T$를 어떻게 고르느냐에 따라 여러 기록의 값이 같아지기도 한다. 값이 같은 기록은 서로 어떤 순서로도 놓일 수 있으므로 최악의 경우를 가정한다. 즉 그 $(S, T)$에서는 군집 크기가 가장 커지는 순서가 나온다고 본다.

가능한 모든 실수 쌍 $(S, T)$ 가운데 군집 크기가 가장 작은 값을 구하라.

첫째 줄에 조사한 사람 수 $n$ ($1 \le n \le 250000$)이 주어진다. 다음 $n$개의 줄에는 각각 정수 $a_i$ ($0 \le a_i \le 2000000$), $b_i$ ($0 \le b_i \le 2000000$), $c_i$가 주어진다. $c_i$는 그 사람이 후보 X에게 투표하면 $1$, 아니면 $0$이다. 조사한 사람 중 후보 X에게 투표하는 사람은 적어도 한 명 있다.

가능한 모든 실수 쌍 $(S, T)$ 가운데 군집 크기의 최솟값을 출력한다.