Delete String

Given two strings and a cost array, find the minimum cost to make the strings equal by deleting characters. Deletions may be made from either string, in any order.

Each lowercase letter has its own deletion cost: costs[0] is the price of removing one 'a', costs[1] one 'b', and so on through costs[25] for 'z'. Removing a letter costs the same whichever string it came from, and the total is the sum over every deletion in both strings.

Input & Output

Input

costs — the deletion cost of each lowercase letter, indexed costs[0] for 'a' through costs[25] for 'z'

s1 — the first string

s2 — the second string

Output

the minimum total cost of the deletions that make the two strings equal

Example

Input

costs = [1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
s1 = abb
s2 = bba

Output

Explanation

With a costing 1 and b costing 2, delete the a from each string, paying 1 each time. Both strings become "bb", for a total of 2. Every other outcome is worse: leaving a single b costs 6, leaving a single a costs 8, and deleting everything costs 10.

Example

Input

costs = [1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
s1 = abc
s2 = cba

Output

Explanation

The strings are reverses of each other, so no two characters survive in the same order in both and whatever is left must be a single letter. Keeping the letter that is most expensive to delete, c, means deleting a and b from each string: (1 + 2) + (2 + 1) = 6. Keeping b would cost 8 and keeping a would cost 10.

Constraints

1 <= s1.length, s2.length <= 1000
s1 and s2 consist of lowercase English letters
costs[i] is the deletion cost of the letter 'a' + i, with 0 <= costs[i] <= 10^4
costs is indexed by letter, so only its first 26 entries are ever read
The answer fits in a 32-bit signed integer

Delete String

Try it yourself