Prenos

Prenesti želimo podatke o $K$ zemljevidih, ki so oblike pravokotne mreže z $N$ vrsticami in $M$ stolpci. Vsi zemljevidi so enakih dimenzij, razlikujejo pa se po svoji vsebini. Vsebino vsake celice zemljevida bomo predstavili z nekim ascii znakom s kodo med 33 in 126 (printable characters).

Zemljevide bomo pošiljali enega za drugim v poljubnem vrstnem redu. Pri tem lahko zemljevid $z$ pošljemo na dva načina. Pošljemo lahko celoten opis zemljevida $z$, kar zahteva prenos $NM$ bajtov. Druga možnost je, da izberemo nek že prenesen zemljevid $z'$ in pošljemo samo podatke o tem, kako se nov zemljevid $z$ razlikuje od $z'$. Za tako pošiljanje potrebujemo $d(z,z') X$ bajtov, kjer je $X$ vnaprej podana cena pošiljanja posamezne spremembe, $d(z,z')$ pa število istoležnih celic, v katerih se zemljevida $z$ in $z'$ razlikujeta.

Omejitve podatkov:

• $1 \leq K \leq 1000$
• $1 \leq N,M \leq 10$
• $1 \leq X \leq 100$

Vhodni in izhodni podatki:

V prvi vrstici so s presledkom ločena števila $K$, $N$, $M$ in $X$. Sledijo opisi vseh $K$ zemljevidov, ki se začnejo s prazno vrstico, čemur sledi $N$ vrstic z nizi dolžine $M$.

Izpišite najmanjšo ceno prenosa vseh zemljevidov.

Primer vhoda:

6 2 3 2

AA.
.BC

BAC
CBC

...
...

.A.
.BC

BA.
.BC

A..
...

Pravilen izhod:

22

Eden od načinov prenosa je sledeč:

• Prenesemo tretji zemljevid (cena 6).
• Prenesemo šesti zemljevid kot razliko do tretjega (cena 2).
• Prenesemo prvi zemljevid (cena 6).
• Prenesemo četrti in peti zemljevid kot razliko do prvega (obakrat cena 2).
• Prenesemo drugi zemljevid kot razliko do petega (cena 4).