题目描述

农夫约翰丢了他最喜欢的牛铃，奶牛贝西同意帮他找到它！

他们都分散开来，沿着不同的路径搜索农场，但通过无线电保持联系，以便彼此保持联系。不幸的是，他们的收音机电池电量不足，因此他们希望通过尽量保持在短距离内来规划自己的行动，以节省电力。

农民约翰从位置（$\red{fx，}$$\red{fy}$）开始，计划沿着由$\red{N}$个步骤组成的路径走，每个步骤要么是"$\red{N}$"（北）、"$\red{E}$"（东）、"$\red{S}$"（南）或"$\red{W}$"西。贝西从位置（$\red{bx，}$$\red{by}$）开始，遵循由$\red{M}$个步骤组成的类似路径。两条路径可能共享相同点。

在每一个时间步中，农夫约翰要么呆在当前位置，要么沿着自己的路径向前走一步，不管下一个方向是哪个（假设他还没有到达路径中的最终位置）。

贝西也可以做出类似的选择。在每个时间步（不包括从初始位置开始的第一步），它们的无线电消耗的能量等于它们之间距离的平方。

请帮助$\red{FJ}$和贝西规划一个联合移动策略，该策略将最大限度地减少消耗的总能量，包括他们两人首先到达各自路径上的最终位置的最后一步。

输入格式

第一行输入包含$\red{N}$和$\red{M（}$$\red{1≤}$$\red{N}$、 $\red{M≤}$$\red{1000). }$

第二行包含整数$\red{fx}$和$\red{fy}$

第三行包含$\red{bx}$和$\red{by（}$$\red{0≤}$$\red{fx}$、$\red{fy}$、$\red{bx}$、$\red{by≤}$$\red{1000). }$

下一行包含一个长度为$\red{N}$的字符串，用于描述$\red{FJ}$的路径

最后一行包含一个长度为$\red{M}$的字符串，用于描述贝西的路径。

据保证，农夫约翰和贝西的坐标始终在$\red{（0}$$\red{≤}$$\red{x}$、 $\red{y≤}$$\red{10000≤}$$\red{x}$、 $\red{y≤}$$\red{1000）}$。

请注意，东点位于正$\red{x}$方向，北点位于正$\red{y}$方向。

输出格式

输出一个整数，指定$\red{FJ}$和$\red{Bessie}$在其行程中可以使用的最小能量

样例

输入样例

2 7
3 0
5 0
NN
NWWWWWN

输出样例

28