Cerința

Unul dintre cele mai influente regate din continentul Alaocs este regatul Ofni. Harta regatului poate fi redată ca o matrice cu n linii și m coloane. Regatul este format din munți (^), râuri și lacuri (~), locuri libere de teren (_) și orașe (x). Observăm că se pot forma zone delimitate de munți, ape sau marginile hărții. Numim zonă o porțiune maximă de teren care conține locuri libere de teren și orașe, delimitată de munți, ape și marginea hărții. De asemenea, mai multe orașe învecinate pe linie sau pe coloană formează o cetate.

Din cauza puterii tot mai mari a regatelor rivale Etam și Akizif regele regatului Ofni a decis să înceapă un proces de fortificare a orașelor și cetăților. Pentru a face asta este necesară construcția de drumuri. Regele dorește ca între fiecare oraș și fiecare cetate să existe cel puțin un drum care să le lege și ca între toate cetățile să existe cel puțin un drum. Costul construcției unui drum printr-un loc liber are costul 1, construcția unui pod peste apă are costul 2, iar al unui tunel prin munte are costul 3. Pentru a nu goli trezoreria regală, regele își dorește ca acest cost de construcție a drumurilor să fie minim.

Problema are două cerințe.
Pentru c = 1, se cere determinarea numărului de cetăți, a numărului de zone și a numărului minim și maxim de cetăți dintr-o zonă.
Pentru c = 2, se cere costul total, minim, de construcție a drumurilor care conectează cetățile și orașele.

Date de intrare

Fișierul de intrare fortificari.in va conține pe prima linie, separate printr-un spațiu, valorile c, n și m, unde c numărul cerinței și n și m au semnificația din enunț. Pe următoarele n linii se află șiruri de câte m caractere neseparate care reprezintă harta regatului.

Date de ieșire

Dacă c = 1, fișierul de ieșire fortificari.out ca conține patru valori cu semnficația din enunț. Dacă c = 2, fișierul de ieșire va conține o singură valoare marcând costul minim de construcție a drumurilor.

Restricții și precizări

• 1 ≤ n, m ≤ 100
• pentru cerința 2, numărul de cetăți și orașe separate ≤ 10
• o cetate e formată din cel puțin două orașe învecinate pe linie sau coloană
• 20 puncte pentru cerința 1
• 10 puncte pentru cerința 2 cu n, m ≤ 10
• 70 puncte pentru cerința 2 fără restricții suplimentare

Exemplul 1

fortificari.in

1 8 7
^^^^^^^
~_xxx^x
_^^^x~x
x__~x~~
_______
^^^^^^_
x_x_x~~
x ~~~~~

fortificari.out

3 3 1 1

Exemplul 2

fortificari.in

2 8 7
^^^^^^^
~_xxx^x
_^^^x~x
x__~x~~
_______
^^^^^^_
x_x_x~~
x_~~~~~

fortificari.out

12

Exemplul 3

fortificari.in

2 8 7
^^^^^^^
~_xxx^x
_^^^x~x
x__~x~~
_______
^^^^^^_
x____x~
x_~~~~~

fortificari.out

14

Explicație

Avem 3 cetăți, 3 zone, iar numărul minim și maxim de cetăți dintr-o zonă este 1 și 1.
Pentru exemplul 2, traseul de cost minim este 5 * 1 + 2 * 2 + 3 = 12.

~ _ x x x ^ x
_ ^ ^ ^ x ~ x
x _ _ ~ x ~ ~
_ _ _ _ _ _ _
^ ^ ^ ^ ^ ^ _
x _ x _ x ~ ~
x _ ~ ~ ~ ~ ~

Pentru exemplul 3, traseul de cost minim este 7 * 1 + 2 * 2 + 3 = 14. Cetatea de jos și orașul izolat au drum comun pe o porțiune.
~ _ x x x ^ x
_ ^ ^ ^ x ~ x
x _ _ ~ x ~ ~
_ _ _ _ _ _ _
^ ^ ^ ^ ^ ^ _
x _ _ _ _ x ~
x _ ~ ~ ~ ~ ~