P3133 [USACO16JAN] Radio Contact G

题目描述

FJ 失去了他最喜欢的牛铃，而 Bessie 已经同意帮助他找到它！他们用不同的路径搜索农场，通过无线电保持联系。

不幸的是，无线电中的电池电量不足，所以他们设法尽可能保持两者位置的距离最小，以节省电量。

FJ 从位置$(f_x,f_y)$ 开始，并计划遵循由 $N$ 步组成的路径.Bessie 从位置 $(b_x,b_y)$ 开始，并遵循由 $M$ 步组成的路径。每个步骤都是 N（北），E（东），S（南），或W（西）。其中，东方向为 $x$ 轴正方向，北方向为 $y$ 轴正方向。两个路径可以经过相同的点。

在每个时间段，FJ 可以不移动，也可以沿着他的道路前进一步。无论哪个方向恰好在下一个（假设他还没有到达他的路径的最后位置）。Bessie 可以做出类似的选择。

在每个时间点（不包括从初始位置开始的第一步），他们的无线电消耗的能量等于它们之间距离的平方。

请帮助 FJ 和 Bessie 计划行动策略，使双方达到各自终点时，最大限度地减少消耗的能量总量。输出所消耗的最小的能量。

输入格式

第一行两个整数 $N$ 和 $M$ $(1\le N,M\le 1000)$。

第二行两个整数 $f_x$ 和 $f_y$。

第三行两个整数 $b_x$ 和 $b_y$ $(0\le f_x,f_y,b_x,b_y\le 1000)$。

下一行为一个长度为 $N$ 的字符串，描述 FJ 的路径。

最后一行为一个长度 $M$ 的字符串，描述 Bessie 的路径。

输出格式

共一行一个整数，表示最小能量。

输入输出样例 1

2 7
3 0
5 0
NN
NWWWWWN

28