Cerința

Eroul nostru Susan se află într-un turn de formă cubică, de latură n. El dorește să ajungă la comoara ascunsă în interiorul turnului. Din fericire, Susan a făcut rost de o hartă care îi indică cu exactitate coordonatele locului în care se află comoara din turn. Eroul nostru vrea să știe care este distanța minimă pe care o poate parcurge pentru a ajunge la comoară.

• fi blocată, astfel fiind inaccesibilă eroului nostru
• fi accesibilă, astfel eroul nostru poate intra în aceasta
• conține o scară ascendentă care îl poate duce pe erou cu un etaj mai sus, în camera situată deasupra camerei curente
• conține o scară descendentă care îl poate duce pe erou cu un etaj mai jos, în camera situată sub camera curentă
• conține o trapă prin care eroul va cădea la etajul inferior, în camerele situate sub camera curentă (dacă eroul, în urma căderii, se află într-o cameră ce conține o trapă, el va continua să cadă până se va afla într-o o cameră fără trapă, pe aceeași coloană)

La fiecare trecere dintr-o cameră în alta, eroul execută un pas.

Fiind date latura turnului și coordonatele zidurilor, scărilor, gropilor, eroului și a comorii, se cere să se afișeze numărul minim de pași pe care îl poate parcurge Susan pentru a ajunge la comoară.

Date de intrare

Fișierul de intrare turn.in conține:

• pe prima linie numărul n, reprezentând lungimea laturii turnului.
• pe a doua linie se află numărul z, reprezentând numărul de ziduri, numărul s1, reprezentând numărul de scări descendente, numărul s2, reprezentând numărul de scări descendente și numărul g, reprezentând numărul de gropi.
• pe următoarele z linii se află coordonatele zidurilor.
• pe următoarele s1 linii se află coordonatele scărilor ascendente.
• pe următoarele s2 linii se află coordonatele scărilor descendente.
• pe următoarele g linii se află coordonatele gropilor.
• pe penultima linie se află coordonatele eroului, iar pe ultima linie se află coordonatele comorii.

Date de ieșire

Fișierul de ieșire turn.out va conține numărul minim de pași pe care îl poate face Susan pentru a ajunge la comoara sa.

Restricții și precizări

• 1 ≤ n ≤ 100
• 1 ≤ z ≤ 30000
• 1 ≤ s1 ≤ s2 ≤ 200
• 1 ≤ g ≤ 10000
• Se garantează că există soluție pentru toate datele de test.
• Poziția inițială se consideră a fi situată la pasul 1.
• Trapa generează o cădere a eroului pe verticală, până când ajunge într-o cameră fără trapă.

Exemplu:

turn.in

3
9 3 3 3
1 1 3
1 2 1
1 3 2
2 1 1
2 1 3
2 2 2
3 1 1
3 2 3
3 3 3
1 2 3
2 3 2
2 1 2
2 2 3
3 3 2
3 1 2
3 3 1
3 2 1
2 3 1
1 1 1
2 2 1

turn.out

11

Explicație

Turnul are 3 etaje. Susan pleacă din celula de coordonate (1 1 1), iar celula în care se află comoara are coordonatele (2 2 1). Există 9 celule în care se află ziduri, 3 celule în care se află scări ascendente, 3 celule în care se află scări descendente și 3 celule în care se află gropi. Traseul cel mai scurt trece prin 11 camere: (1 1 1) (1 1 2) (1 2 2) (1 2 3) (2 2 3) (2 3 3) (2 3 2) (3 3 2) (3 2 2) (3 2 1) (2 2 1).