题目描述

On one fine day, Mr. Panda and Rar the Cat decide to go rock climbing. The rock climbing wall has $N$ rocks. The $i$-th rock is located at height $Y_i$ from the bottom of the wall and $X_i$ units right from the centre of the wall. If $X_i$ is negative then it is to the left of the centre. The positions of all rocks are different.

To test Mr. Panda's rock climbing skills, Rar the Cat decided to issue a challenge to him. The challenge is as follows:

1. Out of the $N$ rocks, Rar the Cat will pick a set of $K$ rocks, this set is called $R$.
2. In order to win the challenge, Mr. Panda first has to pick one pair of rocks $(A, B)$ from set $R$. Mr. Panda is free to choose any pair of rocks as long as $A \neq B$ and both rocks are in set $R$.
3. Mr. Panda will start from the first rock $(A)$ and try to make his way to the second rock $(B)$. He can pass through other rocks on the way from $A$ to $B$, regardless of whether the rock is in set $R$.
4. However, each rock is associated with a slippery rate $S_i$. When a rock has a high slippery rate, it is more difficult to stretch to a far away rock without slipping off. Furthermore, Rar the Cat only allows him to climb upwards. More precisely, to move from the $i$th rock to the $j$th rock, we require $\max(|X_i - X_j|, |Y_i - Y_j|) \leq \max(S_i, S_j)$ and $Y_i < Y_j$
5. Mr. Panda will win the challenge if he manages to pick one pair of rocks $(A, B)$ such that he can get from rock $A$ to rock $B$. If he fails to do that, Mr. Panda would have lost the challenge.

Refer to the sample input and output for more details.

Of course, Mr. Panda knows that there are many pairs of rocks such that the challenge cannot be completed. He wants to find the minimum $K$ such that no matter what set of rocks Rar the Cat chooses, he can always complete the challenge. He needs your help to find this value.

输入格式

Your program must read from standard input. The first line of input contains one integer $N$. The next $N$ lines contain 3 integers each. The $(i + 1)$-th line represents $X_i, Y_i, S_i$ for the $i$-th rock.

输出格式

Your program must output one line with a single integer to the standard output, which is the minimum number of rocks so that Mr. Panda can always complete the challenge. If Mr. Panda can never complete the challenge, output $-1$.

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

3

3
0 1 2000000
-1 2 2000000
1 2 2000000

3

2
0 1 1
0 5 1

-1

提示

Sample Explanation 1

When $K = 2$, there exists some subset of rocks so that Mr. Panda cannot complete the challenge. For example, if Rar the Cat chooses the rocks on $(-1, 1)$ and $(2, 2)$ to form the set $R$, Mr. Panda cannot complete the challenge. Mr. Panda cannot move from the rock on $(2, 2)$ to the rock on $(-1, 1)$ since he can only climb upward. Mr. Panda cannot move directly from the rock on $(-1, 1)$ to the rock on $(2, 2)$ since $\max(|-1 - 2|, |1 - 2|) = 3 > \max(2, 1) = 2$.

Another choice is to move indirectly from $(-1, 1)$ to $(2, 2)$. Mr. Panda can climb from the rock on $(-1, 1)$ to the rock on $(0, 3)$ since $\max(|-1 - 0|, |1 - 3|) = 2 \leq \max(2, 1) = 2$. However, he cannot move from the rock on $(0, 3)$ to the rock on $(2, 2)$ since he must climb upwards.

Moreover, it can be verified that for every set of 3 rocks, there is always a way to pick a pair of rocks so that Mr. Panda can complete the challenge. For example, if Rar the Cat picks the rocks on $(-1, 5)$, $(4, 4)$, $(-1, 1)$ to form set $R$, Mr. Panda can complete the challenge by picking the rocks on $(-1, 5)$ and $(-1, 1)$. To complete the challenge, he climbs from the rock $(-1, 1)$ to the rock on $(0, 3)$ then to the rock on $(-1, 5)$. The intermediate rocks do not need to be from $R$.

Sample Explanation 2

This testcase is only valid for subtasks 1,2 and 5.

If Rar the Cat selects the 2 rocks on height 2 (i.e. the 2nd and the 3rd rocks), Mr. Panda cannot complete the challenge since he must always climb upwards. So Mr. Panda can only guarantee that he can complete the challenge if Rar the Cat chooses all the rocks.

Sample Explanation 3

This testcase is only valid for subtasks 2,3,4 and 5.

Even if Rar the cat selects all the rocks Mr. Panda since there is no way to get from one rock to another. Thus, Mr. Panda can never complete the challenge.

Subtasks

The maximum execution time on each instance is 1.0s. Your program will be tested on sets of input instances as follows:

Subtask	Marks	$N$	Others
1	15	$1 \leq N \leq 20$	$S_i = 2 \times 10^6$ for all $i$
2	29		No other restriction
3	17	$1 \leq N \leq 500$	$X_i = 0$, $S_i = S_j$ for all $i, j$
4	19		$S_i = 1$, $Y_i$ is not a multiple of 3 for all $i$
5	20		No other restriction

For all test cases, $-10^6 \leq X_i \leq 10^6$, $1 \leq Y \leq 10^6$, $1 \leq S_i \leq 2 \times 10^6$