Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Мали Перица је направио почетничку грешку: шифрирао је целокупан садржај свог хард диска користећи неки стринг (састављен од малих слова енглеске абецеде) као кључ, који је затим изгубио! Успео је, додуше, да пронађе два стринга, \(A\) и \(B\), која су ”слични” траженом. Перица сада жели да конструише највероватнију могућу шифру користећи ова два стринга.
Перичин циљ је да учини да ова два стринга буду потпуно исти.
Дозвољен му је само један тип потеза: убацивање одређеног броја ”џокер”
карактера између два суседна карактера у једном од ова два стринга. На
пример, у једном потезу од стринга abcdef можемо направити
стринг abc???def, или abcdef?? (тј. дозвољено
је убацивати џокере и на почетак или крај стринга). Џокер карактери се
подударају са било којим карактером!
Наравно, ово би био једноставан задатак да не постоје додатни услови: када се стрингови \(A\) и \(B\) изједначе на овај начин, обрачунава се ”квалитет” решења, на следећи начин: - За сваку позицију на којој не постоји џокер ни у стрингу \(A\) ни у стрингу \(B\), додаје се 1 поен. - За сваки потез, одузима се \(X\) поена. - За сваки џокер, одузима се \(Y\) поена.
Ваш задатак је да одредите максималан квалитет који је могуће постићи на овај начин.
У првом реду стандардног улаза налазе се четири цела броја, \(N\), \(M\), \(X\) и \(Y\), који представљају дужине стрингова \(A\) и \(B\), цену једног потеза, и цену једног џокера, редом. У другом реду стандардног улаза налази се стринг \(A\), састављен од \(N\) малих слова енглеске абецеде. У трећем реду стандардног улаза налази се стринг \(B\), састављен од \(M\) малих слова енглеске абецеде.
У првом и једином реду стандардног излаза потребно је исписати један цео број, који представља максималан квалитет шифре који је могуће постићи користећи стрингове \(A\) и \(B\) (овај број може бити негативан).
5 4 1 1
abcef
acde-37 7 5 5
abcdefj
befghij-41У првом примеру, можемо убацити један џокер између карактера
c и e у стрингу \(A\), један џокер између карактера
a и c у стрингу \(B\), и један џокер на крај стринга \(B\). Овим добијамо ”исте” стрингове:
abc?ef
a?cde?
Укупни квалитет овог решења је \(3 - 1 \times 3 - 1 \times 3 = -3\) (три подударања без џокера, три потеза, три џокера). Није могуће постићи решење са већим квалитетом.
У другом примеру, једно од могућих оптималних решења ће урадити
следеће потезе: - Убацити један џокер на почетак стринга \(B\); - Убацити два џокера између карактера
b и e у стрингу \(B\); - Убацити три џокера између карактера
f и j у стрингу \(A\).
Овим добијамо ”исте” стрингове:
abcdef???j
?b??efghij
Укупни квалитет овог решења је \(4 - 5 \times 3 - 5 \times 6 = -41\) (четири подударања без џокера, три потеза, шест џокера). Није могуће постићи решење са већим квалитетом.
Тест примери су подељени у пет дисјунктних група: