4. Zakázané ohňostroje

Konečne deň, na ktorý sa Emo celý rok tešil – Silvester. Tento rok ho chce stráviť na internáte v Bratislave. Keď sa to dozvedel jeho kamarát, neodpustil si štipľavú otázku, či už má nakúpené ohňostroje¹. Emo iróniu nepochopil a tak, keďže nemal, začal narýchlo nejaké zháňať.

Zobral auto a šup ho na cesty. Ešte sa vo svojom rodnom meste² zastavil v obchode s pyrotechnikou a minul tam takmer celú výplatu. Odtiaľ už išiel priamo do Bratislavy.

Keď zišiel z diaľnice, zastavil sa ešte na benzínke. Ako tak tankoval, započúval sa do rádia a takmer dostal infarkt. Práve totiž išli správy o situácii v Bratislave:

• Za púšťanie rakiet v Bratislave hrozí veľká pokuta.

• Keďže policajti očakávajú v tento deň veľký počet výtržností³, vymysleli si systém ako mať všetko pod kontrolou. Po meste na náhodné pevne určené miesta umiestnili policajné kontroly, kde kontrolujú obsah každého auta. Nemôžu dať síce pokutu za to, že niekto ohňostroj prepravuje, ale môžu si ho poznačiť a navštíviť večer.

• Aby bolo ťažké sa kontrole vyhnúť, na každej križovatke, kde nie je kontrola, stojí policajt ukazujúci len jeden prípustný smer jazdy. Každému, kto by z takejto križovatky chcel odísť iným, než povoleným smerom, dá pokutu (ale nechá ho ísť).

Emo si nejakú tú raketku neodpustí. Cesta na intrák tak preňho nebude iba o šoférovaní. Potrebuje v prvom rade zistiť kade má na intrák ísť tak, aby minul čo najmenej peňazí na pokuty.

Rýchlo preto zavolal Zajovi, nech mu pomôže. Zajo je totiž rodený Bratislavčan a má prístup k informáciám, o ktorých iní môžu len snívať. Potrebuje však vašu pomoc, aby vedel Emovi rýchlo odpovedať skôr ako si niekto všimne, že ešte aj telefonuje za volantom!

Úloha

Pre účely tejto úlohy budeme Bratislavu považovať za obdĺžnik \(r \times s\) križovatiek. Na každej križovatke sa dá prejsť rovno, odbočiť vpravo, vľavo, aj otočiť sa.

Existujú križovatky nasledovných typov:

• Križovatky s prikázaným smerom odjazdu: tieto križovatky majú len jeden povolený smer odjazdu. Ak z nich Emo odíde iným ako povoleným smerom, dostane pokutu. Veľkosť tejto pokuty môže byť rôzna pre rôzne smery. Napríklad pre križovatky s prikázaným smerom odjazdu hore môže byť iná pokuta ako pre križovatky s prikázaným smerom odjazdu dole.

• Križovatky s kontrolou: tieto križovatky nemajú žiadne obmedzenia na to, ako cez ne môžete jazdiť, ale policajti na nich kontrolujú obsah kufra. Ak Emo počas cesty na internát prejde čo i len cez jednu takúto križovatku, o polnoci bude musieť zaplatiť pokutu za odpálenie rakety. Ak Emo prejde cez viacero takýchto križovatiek, bude platiť rovnako veľa, ako keby prešiel len cez jednu.

• Križovatka s internátom: táto križovatka je Emov cieľ. Prikázaný smer odjazdu z tejto križovatky nás nezaujíma, lebo Emo z tejto križovatky už nechce ísť ďalej.

• Križovatka s benzínkou: na tejto križovatke Emo začína a nie je tam ani kontrola, ani prikázaný smer odjazdu.

• Na niektorých políčkach obdĺžnika nie sú križovatky, ale Dunaj. Sem sa Emo s autom nikdy nechce dostať!

Dostanete popis situácie v Bratislave a aj veľkosti jednotlivých pokút. Zistite, koľko najmenej môže Emo zaplatiť na pokutách, ak chce prísť na internát a o polnoci tam odpáliť raketu. Počas svojej cesty nemôže opustiť Bratislavu.

Nepredpokladajte, že sa v Bratislave dá dostať na každú križovatku bez porušenia predpisov! Dokonca je možné, že na niektorých križovatkách je prikázaný smer jazdy do Dunaja.

Formát vstupu

Na prvom riadku vstupu dostanete medzerami oddelené postupne veľkosti pokút \(P_O, P_L, P_P, P_H, P_D\): veľkosť pokuty za ohňostroj (ktorú Emo zaplatí, ak prejde cez nejakú kontrolu) a za porušenie prikázaného smeru odjazdu vľavo, vpravo, hore a dole. Všetky pokuty sú celé čísla z rozsahu \(0\) až \(10^{12}\) (vrátane).

Nasleduje riadok s rozmermi mapy \(r, s\) (\(1 \leq r \cdot s \leq 100\,000\)). Ďalej nasleduje \(r\) riadkov po \(s\) znakoch popisujúcich samotnú Bratislavu. Každý z týchto znakov určuje typ jednej križovatky.

Znaky popisujúce križovatky môžu byť nasledovné: K – križovatka s kontrolou; E – križovatka s benzínkou, kde Emo začína; I – križovatka s internátom (cieľ); L, P, H, D – križovatky s prikázaným smerom odjazdu vľavo, vpravo, hore alebo na dole; ~ – Dunaj.

Môžete predpokladať, že na mape sa aj intrák aj Emo nachádzajú práve raz.

Formát výstupu

Vypíšte, koľko najmenej môže Emo zaplatiť na pokutách, ak sa chce dostať na intrák a o polnoci tam odpáliť raketu. V prípade, že neexistuje cesta vypíšte -1.

Hodnotenie a obmedzenia

Pre jednotlivé sady testov navyše platia nasledovné obmedzenia. Za vyriešenie každej sady získate 1 bod.

Príklad

Input:

10 10 1 6 4
4 3
HLL
IPK
D~H
DLE

Output:

8

Optimálna cesta na internát vyzerá nasledovne: Z benzínky pôjde Emo doľava, pričom neplatí žiadnu pokutu, lebo na benzínke policajti nie sú. Potom pôjde opäť doľava, pričom opäť neplatí pokutu, lebo odišiel povoleným smerom. Následne pôjde dvakrát nahor, pričom oba razy poruší prikázaný smer jazdy nadol, teda dvakrát zaplatí pokutu \(4\). Keďže Emo neprešiel cez žiadnu kontrolu, o polnoci nedostane žiadnu pokutu.

Input:

1 2 3 4 5
2 2
E~
~I

Output:

-1

Emo môže rovno odparkovať, nikam sa nedostane.

Input:

1000 1 2 3 4
4 6
DHHHPK
LELKHK
~P~PKL
PKLHI~

Output:

1001

Kontrole sa cestou na internát nedá vyhnúť. Optimálne je ísť najprv trikrát doprava, potom hore, doprava, dvakrát dole, doľava a dole. Všimnite si, že po ceste Emo prejde až cez štyri kontroly, pokutu za odpaľovanie ohňostrojov však aj tak zaplatí iba raz. Okrem toho ešte poruší jeden prikázaný smer odjazdu vľavo, takže dokopy na pokutách zaplatí \(1000 + 1 = 1001\).