String Magic

You are a magician, and you practice magic every day. Right now you hold a string X made of lowercase English letters. Today's training task is to turn this string into another string Y.

You have learned four spells that change strings, and you may cast them any number of times in any order. Each time you cast a spell, however, you consume a special stone called a magic stone. The spells you know are as follows.

• Consume A magic stones. Insert any one lowercase English letter at any position in your string. For example, if the original string is bcbd, you can change it into abcbd, bcebd, bcbdf, and so on.
• Consume E magic stones. Remove any one character from your string. For example, if the original string is bcbd, you can change it into one of cbd, bbd, bcd, bcb. If the length of your string is 0, you cannot cast this spell.
• Consume S magic stones. Replace any one character in your string with any other lowercase English letter. For example, if the original string is bcbd, you can change it into acbd, bebd, and so on. If the length of your string is 0, you cannot cast this spell.
• Consume R magic stones. Move the first character of your string to the end. For example, if the original string is bcbd, you can change it into cbdb. If the length of your string is 0, you cannot cast this spell.

Magic stones are expensive, so you want to minimize their consumption. Find the minimum number of magic stones needed to turn string X into string Y.

The input consists of multiple datasets. Each dataset has the following form.

X
Y
A
E
S
R

X and Y are distinct strings consisting only of lowercase English letters, and each has length between 1 and 100. A, E, S, and R are integers between 1 and 106.

The end of the input is indicated by a line containing only '#'. The input contains at most 50 datasets.

For each dataset, output on one line the minimum number of magic stones needed to turn string X into string Y.