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

Input

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

Output

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

Input

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

Output

0

Example 3

Input

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

Output

2