Fișierul intrare/ieșire	noxa.in, noxa.out	Sursă	timus.ru
Autor	Leonid Volkov	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.05 sec	Limită de memorie	10240 KB
Scorul tău	N/A	Dificultate	3.25

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Noxa (clasa a 7-a)

În orașul Noxa toți locuitorii sînt mîndri că ei merg doar cu mașinile lor personale. Sub președintele Trăiam Binescu nivelul de trai a crescut simțitor, astfel încît orice noxian are cel puțin două mașini. Codoi, cetățean model, conducea mașina zilnic pînă la serviciu și înapoi. Dar vai, mașina lui era Eurău 3, iar într-o bună zi Gabi Fii Rea, primărița orașului Noxa, a interzis toate mașinile Eurău 3. Codoi s-a trezit pentru prima oară în viață în situația de a ajunge la serviciu pe jos. Era pierdut! Nu recunoștea nimic din orașul său. Era prima oară pieton în Noxa. Mai mult, aerul era irespirabil: particule, mono/dioxid de carbon, oxid de azot. Trebuia să meargă rapid sau risca să-și piardă cunoștința, poate și viața!

Cerință

Ajutați-l pe Codoi să ajungă la serviciu pe drumul cel mai scurt.

Orașul Noxa este format din străzi paralele și perpendiculare, ce formează o grilă de pătrate identice, cu latura de 100m. Apartamentul lui Codoi se află în colțul din stînga sus, iar serviciul lui se află în colțul din dreapta-jos, la M pătrate, respectiv N pătrate distanță. Unele pătrate sînt parcuri. Ele pot fi traversate pe diagonală, în direcția jos-dreapta (convenabil).

Date de intrare

În fișierul de intrare noxa.in se află, pe prima linie, M și N, numărul de pătrate pe linii, respectiv pe coloane între apartamentul lui Codoi și serviciu. Pe următoarea linie se află K, numărul de parcuri. Pe următoarele K linii se află liniile și coloanele celor K parcuri, în numerotare de la 1.

Date de ieșire

În fișierul de ieșire noxa.out veți scrie un singur număr, anume lungimea, în metri, a drumului cel mai scurt pe care să îl urmeze Codoi. Deoarece lungimea este un număr cu zecimale, veți afișa doar partea întreagă a acelui număr.

Restricții

• 0 ≤ M, N ≤ 10000
• 0 ≤ K ≤ 1000
• Pentru teste în valoare de 75p M·N ≤ 10 milioane
• latura unui pătrat din grilă este de 100m
• funcția sqrt(x) returnează un număr real, care înmulțit cu un număr întreg are ca rezultat tot un număr real
• trunchierea unui număr real x la întreg se face astfel: (int)x

Exemplu