Farmer John has lost his favorite cow bell, and Bessie the cow has agreed to help him find it! They both 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 so as to conserve power, by trying to stay always within a short distance apart.
Farmer John starts at location (\(f_x, f_y\)) and plans to follow a path consisting of \(N\) steps, each of which is either 'N' (north), 'E' (east), 'S' (south), or 'W' west. Bessie starts at location (\(b_x, b_y\)) and follows a similar path consisting of \(M\) steps. Both paths may share points in common. At each time step, Farmer John can either stay put at his current location, or take one step forward along his path, in whichever direction happens to be next (assuming he has not yet reached the final location in his path). Bessie can make a similar choice. At each time step (excluding the first step where they start at their initial locations), their radios consume energy equal to the square of the distance between them.
Please help FJ and Bessie plan a joint movement strategy that will minimize the total amount of energy consumed up to and including the final step where both of them first reach the final locations on their respective paths.
FJ失去了他最喜歡的牛鈴，而Bessie已經同意幫助他找到它！他們用不同的路徑搜尋農場，通過無線電保持聯絡。不幸的是，無線電中的電池電量不足，所以他們設法儘可能保持兩者位置的距離最小，以節省電量。
FJ從位置（fx，fy）開始，並計劃遵循由N步驟組成的路徑，每個步驟都是「N」（北），「E」（東），「S」（南），或「W」（西）。Bessie從位置（bx，by）開始，並遵循由M步驟組成的類似路徑。兩個路徑可以經過相同的點。在每個時間段，FJ可以保持在他現在的位置，或沿著他的道路前進一步，無論哪個方向恰好在下一個（假設他還沒有到達他的路徑的最後位置）。Bessie可以做出類似的選擇。在每個時間步（不包括從初始位置開始的第一步），他們的無線電消耗的能量等於它們之間距離的平方。
請幫助FJ和Bessie計劃行動策略，最大限度地減少消耗的能量總量。總量包括最終步驟，這時兩者首先到達各自路徑上的最終位置。
The first line of input contains \(N\) and \(M\) (\(1 \leq N, M \leq 1000\)). The
second line contains integers \(f_x\) and \(f_y\), and the third line contains \(b_x\)
and \(b_y\) (\(0 \leq f_x, f_y, b_x, b_y \leq 1000\)). The next line contains a
string of length \(N\) describing FJ's path, and the final line contains a string
of length \(M\) describing Bessie's path.
It is guranteed that Farmer John and Bessie's coordinates are always in the
range (\(0 \leq x,y \leq 1000\)) throughout their journey. Note that East points in the positive x direction and North points in the positive y direction.
第一行輸入N和M（1≤N，M≤1000）。
第二行輸入整數fx和fy，第三行輸入bx和by（0≤fx，fy，bx，≤1000）。下一行包含一個長度為N的字串描述FJ的路徑，最後一行包含一個字串的長度M描述Bessie的路徑。
資料滿足（0≤x，y≤1000）。注意，東方向為正X方向，北方向為正Y方向。
Output a single integer specifying the minimum energy FJ and Bessie can use
during their travels.
輸出一個整數，表示最小能量。
2 7
3 0
5 0
NN
NWWWWWN
28
感謝@ prcups 改進翻譯
先分別求出農夫和奶牛沒走一步到達的點
設 \(dp_{i , j}\) 當農夫走了 \(i\) 步，奶牛走了 \(j\) 步後的最小花費
那麼
注意判斷越界條件，\(dp_{0 , 0} = 0\)
考試時 \(dis\) 打錯了，差點就寄了。