6. Výtvarný ateliér

Adam a Samo mali už odjakživa vzťah k výtvarnému umeniu, aj keď sa mu nevenujú profesionálne. Obaja išli na vysokú školu študovať nejakú odnož informatiky, no každý na inej univerzite a v inej krajine. Počas svojho štúdia sa aktívne podieľajú na príprave Korešpondenčnej Súťaže Papieroskladania. Keď sa ale naskytla ďalšia aktivita spojená s umením, neváhali a išli do toho.

V rámci medzinárodného a medziuniverzitného projektu výtvarného ateliéru Adam a Samo spolupracujú na vytváraní farebných ozdobných reťazí. Ide o reťaze, ktorých oká sú vyrobené z farebného papiera, pričom farieb je 26. Lenže, obaja už dokončili reťaze, keď zistili, že reťaze by mali byť vlastne rovnaké!

Adam je ale momentálne zahltený inými povinosťami, tak ostáva na Samovi, aby svoju reťaz patrične upravil.

Poraďte mu, ako má upraviť svoju reťaz!

Úloha

Máte dve reťaze - Adamovu a Samovu. Reťaz má daný začiatok a koniec (neviete ju teda otočiť). Je opísaná postupnosťou farieb ôk od jej začiatku po koniec. Samo má k dispozícii nožnice, fixky, a dokonca aj predpripravené kusiská reťazí, takže vie buď:

• odstrihnúť súvislú časť reťaze a spojiť odstrihnuté miesta dokopy. Reťaz nemôže byť v procese obrátená!
  • z abcd tak môže vzniknúť acd, bcd, bc ale nie adc alebo cda
• vložiť nejaký súvislý kus reťaze medzi dve oká (alebo na koniec alebo začiatok reťaze)
  • z abcd tak môže vzniknúť abbbcd, alebo aefgbcd, alebo kspabcd
• prefarbiť oko na inú farbu
  • z abcd tak môže vzniknúť abce

Tieto operácie vie Samo ľubovoľne kombinovať.

Chcel by ale, aby bol s výsledkom spokojný. Napríklad so svojou pôvodnou reťazou bol spokojný a je smutný, ak ju musí upravovať. Spokojnosť Samo kvantifikuje nasledovne:

• Za každé nezmenené oko (neodstránené, ani neprefarbené) je o \(m\) bodov spokojnejší
• Za každý súvislý odstránený úsek je o \(d\) bodov menej spokojný.
• Za každý súvislý vložený úsek je \(i\) bodov menej spokojný.
• Za každé prefarbenie oka je o \(r\) bodov menej spokojný.

Čísla \(i\) a \(r\) sú konštanty a nezávisia od dĺžky vloženého, respektíve odstráneného úseku.

Farieb existuje 26 a sú označené malými písmenami anglickej abecedy. Zistite, ako najviac spokojný môže Samo zostať, a nejaký spôsob, ako môže svoju reťaz upraviť.

Formát vstupu

V prvom riadku vstupu sa nachádzajú štyri čísla:

• číslo, o koľko bude spokojnejší za každé nezmenené oko, \(m\)
• cena odstránenia súvislej časti ôk \(d\),
• cena vloženia súvislej reťaze ôk \(i\)
• cena prefarbenia oka \(r\).

Nasledujú dva riadky. V prvom z nich sa nachádza popis Samovej reťaze a na druhom popis Adamovej reťaze. Oba popisy sú reťazec z malých písmen anglickej abecedy.

Platí, že reťaze nepresahujú dĺžku \(5\,000\) a \(0 \leq m, d, i, r \leq 100\,000\).

Formát výstupu

Vypíšte jeden riadok: najväčšiu spokojnosť, ku ktorej sa vie Samo dopracovať.

Hodnotenie

Úloha má štyri sady. Maximálne dĺžky reťazí v nich budú postupne \(500\), \(2\,000\), \(2\,000\) a \(5\,000\).

V druhej sade, navyše platí, \(d = i = r = 0\), teda Samo nestráca žiadnu spokojnosť.

Príklady

Input:

1 2 2 1
abccb
accba

Output:

0

Samo by mal vymazať prvé oko s farbou ‘b’ zo svojej reťaze, a pridať oko s farbou ‘a’ na koniec. Takto sa štyroch svojich ôk nedotkne (+4 body spokojnosti), a raz odstráni ‘b’ (-2 body) a raz pridá ‘a’ (-2 body). Všimnite si, že napriek tomu, že je prefarbenie lacnejšie, než vymazanie, neoplatí sa mu.

Input:

3 2 2 1
asdffflp
kpfffor

Output:

3

Samo by mal vymazať ‘asd’ zo začiatku svojej reťaze a pridať tam ‘kp’. Na druhej strane, mal by ‘lp’ zmeniť po jednom na ‘or’. Takto bude \(-2-2+3+3+3-1-1 = 3\) bodov spokojný

Input:

1 1 1 10
kms
ksp

Output:

0

Samo nechce prefarbovať. Najlepšie mu je teda vystrihnúť preč \(m\) a pridanie \(p\)

Input:

10 1 1000 100
kspoooksp
kspkspksp

Output:

-240

Samo tu potrebuje zmeniť ‘ooo’ na ‘ksp’. Pridávanie mu výrazne uberá na spokojnosti, tak radšej ich po jednom prefarbí.