Alee

Parcul oraşului a fost neglijat mult timp, astfel că acum toate aleile sunt distruse. Prin urmare, anul acesta Primăria şi-a propus să facă reamenajări.

Parcul are forma unui pătrat cu latura de $n$ metri şi este înconjurat de un gard care are exact două porţi. Proiectanţii de la Primărie au realizat o hartă a parcului şi au trasat pe hartă un caroiaj care împarte parcul în $n \times n$ zone pătrate cu latura de $1$ metru. Astfel harta parcului are aspectul unei matrice pătratice cu $n$ linii şi $n$ coloane. Liniile şi respectiv coloanele sunt numerotate de la $1$ la $n$. Elementele matricei corespund zonelor pătrate de latură $1$ metru. O astfel de zonă poate să conţină un copac sau este liberă.

Edilii oraşului doresc să paveze cu un număr minim de dale pătrate cu latura de $1$ metru zonele libere (fără copaci) ale parcului, astfel încât să se obţină o alee continuă de la o poartă la alta.

Cerinţă

Scrieţi un program care să determine numărul minim de dale necesare pentru construirea unei alei continue de la o poartă la cealaltă.

Date de intrare

Fişierul de intrare alee.in conţine pe prima linie două valori naturale $n$ şi $m$ separate printr-un spaţiu, reprezentând dimensiunea parcului, respectiv numărul de copaci care se găsesc în parc. Fiecare dintre următoarele $m$ linii conţine câte două numere naturale $x$ şi $y$ separate printr-un spaţiu, reprezentând poziţiile copacilor în parc ($x$ reprezintă linia, iar $y$ reprezintă coloana zonei în care se află copacul). Ultima linie a fişierului conţine patru numere naturale $x_1 \ y_1 \ x_2 \ y_2$, separate prin câte un spaţiu, reprezentând poziţiile celor două porţi ($x_1$, $y_1$ reprezintă linia şi respectiv coloana zonei ce conţine prima poartă, iar $x_2$, $y_2$ reprezintă linia şi respectiv coloana zonei ce conţine cea de a doua poartă).

Date de ieșire

Fişierul de ieşire alee.out va conţine o singură linie pe care va fi scris un număr natural care reprezintă numărul minim de dale necesare pentru construirea aleii.

Restricții și precizări

• $1 \leq n \leq 175$
• $1 \leq m < n \cdot n$
• Aleea este continuă dacă oricare două plăci consecutive au o latură comună.
• Aleea începe cu zona unde se găseşte prima poartă şi se termină cu zona unde se găseşte cea de a doua poartă.
• Poziţiile porţilor sunt distincte şi corespund unor zone libere.
• Pentru datele de test există întotdeauna soluţie.

Exemplu

alee.in

8 6 
2 7
3 3
4 6
5 4
7 3
7 5 
1 1 8 8

alee.out

15

Explicație

O modalitate de a construi aleea cu număr minim de dale este:

OOO-----
--OO--x-
--xO----
---OOx--
---xO---
----OO--
--x-xOO-
------OO

(cu X am marcat copacii, cu - zonele libere, iar cu O dalele aleii).