Farmer John ha perso il suo campanaccio preferito e Bessie accetta di aiutarlo! Cercano nella fattoria lungo percorsi diversi, restando in contatto via radio. Ma le batterie si scaricano, quindi vogliono pianificare i movimenti per restare sempre vicini e risparmiare energia.

Farmer John parte da $(f_x, f_y)$ su un percorso di $N$ passi, ciascuno 'N' (nord), 'E' (est), 'S' (sud) o 'W' (ovest). Bessie parte da $(b_x, b_y)$ su uno simile di $M$ passi. I percorsi possono avere punti comuni. A ogni istante Farmer John resta fermo oppure, se non è alla fine, avanza un passo nella prossima direzione del percorso. Bessie sceglie allo stesso modo. A ogni istante, escluso il primo nelle posizioni iniziali, le radio consumano il quadrato della distanza tra loro.

Aiutateli a pianificare una strategia comune che minimizzi l’energia totale fino all’istante in cui entrambi raggiungono per la prima volta le rispettive posizioni finali, incluso tale istante.

Input

La prima riga contiene $N$ e $M$ ($1 \leq N, M \leq 1000$), la seconda gli interi $f_x$, $f_y$, la terza $b_x$, $b_y$ ($0 \leq f_x, f_y, b_x, b_y \leq 1000$). La successiva è una stringa di lunghezza $N$ per il percorso di FJ e l’ultima di lunghezza $M$ per quello di Bessie.

Le coordinate restano sempre in $0 \leq x,y \leq 1000$. Est è il verso positivo di $x$ e nord quello di $y$.

Output

Stampate un intero, l’energia minima durante il viaggio.

Esempi

Input 1

2 7
3 0
5 0
NN
NWWWWWN

Output 1

28

Autore del problema: Brian Dean