Description

$\texttt{piggy}$ built an extremely huge $\texttt{PIG}$ building, which can be seen as a plane. On this plane there are $n$ infinitely long escalators that are neither perpendicular nor parallel to the ground. They can be seen as linear functions, and all of them go to the right, i.e. in the positive direction of the $x$ axis.

At the intersection point of two escalators, you can transfer by paying $1 \ \texttt{ZMB}$.

Someone wants to text $\texttt{piggy}$ to ask $\texttt{piggy}$ to come to find him.

However:

So he can only walk over to find $\texttt{piggy}$.

He is currently at the point with $x$-coordinate $y_1$ on the $x_1$-th escalator.

$\texttt{piggy}$ is at the point with $x$-coordinate $y_2$ on the $x_2$-th escalator.

What is the minimum cost in $\texttt{ZMB}$ for him to get there?

Input Format

The first line contains a positive integer $n$.

The second line contains four integers $x_1, y_1, x_2, y_2$.

The next $n$ lines: the $i$-th line contains two numbers $k_i, b_i$, meaning the escalator is given by $y = k_i x + b_i$.

Output Format

Output the minimum cost in $\texttt{ZMB}$. If it is impossible to reach, output -1.

1
1 1 1 2
50 -30

0

2
1 2 2 2
1 0
2 0

-1

2
1 -1 2 1
1 0
2 0

1

Hint

This problem uses subtasks.

$\sf Subtask1(20pts)$: $1 \le n \le 10$.

$\sf Subtask2(30pts)$: $1 \le n \le 1000$.

$\sf Subtask3(50pts)$: $1 \le x_1, x_2 \le n \le 10^5$, $-10^3 \le y_1, y_2, k_i, b_i \le 10^3$.

Escalators are numbered starting from $1$.

Translated by ChatGPT 5