El de la distancia de edición (II) P48188

A estas alturas, seguro que ya os suena lo de que algunos problemas son tan clásicos que bla, bla, bla. Nada nuevo: éste también lo es. Ahora, os pedimos que calculéis el coste mínimo de insertar letras o de modificar letras en dos palabras $p_1$ y $p_2$ para hacerlas idénticas. Ambas palabras están compuestas por letras escogidas de entre las $n$ primeras minúsculas (por ejemplo, para $n=4$, el alfabeto es $\{a, b, c, d\}$). Para cada letra (llamémosle $x$), insertar una $x$ en cualquier lugar de cualquier palabra tiene coste $I_x$. El coste de transformar una letra $x$ en una letra $y$ viene dado por $\lceil (I_x+I_y)/4\rceil$, es decir, una cuarta parte, redondeando para arriba, de la suma de los costes de inserción $I_x$ y $I_y$.

Entrada

La entrada consiste en diversos casos. Cada caso empieza con $2\leq n\leq 26$, seguido de $n$ naturales estrictamente positivos $I_{\mbox{\texttt{a}}}, I_{\mbox{\texttt{b}}}, I_{\mbox{\texttt{c}}}, \ldots$. Siguen dos palabras $p_1$ y $p_2$ con entre 1 y 1000 letras minúsculas elegidas entre las $n$ primeras. Podéis asumir $1\leq I_x\leq 1000$ para cada letra $x$.

Salida

Para cada caso, escribid el coste mínimo de conseguir que $p_1$ y $p_2$ sean idénticas.