Miting

În Orașul Liniștit un număr de $k$ tineri prieteni doresc să participe la un miting de protest. Deoarece cartierul în care locuiesc aceștia este mare, ei se vor deplasa spre punctul de întâlnire cu mașinile personale. Fiecare tânăr va aduce cu el o pancartă, pe care a desenat o singură literă din mulțimea $\{$A$,$ B$,\ \dots,$ Z$\}$. Nu există două pancarte cu litere identice. Cele $k$ litere formează un cuvânt, să-l notăm $cuv$, cunoscut.

Cartierul în care locuiesc tinerii poate fi codificat printr-o matrice cu $n \cdot m$ zone pătratice, dintre care unele sunt interzise. Se știe că o mașină consumă o unitate de combustibil la trecerea dintr-o zonă în zona vecină și nu consumă combustibil dacă staționează. Două zone sunt vecine dacă au în comun o latură. Pentru a face economie de combustibil, tinerii decid că dacă două mașini se întâlnesc într-o zonă și toate literele aflate în cele două mașini reprezintă o secvență din cuvântul $cuv$, atunci ei vor continua drumul cu o singură mașină, luând desigur toate pancartele cu ei. În caz contrar, mașinile își continuă drumul separat.

De exemplu, dacă cuvantul $cuv$ este JOS, atunci mașina care transportă litera J poate prelua tânărul care aduce pancarta cu litera O, sau invers: mașina având litera O poate prelua tânărul care aduce litera J. Apoi se poate continua drumul spre mașina care transportă litera S. În altă variantă se pot reuni mai întâi literele S și O într-o singură mașină, dacă mașinile care le transportau se întâlnesc în aceeași zonă. Totuși, între mașina care transportă doar litera J și cea care transportă doar litera S nu se poate realiza un transfer, adică o reunire a literelor.

Cerinţe

Cunoscând dimensiunile cartierului $n$ și $m$, cuvântul $cuv$, configurația cartierului și pozițiile inițiale ale tinerilor, se cere:

1. Aria minimă a unei submatrice a matricei care codifică cartierul, în care se situează toate pozițiile inițiale ale tinerilor.
2. Numărul minim de unități de combustibil consumați de către toate mașinile, știind că în final toți tinerii se vor reuni într-o singură mașină.

Date de intrare

Fişierul de intrare miting.in conţine:

Pe prima linie, un număr natural $p$, care poate avea doar valoarea $1$ sau $2$.

Pe a doua linie două numere naturale $n$ și $m$, separate printr-un spațiu.

Pe a treia linie, cuvântul $cuv$.

Pe următoarele $n$ linii, câte $m$ caractere pe linie reprezentând zonele cartierului. O zonă este interzisă dacă îi corespunde caracterul #, este liberă dacă îi corespunde caracterul _ (underline) și este punctul de plecare al unei mașini dacă îi corespunde una dintre literele cuvântului $cuv$.

Date de ieșire

Dacă valoarea lui $p$ este $1$, se va rezolva numai cerința $1$.

În acest caz, în fişierul de ieşire miting.out se va scrie un singur număr natural $A$, reprezentând aria minimă a unei submatrice a matricei care codifică cartierul, în care se situează toate pozițiile inițiale ale tinerilor.

Dacă valoarea lui $p$ este $2$, se va rezolva numai cerința $2$.

În acest caz, în fişierul de ieşire miting.out se va scrie un singur număr natural $C$, reprezentând numărul minim de unități de combustibil consumate de către toate mașinile până la reunirea tinerilor, deci și a literelor, într-o singură mașină. În cazul în care nu există soluție, adică nu toți tinerii se pot reuni într-o singură mașină, se va scrie $-1$.

Restricții și precizări

• $2 \leq n, m \leq 60$
• $2 \leq k \leq 10$
• Fie $z$ numărul zonelor interzise. Atunci $0 ≤ z ≤ \frac{n \cdot m}{3}$.
• În fiecare unitate de timp, o mașină poate să rămână pe loc în așteptarea alteia sau poate să treacă într-o zonă vecină, indiferent dacă zona respectivă este sau nu ocupată de o altă mașină.
• Lungimea laturii unei zone se consideră egală cu $1$.
• Pentru rezolvarea corectă a primei cerinţe se acordă $20$ de puncte, iar pentru cerința a doua se acordă $80$ de puncte.
• Pentru $30\%$ dintre testele cerinței $2$ se garantează $k ≤ 3$.

Exemplul 1

miting.in

1
4 5
JOS
#_O_#
_#__S
_#J_#
___#_

miting.out

9

Explicație

Submatricea de arie minimă care include toate literele are colțul stânga sus la linia $1$ și coloana $3$ și colțul dreapta jos la linia $3$ și coloana $5$. Aria este egală cu numărul de zone acoperite:
$3 \cdot 3 = 9$.

Atenție! Pentru acest test se rezolvă doar cerința $1$.

Exemplul 2

miting.in

2
5 7
BUN
_#_#_#_
__N#__#
_#__B__
U__#_#_
_#_#_#_

miting.out

6

Explicație

O variantă de consum minim este: U se deplasează cu două poziții la dreapta. Apoi B se deplasează cu două poziții la stânga. U se deplasează din nou cu o singură poziție în sus. În final, N coboară o poziție.

Remarcați că B s-a reunit cu U, apoi BU cu N.

Atenție! Pentru acest test se rezolvă doar cerința $2$.

Exemplul 3

miting.in

2
6 7
ROST
O#_#_#_
___#__#
_#_R___
____#__
__#_S_#
_#_T_#_

miting.out

9

Explicație

O variantă de consum minim este: O se deplasează cu o poziție în jos, apoi cu două poziții spre dreapta, coboară o poziție și în final se deplasează o poziție spre dreapta, unde se reunește cu R. Apoi S se deplasează cu o poziție la stânga. T urcă o poziție și se reunește cu S. În final, mașina în care se găsesc S și T urcă două poziții și se întâlnește cu mașina în care se găsesc R și O. În această zonă, la linia $3$ și coloana $4$, toate literele se reunesc într-o singură mașină.

Atenție! Pentru acest test se rezolvă doar cerința $2$.