Radio Contact#10599
Farmer John has lost his favorite cow bell, and Bessie the cow has agreed to help him find it! They fan out and search the farm along different paths, but stay in contact via radio so they can keep in touch with each other. Unfortunately, the batteries in their radios are running low, so they want to plan their movements to conserve power by trying to stay as close to each other as possible.
Farmer John starts at location (f_x, f_y) and plans to follow a path consisting of steps, each of which is either '' (north), '' (east), '' (south), or '' (west). Bessie starts at location (b_x, b_y) and follows a similar path consisting of steps. The two paths may have points in common. At each time step, Farmer John can either remain at his current location or take one step forward along his path, in whichever direction comes next (provided he has not yet reached the end of his path). Bessie can make the same choice.
At each time step, except for the initial time when they are at their starting locations, their radios consume an amount of energy equal to the square of the distance between them.
Please help FJ and Bessie plan a joint movement strategy that minimizes the total amount of energy consumed up to and including the time step when they first reach the final locations on their respective paths.
The first line contains two integers and m~(1 \le n, m \le 1000). The second line contains two integers f_x and f_y, and the third line contains two integers b_x and b_y~(0 \le f_x, f_y, b_x, b_y \le 1000). The next line contains a string of length describing FJ's path, and the final line contains a string of length describing Bessie's path.
It is guaranteed that Farmer John and Bessie's coordinates always remain within the range 0 \le x, y \le 1000 throughout their journeys. Note that east corresponds to the positive -direction, while north corresponds to the positive -direction.
Print the minimum amount of energy that FJ and Bessie can consume during their travels.
Example 1