Drar

Time limit: 0.6s Memory limit: 128MB Input: drar.in Output: drar.out

Domnișoara R este o tânără foarte pasionată de medicină. Aceasta, pregătindu-se constant pentru admiterea la UMF, constată că are un obstacol - Stresu’.

Domnișoara R are o casă cu NMN \cdot M camere, aranjate pe NN linii (numerotate de la 11 la NN) și MM coloane (numerotate de la 11 la MM), dintre care BB camere sunt inaccesibile (nu este permis accesul în acestea). Vom nota cu [i,j][i, j] (1iN,1jM1 \leq i \leq N, 1 \leq j \leq M) camera situată pe linia ii și coloana jj.

Pentru că Universul este neprietenos, vrea să îi pună bețe în roate d-rei. RR și astfel îl trimite pe Stresu’ în casa acesteia în camera [X,Y][X, Y], care este o cameră accesibilă.

Stresu’ se poate deplasa în orice cameră adiacentă camerei în care se află (situată pe aceeași linie pe o coloană alăturată sau pe aceeași coloană pe o linie alăturată) sau își poate folosi unul dintre așii din mânecă. Stresu’ dispune de QQ ași.

Când utilizează asul cu numărul ii (1iQ1 \leq i \leq Q) Stresu’ se poate deplasa din camera [L1i,C1i][L1_i, C1_i] în camera [L2i,C2i][L2_i, C2_i]. Orice deplasare (utilizând un as sau într-o cameră adiacentă) necesită o secundă și deplasarea nu poate fi efectuată dacă presupune revenirea în ultima cameră care a fost vizitată. Se garantează că dacă există un as în mânecă de la camera [L1,C1][L1, C1] la camera [L2,C2][L2, C2], nu va exista un alt as de la camera [L2,C2][L2, C2] la camera [L1,C1][L1, C1].

Dra. R se află inițial în camera [1,1][1, 1]. Când aceasta constată că Stresu’ a intrat în casă, se panichează și urmează un traseu ilustrat printr-un șir de caractere care descrie direcțiile de deplasare:

  • L - din camera [i,j][i, j] se va deplasa în camera [i,j1][i, j − 1]
  • R - din camera [i,j][i, j] se va deplasa în camera [i,j+1][i, j + 1]
  • U - din camera [i,j][i, j] se va deplasa în camera [i1,j][i − 1, j]
  • D - din camera [i,j][i, j] se va deplasa în camera [i+1,j][i + 1, j]

Se garantează că d-ra R nu va trece prin camere inaccesibile.
Stresu’ și d-ra R nu pot staționa în camere, fiecare dintre ei trebuie să efectueze o deplasare la fiecare secundă.

Cerință

Știind că scopul lui Stresu’ este să o prindă pe d-ra R, scrieți un program care să determine timpul minim în care Stresu’ poate ajunge în aceeași cameră cu d-ra R.

Date de intrare

Fișierul de intrare drar.in conține pe prima linie numerele N M Q X Y BN \ M \ Q \ X \ Y \ B, reprezentând dimensiunile casei d-rei R, numărul de ași din mâneca lui Stresu’, coordonatele camerei pe unde intră Stresu’, respectiv numărul de camere inaccesibile.
Următoarele BB linii conțin camerele inaccesibile, câte o cameră pe o linie. Pe următoarele QQ linii sunt descriși așii, câte un as pe o linie, sub forma celor 44 numere L1i C1i L2i C2iL1_i \ C1_i \ L2_i \ C2_i, (1iQ1 \leq i \leq Q) cu semnificația din enunț. Pe ultima linie din fișier se va afla șirul de caractere care descrie modul în care se deplasează d-ra R. Numerele scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire drar.out va conține o singură linie pe care va fi scris timpul minim în care Stresu’ poate ajunge în aceeași cameră cu d-ra RR sau valoarea 1−1 dacă acest lucru nu este posibil.

Restricții și precizări

  • 1N,M2001 \leq N, M \leq 200
  • 1XN,1YM1 \leq X \leq N, 1 \leq Y \leq M
  • 0Q1 0000 \leq Q \leq 1 \ 000
  • 0BNM0 \leq B \leq N \cdot M
  • 1L1i,L2iN,1C1i,C2iM1 \leq L1i, L2i \leq N, 1 \leq C1_i, C2_i \leq M
  • 11 \leq lungimea traseului 200\leq 200
# Punctaj Restricții
1 10 X=Y=1X = Y = 1
2 30 1N,M6,0Q31 \leq N, M \leq 6, 0 \leq Q \leq 3
3 30 7N,M507 \leq N, M \leq 50
3 30 Nu există restricții suplimentare.

Exemplu

drar.in

6 6 4 5 2 5
2 1
4 4
2 4
3 2
2 6
6 4 2 2
3 4 2 3
5 1 2 5
3 5 3 3
RRRRDD

drar.out

6

Log in or sign up to be able to send submissions!