gheizere

Într-o zonă vulcanică de formă dreptunghiulară de dimensiuni întregi $N \cdot M$, împărţită în celule pătrate de latura $1$, există $P$ gheizere.

Gheizerele sunt izvoare intermitente de origine vulcanică, care emit în atmosferă la intervale regulate de timp jeturi de apă fierbinte şi/sau vapori, datorită încălzirii rapide a apelor din golurile subterane.

Erupţia unui gheizer produce stropirea cu apă fierbinte a unei zone circulare cu centrul situat în punctul $(x,y)$ aflat pe linia $x$ şi coloana $y$, şi raza $r$, zona afectată fiind considerată zona delimitată de pătratul în care se înscrie cercul.

Î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.

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.

Cerință

Să se determine timpul minim necesar traversării de la vest la est a zonei vulcanice de către cercetător fără riscuri majore.

Date de intrare

Fişierul 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.

Date de ieșire

Fişierul gheizere.out va conţine o singură valoare naturală $T$ ce reprezintă timpul minim necesar cercetătorului pentru a traversa zona vulcanică de la vest la est fără riscuri majore.

Restricții și precizări

• $2 \leq N, M \leq 250$
• $1 \leq e, v \leq N$
• $1 \leq x \leq N$
• $1 \leq y \leq M$
• $1 \leq P \leq 1 \ 000$
• $1 \leq r \leq 5$
• $1 \leq d \leq 5$
• $2 \leq t < 10$
• Două gheizere nu pot avea aceleaşi coordonate pentru centrul cercului
• Iniţial toate gheizerele sunt inactive
• Cercetătorul parcurge traseul fără să se oprească
• Pentru datele de intrare există întotdeauna soluţie
• Durata maximă a unui traseu parcurs de către cercetător este $\leq 1 \ 000$ secunde

Exemplu

gheizere.in

9 10 5
1 9
2 6 1 2 2
3 3 1 3 3
6 8 2 6 1
8 2 1 4 2
9 5 1 4 1

gheizere.out

18

Explicație

Unul dintre traseele posibile care porneşte din $(1,1)$ şi ajunge în $(9,10)$ în timp minim este marcat, secundă cu secundă, în figura următoare.

Zonele influenţate de gheizere sunt marcate cu pătrate gri, iar centrul fiecărui gheizer este evidenţiat (bold).