008 - 文字列の魔法

時間制限 8 秒 / メモリ制限 256 MB / 得点 32 / x 0 /

TLE
8sec
MLE
256MB
得点
32

問題

魔法使いであるあなたは，今日も魔法の修行に励んでいる．あなたは今，手元に英小文字からなる文字列 X を持っている．あなたの今日の修行の課題は，この文字列を，別の文字列 Y に変化させることである．

あなたは，文字列を変化させる魔法を 4 種類習得していて，それらを好きな順序で何回でも唱えることができる．ただし，魔法を唱えるたびに，魔法石と呼ばれる特別な石を消費する．あなたが習得している魔法は次の通りである．

  • 魔法石を A 個消費する．手元の文字列の好きな位置に，好きな英小文字 1 文字を追加する．例えば，元の文字列が bcbd であった場合，abcbd, bcebd, bcbdf などの文字列に変化させることができる．
  • 魔法石を E 個消費する．手元の文字列の好きな 1 文字を取り除く．例えば，元の文字列が bcbd であった場合，cbd, bbd, bcd, bcb のいずれかに変化させることができる．なお，元の文字列の長さが 0 である場合，この魔法を唱えることはできない．
  • 魔法石を S 個消費する．手元の文字列の好きな 1 文字を，別の好きな英小文字 1 文字に置き換える．例えば，元の文字列が bcbd であった場合，acbd や bebd などの文字列に変化させることができる．なお，元の文字列の長さが 0 である場合，この魔法を唱えることはできない．
  • 魔法石を R 個消費する．手元の文字列の先頭の 1 文字を末尾に移動させる．例えば，元の文字列が bcbd であった場合，cbdb に変化させることができる．なお，元の文字列の長さが 0 である場合，この魔法を唱えることはできない．

魔法石は高価なので，あなたは魔法石の消費を最小限にしたいと考えている．文字列 X を文字列 Y に変化させるために必要な魔法石の個数の最小値を求めよ．

Input

入力は複数のデータセットからなる．各データセットは以下の形式で表される．

X Y A E S R

X, Y は英小文字のみからなる異なる文字列であり，いずれも長さは 1 以上 100 以下である．A, E, S, R はいずれも 1 以上 106 以下の整数である．

入力の終わりは '#' 一つのみからなる行で示される．入力に含まれるデータセットの数は高々 50 である．

Output

各データセットについて，文字列 X を文字列 Y に変化させるために必要な魔法石の個数の最小値を，1 行に出力せよ．

Sample Input

typewriter
periodicity
100010
100100
101000
110000
periodicity
typewriter
100010
100100
101000
110000
periodicity
typewriter
100010
100100
101000
1
domestic
contest
100010
100100
101000
110000
#

Output for the Sample Input

823120
1001540
603217
502210