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_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\leq n\leq 26$, followed by $n$ strictly positive natural numbers $I_{\mbox{\texttt{a}}}, I_{\mbox{\texttt{b}}}, I_{\mbox{\texttt{c}}}, \ldots$. 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\leq I_x\leq 1000$ for every letter $x$.

Output

For every case, print the minimum cost to make $w_1$ and $w_2$ identical.