The one of the edition distance (I) P26005

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₁ and w₂ 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₁ and w₂ 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₁ and w₂ identical.