Problem 3431: Constangeles

De fapt suntem doar doi...

Acum că au reușit să facă Constanța tare din nou, cei patru se întâlnesc cu o nouă provocare: următoarea rundă de la OOIT. Astfel, Rara decide să își cheme buzduganul magic la el acasă ca să se pregătească pentru concurs. Problema e că, odată cu venirea frigului și a ploilor, a picat și curentul în întregul oraș. Acesta este curpins de o beznă totală, iar cei doi prieteni nu se mai pot găsi. Se pare că nu e chiar așa de tare Constanța…

Orașul este în formă de matrice dreptunghiulară de dimensiuni $N \times M$ , unde fiecare element al acesteia reprezintă o bucată de drum. Din fericire, Rara știe $K$ poziții ai unor stâlpi de iluminat pe care îi poate aprinde, chiar și fără curent, folosindu-se de bateria sa magică.

Fiecare stâlp de iluminat $i \ (1 \leq i \leq K)$ se află pe linia $X_i$ și coloana $Y_i$ și are o rază $R_i$ de iluminare. Dacă acesta este aprins, el va ilumina toate bucățile de drum $(X_d, Y_d)$ pentru care $|X_d - X_i| + |Y_d - Y_i| \leq R_i$ .

De asemenea, stâlpii sunt legați printr-un fir magic astfel încât, dacă stâlpul $i$ este aprins, atunci se vor aprinde și stâlpii precedenți acestuia. Formal, aprinderea unui stâlp de iluminat $i$ duce la aprinderea stâlpilor de iluminat $j$ cu proprietatea că $1 \leq j \leq i$ .

Cerință

Cum Rara este un băiat tare leneș, vă roagă să îl ajutați să găsească numărul minim de stâlpi ce trebuie aprinși pentru ca prietenul său să poată ajunge din punctul de start $(1, 1)$ până la el, în $(N, M)$ , mergând doar pe direcțiile $N$ , $S$ , $E$ și $V$ și numai pe bucăți de drum iluminate de stâlpi.

Date de intrare

Pe prima linie se află, separate prin câte un spațiu, $N$ și $M$ (dimensiunile orașului) și $K$ (numărul de stâlpi de iluminat).
Pe următoarele $K$ linii se găsesc trăsăturile stâlpilor. Astfel, pe linia $i + 1$ se află $X_i$ , $Y_i$ și $R_i$ , caracteristicile celui de-al $i$ -lea stâlp, separate prin câte un spațiu.

Date de ieșire

Pe prima linie se va afla numărul minim de stâlpi ce trebuie aprinși astfel încât cei doi prieteni să se întâlnească.

Restricții și precizări

$1 \leq N, M \leq 1000$ .
$1 \leq K \leq N \cdot M$ .
$1 \leq X_i \leq N$ .
$1 \leq Y_i \leq M$ .
$0 \leq R_i \leq 2000$ .
Se garantează că, dacă Rara aprinde toți stâlpii de iluminat, atunci prietenul lui va ajunge la $(N, M)$ .
Se garantează că pe o bucată de drum se va afla cel mult un stâlp de iluminat.
Pentru citirea și afișarea rapidă, se recomandă folosirea acestor linii de cod la începutul funcției main:

ios::sync_with_stdio(false);  
cin.tie(NULL);  
cout.tie(NULL);

#	Punctaj	Restricții
0	0	Exemplul
1	21	$1 \leq N, M \leq 100$
2	17	$0 \leq R_i \leq 5$
2	62	Fără restricții suplimentare

Exemplu

stdin

stdout

Explicație

După ce Rara aprinde primele $4$ stâlpuri de iluminat, orașul arată astfel:

\begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ \end{bmatrix}

În această matrice am notat bucățile de drum cu $1$ dacă sunt iluminate și cu $0$ în caz contrar.
Se poate observa că există un drum pe care prietenul lui Rara îl poate parcurge de la $(1, 1)$ până la $(5, 4)$ , mergând numai pe bucăți de drum iluminate.
Un astfel de drum este următorul: $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (4, 1) \rightarrow (5, 1) \rightarrow (5, 2) \rightarrow (5, 3) \rightarrow (5, 4)$

Constangeles