!problema/gheizere?enunt.jpg 200 x 200!
În figura alăturată avem 2 gheizere ce au coordonatele $(3,3)$ şi $(5,8)$, primul gheizer cu raza egală cu $1$, iar cel de-al doilea gheizer cu raza egală cu $2$. Pentru fiecare gheizer se cunoaşte intervalul de unităţi de timp $t$ consumat între erupţii, precum şi durata $d$ a unei erupţii, valori exprimate în secunde.

Misiunea unui cercetător este de a găsi un traseu ce pleacă dintr-un punct dat al terenului situat pe latura de vest $(v,1)$ şi traversează zona fără să o părăsească şi fără să treacă de două ori prin aceeaşi poziţie până la un alt punct $(e,M)$ situat pe latura de est.

Misiunea unui cercetător este de a găsi un traseu ce pleacă dintr-un punct dat al terenului situat pe latura de vest $(v,1)$ şi traversează zona fără să o părăsească până la un alt punct $(e,M)$ situat pe latura de est.

Cercetătorul se poate deplasa în oricare dintre direcţiile $nord$, $est$, $sud$, iar timpul consumat pentru parcurgerea unei celule neafectate la un moment dat este de o secundă. Parcurgerea unei zone în care acţionează cel puţin un gheizer pe perioada de erupţie a acestuia implică riscuri majore pentru cercetător.
h2. Cerinţă

h2. Date de intrare
Fişierul de intrare $gheizere.in$ conţine:

* pe prima linie trei valori naturale $N$, $M$ şi $P$, unde $N$ reprezintă numărul de linii şi $M$ numărul de coloane ale zonei vulcanice, iar $P$ numărul de gheizere;
* pe a două linie două valori naturale $v$ respectiv $e$, unde $v$ reprezintă linia punctului de plecare din vest, iar $e$ linia punctului de sosire din est;
* pe următoarele $P$ linii un set de cinci valorii $x$, $y$, $r$, $t$, $d$ ce reprezintă în ordine, pentru fiecare gheizer coordonatele centrului $(x,y)$, $r$ raza cercului de erupţie, $t$ timpul dintre erupţii, iar $d$ durata unei erupţii.

7738