Radio Contact

Farmer John lost his favorite cow bell, and Bessie the cow agreed to help him find it. The two spread out and search the farm along different paths, and they keep in touch by radio. The radio batteries are almost empty, so they want to stay close to each other and save power.

Farmer John starts at $(f_x, f_y)$ and follows a path of $N$ steps. Each step is one of 'N' (north), 'E' (east), 'S' (south), or 'W' (west). Bessie starts at $(b_x, b_y)$ and follows a path of $M$ steps in the same format. The two paths may pass through the same point.

At each time step Farmer John either stays where he is, or takes the next step of his path if any step is left. Bessie makes the same choice for herself. Except for the first time step, where both stand at their starting positions, the radios spend energy equal to the square of the distance between the two positions at every time step.

Plan the movements so that the total energy spent up to the time step where both first stand on the last point of their own path is as small as possible. Report that total.

The first line contains $N$ and $M$ ($1 \le N, M \le 1000$). The second line contains $f_x$ and $f_y$, and the third line contains $b_x$ and $b_y$ ($0 \le f_x, f_y, b_x, b_y \le 1000$). The fourth line contains a string of length $N$ describing Farmer John's path, and the fifth line contains a string of length $M$ describing Bessie's path.

Both coordinates stay in the range $0 \le x, y \le 1000$ during the whole journey. East is the direction of increasing $x$, and north is the direction of increasing $y$.

Print one integer, the smallest total energy the radios can spend.