Farmer John perdió su cencerro favorito y Bessie acepta ayudar a buscarlo. Recorren distintos caminos por la granja, manteniendo contacto por radio. Pero las baterías se agotan: quieren planificar sus movimientos para permanecer siempre cerca y ahorrar energía.

Farmer John parte de $(f_x, f_y)$ y sigue $N$ pasos, cada uno 'N' (norte), 'E' (este), 'S' (sur) o 'W' (oeste). Bessie parte de $(b_x, b_y)$ y sigue un camino similar de $M$ pasos. Pueden compartir puntos. En cada instante, Farmer John puede quedarse o, si no terminó su camino, avanzar un paso en la siguiente dirección del mismo. Bessie elige igual. En cada instante salvo el inicial, las radios consumen energía igual al cuadrado de su distancia.

Ayúdales a planificar una estrategia conjunta que minimice la energía total hasta el instante en que por primera vez ambos hayan llegado a sus respectivos finales, incluyéndolo.

Entrada

La primera línea contiene $N$ y $M$ ($1 \leq N, M \leq 1000$), la segunda los enteros $f_x$, $f_y$, la tercera $b_x$, $b_y$ ($0 \leq f_x, f_y, b_x, b_y \leq 1000$). La siguiente es una cadena de longitud $N$ con el camino de FJ y la última una de longitud $M$ con el de Bessie.

Sus coordenadas siempre están en $0 \leq x,y \leq 1000$. El este es la dirección positiva de $x$ y el norte la de $y$.

Salida

Imprime un entero con la energía mínima durante su viaje.

Ejemplos

Entrada 1

2 7
3 0
5 0
NN
NWWWWWN

Salida 1

28

Autor del problema: Brian Dean