Farmer John a perdu sa cloche préférée et Bessie accepte de l’aider ! Ils explorent la ferme sur des chemins différents tout en gardant contact par radio. Mais leurs piles faiblissent : ils veulent planifier leurs déplacements pour rester toujours proches et économiser l’énergie.

Farmer John part de $(f_x, f_y)$ et suit un chemin de $N$ pas, chacun 'N' (nord), 'E' (est), 'S' (sud) ou 'W' (ouest). Bessie part de $(b_x, b_y)$ sur un chemin similaire de $M$ pas. Les chemins peuvent partager des points. À chaque instant, Farmer John reste sur place ou, s’il n’a pas atteint la fin, avance d’un pas dans la prochaine direction du chemin. Bessie fait un choix analogue. À chaque instant, sauf le premier où ils sont aux positions initiales, les radios consomment le carré de la distance qui les sépare.

Aidez-les à planifier une stratégie commune minimisant l’énergie totale jusqu’à l’instant où ils atteignent pour la première fois tous deux leurs positions finales respectives, cet instant inclus.

Entrée

La première ligne contient $N$ et $M$ ($1 \leq N, M \leq 1000$), la deuxième les entiers $f_x$, $f_y$, la troisième $b_x$, $b_y$ ($0 \leq f_x, f_y, b_x, b_y \leq 1000$). La ligne suivante est une chaîne de longueur $N$ décrivant le chemin de FJ ; la dernière, de longueur $M$, celui de Bessie.

Les coordonnées restent dans $0 \leq x,y \leq 1000$ durant tout le trajet. L’est est le sens positif de $x$, le nord celui de $y$.

Sortie

Affichez un entier indiquant l’énergie minimale de leur trajet.

Exemples

Entrée 1

2 7
3 0
5 0
NN
NWWWWWN

Sortie 1

28

Auteur du problème : Brian Dean