Pusheen has been dreaming about tuna sashimi! She has decided that she needs to eat more tuna in her life, so she decides to visit her favourite restaurant to eat tuna sashimi and tuna nigiri.
Pusheen decides to take her helicopter to her favourite restaurant. Due to various regulations, Pusheen is required to fix the helicopter at a specific altitude if she's not taking off or landing, so the helicopter can be effectively treated as traveling in a 2D plane. Due to fuel restrictions, Pusheen will travel only to points ~(x, y)~ with nonnegative coordinates further subject to the constraint that ~x \le X~ and ~y \le Y~.
The helicopter is a bit finicky to maneuver, so in a single second, Pusheen can only change either the velocity of the helicopter in the x-direction or the y-direction by one unit. Pusheen is not required to change the velocity of the helicopter within a second. Note that the change in velocity happens before the helicopter moves within that second - this means that at the end of every second, Pusheen is guaranteed to be at a lattice point. Pusheen can only board/disembark from the helicopter when it is not moving.
More formally, if Pusheen's location at the beginning of second ~t~ is ~(x, y)~ and her helicopter's velocity is ~(vx, vy)~, and Pusheen decides to change the velocity at the start of that second by ~(ax, ay)~, then Pusheen's location at the beginning of second ~t+1~ is ~(x+vx+ax, y+vy+ay)~ and her helicopter's velocity is ~(vx + ax, vy + ay)~. Pusheen can only board/disembark when ~vx = vy = 0~. Pusheen's helicopter will fly through all points on the line segment from ~(x, y)~ to ~(x+vx+ax, y+vy+ay)~ in that second.
It's also a windy day! Some lattice points have high winds that Pusheen must not fly through at any point in time. Help Pusheen figure out if she can get to her favourite restaurant, and figure out how quickly she can do so!
~0 \le X, Y \le 100~
~0 \le x_s, x_e, x_i \le X~
~0 \le y_s, y_e, y_i \le Y~
~(x_s, y_s) \neq (x_e, y_e)~
~0 \le N \le (X+1)(Y+1) - 2~
Pusheen's starting and ending locations will not have wind.
All ~N~ lattice points with wind are distinct.
In tests worth 1 mark, ~Y = 0~ and ~N = 0~.
In tests worth 2 additional marks, ~Y \le 1~ and ~N = 0~.
In tests worth 3 additional marks, ~N = 0~.
The first line contains three nonnegative integers, ~X~, ~Y~, and ~N~.
The next line contains two nonnegative integers, ~x_s~ and ~y_s~, representing Pusheen's starting location.
The next line contains two nonnegative integers, ~x_e~ and ~y_e~, representing the location of Pusheen's favourite restaurant.
The next ~N~ lines each contain two space-separated integers, ~x_i~ and ~y_i~, representing a lattice point with wind.
If Pusheen cannot make it to her favourite restaurant, output
-1. Otherwise, output the minimum number of seconds
needed for Pusheen to be able to make it to her favourite restaurant.
Sample Input 1
1 0 0 0 0 1 0
Sample Output 1
Sample Input 2
4 0 0 0 0 4 0
Sample Output 2
Sample Input 3
1 1 0 0 0 1 1
Sample Output 3
Sample Input 4
2 0 1 0 0 2 0 1 0
Sample Output 4