A text-repair tool transforms a source string s into a target string t using three kinds of single-character operations, each with its own fixed cost: inserting one character anywhere, deleting one character, or substituting one character for a different character. Given the three costs and the two strings, find the minimum total cost of a sequence of operations that turns s into t. Substituting a character for itself is never necessary and is not considered a valid use of the substitute operation.

Input format

Line 1: three integers insCost, delCost, subCost. Line 2: the source string s (may be empty, producing a blank line). Line 3: the target string t (may be empty, producing a blank line).

Both s and t contain only lowercase English letters.

Output format

A single integer: the minimum total cost to transform s into t.

Constraints

• 1 <= insCost, delCost, subCost <= 20
• 0 <= |s|, |t| <= 40

1 1 10
cat
cot

2

5 5 1
abc
abd

1