22383번 - 文字列の魔法 다국어

문제

魔法使いであるあなたは,今日も魔法の修行に励んでいる.あなたは今,手元に英小文字からなる文字列 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 に変化させるために必要な魔法石の個数の最小値を求めよ.

입력

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

X
Y
A
E
S
R

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

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

출력

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

제한

힌트