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