Farmer John hat seine Lieblingskuhglocke verloren, und Bessie hilft beim Suchen! Sie suchen auf verschiedenen Wegen durch die Farm und halten Funkkontakt. Doch die Batterien werden schwach, also wollen sie ihre Bewegungen planen, um stets nahe beieinander zu bleiben und Energie zu sparen.

Farmer John startet bei $(f_x, f_y)$ und folgt einem Weg aus $N$ Schritten, jeweils 'N' (Norden), 'E' (Osten), 'S' (Süden) oder 'W' (Westen). Bessie startet bei $(b_x, b_y)$ auf einem ähnlichen Weg aus $M$ Schritten. Die Wege dürfen gemeinsame Punkte haben. In jedem Zeitschritt kann Farmer John stehen bleiben oder, falls er noch nicht am Ende ist, einen Schritt in der nächsten Richtung seines Weges machen. Bessie wählt ebenso. In jedem Zeitschritt außer dem ersten an den Startpositionen verbrauchen die Funkgeräte Energie gleich dem Quadrat ihres Abstands.

Plane eine gemeinsame Strategie mit minimalem Gesamtverbrauch bis einschließlich des letzten Schritts, in dem erstmals beide ihre jeweiligen Endpositionen erreicht haben.

Eingabe

Die erste Zeile enthält $N$ und $M$ ($1 \leq N, M \leq 1000$), die zweite ganze Zahlen $f_x$, $f_y$, die dritte $b_x$, $b_y$ ($0 \leq f_x, f_y, b_x, b_y \leq 1000$). Die nächste Zeile enthält eine Zeichenkette der Länge $N$ für FJs Weg, die letzte eine der Länge $M$ für Bessies Weg.

Alle Koordinaten bleiben während der Reise in $0 \leq x,y \leq 1000$. Osten ist die positive $x$-Richtung, Norden die positive $y$-Richtung.

Ausgabe

Gib eine ganze Zahl für die minimale Energie während ihrer Reise aus.

Beispiele

Eingabe 1

2 7
3 0
5 0
NN
NWWWWWN

Ausgabe 1

28

Aufgabenautor: Brian Dean