题目描述

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

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

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

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

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

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

输入格式

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

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

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

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

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

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

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

输出格式

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

样例

输入样例

2 7
3 0
5 0
NN
NWWWWWN

输出样例

28