At this stage, you surely already know
that some problems are so classic that blah, blah, blah.
Nothing new with this problem.
Now, we ask you to compute
the minimum cost to insert letters into or to modify letters from
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}.
The cost to transform a letter x into a letter y
is given by ⌈(I_{x}+I_{y})/4⌉,
i.e., a fourth part, ceiling, of the sum fo the insertion costs I_{x} and I_{y}.

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**

6 54 27 35

Information

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