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