作为世界上最受尊敬的政治民意调查公司的员工，你必须将复杂的现实问题简化为几个数字。这并不总是容易的。一场大型选举即将到来，应候选人 X 的要求，你刚刚完成了对 $n$ 个人的民意调查。你从每个人那里收集了三条信息，第 $i$ 个人的记录值为：

• $a_i$ —— 他们背诵出的 $\pi$ 的位数
• $b_i$ —— 他们头上的头发数量
• $c_i$ —— 他们是否会投票给候选人 X

不幸的是，你开始怀疑这些是否真的是最相关的问题。事实上，你无法在数据中看出 $a$、$b$ 和 $c$ 之间有任何相关性。当然，你不能直接反驳你的客户——那可是丢掉工作的捷径！

也许答案是找到某种加权公式，使结果看起来有意义。你将选择两个实数 $S$ 和 $T$，并根据度量 $a_i \cdot S + b_i \cdot T$ 对民调结果 $(a_i, b_i, c_i)$ 进行排序。如果 $c_i$ 为真的结果尽可能地聚集在一起，那么排序效果最好。更准确地说，如果 $j$ 和 $k$ 分别是 $c_i$ 为真的结果在排序后的第一个和最后一个索引，你希望最小化簇大小，即 $k - j + 1$。注意，某些 $S$ 和 $T$ 的选择会导致 $(a_i, b_i, c_i)$ 三元组之间出现平局。当这种情况发生时，你应该假设发生了最坏的排序情况（即在该 $(S, T)$ 对下使簇大小最大化的排序）。

输入格式

输入的第一行包含 $n$ ($1 \le n \le 250\,000$)，即接受调查的人数。 接下来有 $n$ 行，每行对应一个接受调查的人。每行包含整数 $a_i$ ($0 \le a_i \le 2\,000\,000$)、$b_i$ ($0 \le b_i \le 2\,000\,000$) 和 $c_i$，其中如果该人会投票给候选人 X，则 $c_i$ 为 1，否则为 0。输入保证至少有一个人会投票给候选人 X。

输出格式

显示在所有可能的 $(S, T)$ 对中，最小可能的簇大小。

样例

样例输入 1

6
0 10 0
10 0 1
12 8 1
5 5 0
11 2 1
11 3 0

样例输出 1

4

样例输入 2

10
6 1 1
0 2 0
2 1 1
6 1 1
8 2 0
4 4 0
4 0 0
2 3 1
6 1 0
6 3 1

样例输出 2

8

样例输入 3

5
5 7 0
3 4 0
5 7 0
5 7 1
9 4 0

样例输出 3

1