Farmer John 丢了最喜欢的牛铃，Bessie 答应帮他寻找！他们分头沿不同路线搜索农场，用无线电保持联系。不幸的是，无线电电池快没电了，因此他们想规划行动，尽量一直保持较近的距离以节约电量。

Farmer John 从 $(f_x, f_y)$ 出发，计划走一条有 $N$ 步的路线，每步为 'N'（北）、'E'（东）、'S'（南）或 'W'（西）。Bessie 从 $(b_x, b_y)$ 出发，走类似的 $M$ 步路线。两条路线可以有公共点。每个时间步，Farmer John 可留在原地，或沿路线的下一个方向前进一步（若尚未到达路线终点）。Bessie 同样可以选择。每个时间步（不计他们位于初始位置的第一步），无线电消耗的能量等于两者距离的平方。

请帮助 FJ 与 Bessie 规划联合行动策略，使总耗能最小，计入直到两者首次都到达各自终点的最后一步。

输入格式

输入第一行包含 $N$ 和 $M$（$1 \leq N, M \leq 1000$）。第二行包含整数 $f_x$、$f_y$，第三行包含 $b_x$、$b_y$（$0 \leq f_x, f_y, b_x, b_y \leq 1000$）。下一行是描述 FJ 路线的长度为 $N$ 的字符串，最后一行是描述 Bessie 路线的长度为 $M$ 的字符串。

保证他们全程坐标都在 $0 \leq x,y \leq 1000$ 内。注意东是 $x$ 正方向，北是 $y$ 正方向。

输出格式

输出一个整数，表示 FJ 与 Bessie 行程中的最小耗能。

样例

输入格式 1

2 7
3 0
5 0
NN
NWWWWWN

输出格式 1

28

题目作者：Brian Dean