Minimum Transfer Cost in the Escalator Mansion

Piggy has built an enormous PIG building that can be regarded as a plane. On this plane there are n moving escalators, each of which is represented by a linear function (i.e. a first‐degree function) that is neither vertical nor horizontal. All escalators move toward the right (that is, in the positive direction of the \( x \)–axis).

Any two escalators that intersect have an intersection point at which you can transfer from one escalator to the other by spending \(1\,\texttt{ZMB}\). A person stands on the x₁–th escalator at the point with \( x\)–coordinate \(y_1\). Meanwhile, Piggy is located on the x₂–th escalator at the point with \( x\)–coordinate \(y_2\). Due to obstacles (see figure below), the person cannot text Piggy to come over and must walk via the escalators.

The person may ride an escalator for free, but may only move in the escalator's direction (i.e. increasing \( x \)) and may only transfer at an intersection if the intersection point is strictly to the right of his current position on that escalator. Note that when a transfer occurs, he immediately appears on the other escalator at the intersection point. Once on any escalator, he may ride it further to any later \( x \)–coordinate.

If the person is on Piggy's escalator and his current \( x \)–position is not greater than \( y_2 \), he can ride for free to reach Piggy at \( x=y_2 \). Find the minimum number of transfers (each costing \(1\,\texttt{ZMB}\)) required so that the person can reach Piggy's position. If it is impossible to do so, output \(-1\).

Intersection of two escalators:

Assume escalator \( i \) is represented by the equation \( y=k_i x+b_i \) and escalator \( j \) by \( y=k_j x+b_j \). Their intersection (if \( k_i \neq k_j \)) is at \[ x=\frac{b_j-b_i}{k_i-k_j} \] A transfer from escalator \( i \) to escalator \( j \) is possible from state \( (i,x_0) \) only if \( x=\frac{b_j-b_i}{k_i-k_j} > x_0 \).

inputFormat

The first line contains an integer \( n \) (the number of escalators).

The second line contains two numbers \( x_1 \) and \( y_1 \): the index (1–indexed) of the escalator where the person starts and his current \( x \)–coordinate.

The third line contains two numbers \( x_2 \) and \( y_2 \): the index (1–indexed) of the escalator where Piggy is and the \( x \)–coordinate of Piggy.

Then follow \( n \) lines. The \( i \)–th of these lines contains two real numbers \( k_i \) and \( b_i \) representing the escalator's equation:

[ y=k_i,x+b_i ]

It is guaranteed that no escalator is vertical or horizontal (i.e. \( k_i \neq 0 \) for all \( i \) and no two escalators are identical in orientation if they are parallel to the ground).

outputFormat

Output a single integer indicating the minimum number of transfers (each costing \(1\,\texttt{ZMB}\)) needed for the person to reach Piggy. If it is impossible, output \(-1\).

sample

3
1 1
1 10
1 0
2 0
-1 10

0

</p>