E. Elevations of Salvador
time limit per test
0.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The city of Salvador, in Bahia, is famously hilly, and its blocks are laid out on a regular grid. We model the whole neighborhood as the infinite integer grid: every grid point has integer coordinates and is a corner where blocks meet.

A courier from a UFBA student delivery group starts at corner $$$A = (a_x, a_y)$$$ and must reach corner $$$B = (b_x, b_y)$$$. In one minute the courier can walk one block to an orthogonally adjacent corner, that is, from $$$(x, y)$$$ to any of $$$(x+1, y)$$$, $$$(x-1, y)$$$, $$$(x, y+1)$$$ or $$$(x, y-1)$$$. Each such move costs exactly $$$1$$$ minute.

Besides the ordinary grid, Salvador also has $$$M$$$ special perfectly straight slanted streets, each running at exactly $$$45$$$ degrees. Each slanted street is described by a pair $$$(k, d)$$$ with $$$d \in \{+1, -1\}$$$:

  • If $$$d = +1$$$, the street is the line $$$y = x + k$$$. While standing on a grid point of this street, the courier may, in addition to the ordinary moves, step to $$$(x+1, y+1)$$$ or $$$(x-1, y-1)$$$ in one minute, staying on the street.
  • If $$$d = -1$$$, the street is the line $$$y = -x + k$$$. While standing on a grid point of this street, the courier may, in addition to the ordinary moves, step to $$$(x+1, y-1)$$$ or $$$(x-1, y+1)$$$ in one minute, staying on the street.

These extra slanted steps are available only while the courier is currently on a grid point that belongs to the corresponding slanted street. Every move, ordinary or slanted, costs exactly $$$1$$$ minute.

For example, suppose $$$A = (0, 0)$$$, $$$B = (3, 3)$$$, and there is a single slanted street $$$(k, d) = (0, +1)$$$, the line $$$y = x$$$. The courier can ride this street from $$$A$$$ to $$$B$$$ in $$$3$$$ minutes:

Help the group find the minimum number of minutes needed to travel from $$$A$$$ to $$$B$$$.

Input

The first line contains four integers $$$a_x$$$, $$$a_y$$$, $$$b_x$$$ and $$$b_y$$$ ($$$-10^{9} \leq a_x, a_y, b_x, b_y \leq 10^{9}$$$), the coordinates of $$$A$$$ and $$$B$$$.

The second line contains a single integer $$$M$$$ ($$$0 \leq M \leq 2 \times 10^{5}$$$), the number of slanted streets.

Each of the next $$$M$$$ lines contains two integers $$$k$$$ and $$$d$$$ ($$$-2 \times 10^{9} \leq k \leq 2 \times 10^{9}$$$, $$$d \in \{-1, +1\}$$$), describing one slanted street as defined above.

Output

Output a single integer: the minimum number of minutes needed to travel from $$$A$$$ to $$$B$$$.

Examples
Input
0 0 3 3
1
0 1
Output
3
Input
0 0 2 3
0
Output
5
Input
0 0 5 1
1
0 1
Output
5
Note

Explanation for example 1

The slanted street with $$$k = 0$$$, $$$d = +1$$$ is the line $$$y = x$$$, which passes through both $$$A = (0, 0)$$$ and $$$B = (3, 3)$$$. The courier rides it with three slanted steps $$$(0,0) \to (1,1) \to (2,2) \to (3,3)$$$, for a total of $$$3$$$ minutes.

Explanation for example 2

There are no slanted streets ($$$M = 0$$$), so the courier can only move one block at a time. A shortest such walk from $$$A = (0, 0)$$$ to $$$B = (2, 3)$$$ takes $$$5$$$ minutes.

Explanation for example 3

The slanted street with $$$k = 0$$$, $$$d = +1$$$ is the line $$$y = x$$$, and $$$A = (0, 0)$$$ lies on it while $$$B = (5, 1)$$$ does not. The courier takes one slanted step $$$(0, 0) \to (1, 1)$$$ and then walks $$$(1,1) \to (2,1) \to (3,1) \to (4,1) \to (5,1)$$$, for a total of $$$5$$$ minutes.