Obeleži sve kategorije koje odgovaraju problemu

Mali Perica je napravio početničku grešku: šifrirao je celokupan sadržaj svog hard diska koristeći neki string (sastavljen od malih slova engleske abecede) kao ključ, koji je zatim izgubio! Uspeo je, doduše, da pronađe dva stringa, $A$ i $B$, koja su ”slični” traženom. Perica sada želi da konstruiše najverovatniju moguću šifru koristeći ova dva stringa.

Peričin cilj je da učini da ova dva stringa budu potpuno isti. Dozvoljen mu je samo jedan tip poteza: ubacivanje određenog broja ”džoker” karaktera između dva susedna karaktera u jednom od ova dva stringa. Na primer, u jednom potezu od stringa abcdef možemo napraviti string abc???def, ili abcdef?? (tj. dozvoljeno je ubacivati džokere i na početak ili kraj stringa). Džoker karakteri se podudaraju sa bilo kojim karakterom!

Naravno, ovo bi bio jednostavan zadatak da ne postoje dodatni uslovi: kada se stringovi $A$ i $B$ izjednače na ovaj način, obračunava se ”kvalitet” rešenja, na sledeći način:

• Za svaku poziciju na kojoj ne postoji džoker ni u stringu $A$ ni u stringu $B$, dodaje se 1 poen.
• Za svaki potez, oduzima se $X$ poena.
• Za svaki džoker, oduzima se $Y$ poena.

Vaš zadatak je da odredite maksimalan kvalitet koji je moguće postići na ovaj način.

Opis ulaza

U prvom redu standardnog ulaza nalaze se četiri cela broja, $N$, $M$, $X$ i $Y$, koji predstavljaju dužine stringova $A$ i $B$, cenu jednog poteza, i cenu jednog džokera, redom. U drugom redu standardnog ulaza nalazi se string $A$, sastavljen od $N$ malih slova engleske abecede. U trećem redu standardnog ulaza nalazi se string $B$, sastavljen od $M$ malih slova engleske abecede.

Opis izlaza

U prvom i jedinom redu standardnog izlaza potrebno je ispisati jedan ceo broj, koji predstavlja maksimalan kvalitet šifre koji je moguće postići koristeći stringove $A$ i $B$ (ovaj broj može biti negativan).

Primer 1

Ulaz

5 4 1 1
abcef
acde

Izlaz

-3

Primer 2

Ulaz

7 7 5 5
abcdefj
befghij

Izlaz

-41

Objašnjenje primera

U prvom primeru, možemo ubaciti jedan džoker između karaktera c i e u stringu $A$, jedan džoker između karaktera a i c u stringu $B$, i jedan džoker na kraj stringa $B$. Ovim dobijamo ”iste” stringove:

abc?ef

a?cde?

Ukupni kvalitet ovog rešenja je $3 - 1 \times 3 - 1 \times 3 = -3$ (tri podudaranja bez džokera, tri poteza, tri džokera). Nije moguće postići rešenje sa većim kvalitetom.

U drugom primeru, jedno od mogućih optimalnih rešenja će uraditi sledeće poteze:

• Ubaciti jedan džoker na početak stringa $B$;
• Ubaciti dva džokera između karaktera b i e u stringu $B$;
• Ubaciti tri džokera između karaktera f i j u stringu $A$.

Ovim dobijamo ”iste” stringove:

abcdef???j

?b??efghij

Ukupni kvalitet ovog rešenja je $4 - 5 \times 3 - 5 \times 6 = -41$ (četiri podudaranja bez džokera, tri poteza, šest džokera). Nije moguće postići rešenje sa većim kvalitetom.

Ograničenja

• $1 \leq N, M \leq 1000$
• $0 \leq X, Y \leq 10^8$
• Stringovi $A$ i $B$ će sadržati samo mala slova engleske abecede.

Napomena

Test primeri su podeljeni u pet disjunktnih grupa:

• U test primerima vrednim 20 poena važiće $N, M \leq 100$, $X, Y \leq 1000$.
• U test primerima vrednim 10 poena važiće $X = Y = 0$.
• U test primerima vrednim 10 poena važiće $X = 0$.
• U test primerima vrednim 20 poena važiće $X, Y \leq 1000$.
• U test primerima vrednim 40 poena nema dodatnih ograničenja.