题目描述

Walltopia 是一家提供攀岩墙娱乐设施的公司。Alice 和 Bob 来到附近的一家 Walltopia 攀岩中心。

我们可以把那里的攀岩墙看成一个平面，上面有 $N$ 块人工岩点。第 $i$ 块岩点的位置为：

• 距离墙底 $y_i$ 厘米；
• 距离墙中心向右 $x_i$ 厘米，$x_i$ 可以为负数；
• 该岩点有一个湿滑系数 $s_i$。

保证不存在两块岩点位于同一位置。

Alice 想测试 Bob 的攀岩能力。她会恰好选择 $K \ge 2$ 块岩点，称为特殊岩点。为了通过测试，Bob 必须从这些特殊岩点中选择两块不同的岩点，并且能够从第一块爬到第二块。

攀爬过程中，Bob 可以使用墙上的所有岩点，不限于特殊岩点。

从岩点 $i$ 可以直接爬到岩点 $j$ 当且仅当：

并且

换句话说，Bob 只能向上爬，并且两点之间的切比雪夫距离不能超过两点湿滑系数的较大值。

请编写程序 walltopia，求最小的 $K$，使得无论 Alice 怎样选择 $K$ 块特殊岩点，Bob 总能通过测试。

如果不存在这样的 $K$，输出 $-1$。

输入格式

第一行包含一个正整数 $N$，表示岩点数量。

接下来 $N$ 行，每行包含三个整数：

表示第 $i$ 块岩点的位置和湿滑系数。

输出格式

输出一个整数，表示满足条件的最小 $K$。

如果 Bob 无论如何都无法保证通过测试，输出 -1。

数据范围

• $1 \le N \le 500$；
• $-10^6 \le x_i \le 10^6$；
• $1 \le y_i \le 10^6$；
• $1 \le s_i \le 2\times 10^6$。

子任务

只有通过该子任务及其依赖子任务的全部测试点，才能获得该子任务分数。

样例

输入

5
0 3 2
-1 5 1
4 4 3
-1 1 2
2 2 1

输出

3

说明

若 $K=2$，Alice 可以选择最后两块岩点作为特殊岩点。Bob 无法从 $(-1,1)$ 直接爬到 $(2,2)$，因为

Bob 只能从 $(-1,1)$ 爬到 $(0,3)$，之后也无法爬到 $(2,2)$，因为他必须始终向上攀爬。

可以证明，当 Alice 任意选择 $3$ 块岩点时，Bob 总能通过测试。