Chairs

Ian is in his FIT2004 class, and wants to ask the TA for help to solve a $67$-dimensional dynamic programming problem.

The classroom can be modelled as an $n \times m$ rectangle, with the bottom left located at $(1, 1)$, and the top right located at $(n, m)$. Note that coordinates along the edge of the rectangle are inside the classroom.

Unfortunately there are $k$ chairs blocking his way, located at distinct coordinates.

Ian, from any coordinate $(c_1, c_2)$, can move to any adjacent coordinate inside the classroom:

• $(c_1 + 1, c_2)$
• $(c_1 - 1, c_2)$
• $(c_1, c_2 + 1)$
• $(c_1, c_2 - 1)$

When moving, Ian has a set of specific interactions:

• Step from the ground onto the top of the chair, which requires $1$ unit of energy.

• Step from a chair onto the ground, which requires $1$ unit of energy.

• Step from a chair onto a chair, which does not require energy.

• Step from the ground onto the ground, which does not require energy.

All interactions take $1$ second of time.

Ian is currently at position $(a, b)$, and the TA is located at position $(c, d)$.

Since Ian values his time and energy, he would like to know the minimum energy he must use to reach the TA in at most $t$ seconds.

Input

The first line contains $n, m$.

The next line contains $a, b, c, d, k, t$.

The next $k$ lines each contain $(x_i, y_i)$, the coordinates of the $i$-th chair.

Output

Output a single number, the minimum energy that Ian must use to move from $(a, b)$ to $(c, d)$ in at most $t$ seconds, or $-1$ if Ian cannot reach the TA in time.

Constraints

• $3 \le n \cdot m \le 10^3$

• $1 \le a, c \le n$

• $1 \le b, d \le m$

• $0 \le k \le n \cdot m - 2$

• $(x_i, y_i) \neq (a, b)$

• $(x_i, y_i) \neq (c, d)$

• $(x_i, y_i)$ are distinct

• $1 \le t \le 10^4$

Example 1

3 3
1 1 3 3 3 5
1 2
2 2
3 2

2

Explanation

Ian can take the path $(1, 1) \to (2, 1) \to (2, 2) \to (2, 3) \to (3, 3)$.

Moving from $(2, 1) \to (2, 2)$ requires stepping from the ground onto a chair, which uses $1$ energy.

Moving from $(2, 2) \to (2, 3)$ requires stepping from a chair onto the ground, which uses $1$ energy.

In total, Ian uses $1 + 1 = 2$ energy, and reaches the TA within $5$ seconds.

It can be shown that this path minimises Ian's energy usage.

Example 2

3 3
1 1 1 3 2 6
1 2
2 2

0

Example 3

3 3
1 1 3 3 7 4
1 2
1 3
2 1
2 2
2 3
3 1
3 2

2