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₁ y p₂ 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 ⌈ (I_x+I_y)/4⌉, 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≤ n≤ 26, seguido de n ‍naturales estrictamente positivos I_a, I_b, I_c, …. Siguen dos palabras p₁ y p₂ con entre 1 y 1000 letras minúsculas elegidas entre las n primeras. Podéis asumir 1≤ I_x≤ 1000 para cada letra x.

Salida

Para cada caso, escribid el coste mínimo de conseguir que p₁ y p₂ sean idénticas.