Some problems are so classic that barely need a statement.
For this one, please compute
the minimum cost to insert letters into two words w_{1} and w_{2}
to make them identical.
Both words are made up of only letters chosen
among the n smallest lowercase letters
(for instance, for n=4, the alphabet is {a, b, c, d}).
For every letter (call it x),
inserting an x in any place in any word has cost I_{x}.

Input

Input consists of several cases.
Each case begins with 2≤ n≤ 26,
followed by n strictly positive natural numbers
I_{a}, I_{b}, I_{c}, ….
Follow two words w_{1} and w_{2} made up of between 1 and 1000 lowercase letters
chosen among the n smallest letters.
Assume 1≤ I_{x}≤ 1000 for every letter x.

Output

For every case, print the minimum cost
to make w_{1} and w_{2} identical.

Public test cases

**Input**

2 11 10 aaa aba 4 100 100 100 1 abcd bcda 3 1 10 100 abbcabccabbac bbcabacabbac 4 1 2 1 4 dcbbcbbddccdabdbdbdcbbc cddcab

**Output**

21 200 102 40

Information

- Author
- Omer Giménez
- Language
- English
- Translator
- Carlos Molina
- Original language
- Spanish
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++ Python