The one of the edition distance (II) P48188

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₁ 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. 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₁ 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.