题目描述

农民约翰在管理农场的各个方面都相当可靠，除了一点：他不善于及时或合乎逻辑地割草。

农场是一个由正方形单元组成的大型${2D}$网格。

${FJ}$在时间${t=0}$时在其中一个单元中开始，在该单元中割草，使其最初是唯一割草的单元。${FJ}$的剩余割草模式由 一系列${N}$语句描述。

例如，如果第一个语句为"${W 10}$"，则对于时间${t=1}$到${t=10（}$即接下来的${10}$个时间单位），${FJ}$ 将向其西部移动一个单元格，沿途割草。

在完成这一系列步骤后，他将在时间${t=10}$时在他西边的${10}$个牢房结束，一路上每个牢房都割草了。

${FJ}$的进度如此缓慢，以至于在他完成所有割草之前，他割草的一些草可能会长回来。

在${t}$时割草的任何部分都将在${t+x}$时重新出现。${FJ}$的割草模式可能会让他多次访问同一个单元格，但他说，他从未遇到过一个已经割草的单元格。

也就是说，每次他访问一个牢房时，他最近一次访问同一牢房的时间必须至少提前${x}$个单位， 这样草才能长回来。

请确定${x}$的最大可能值，以便${FJ}$的观察结果仍然有效。

输入格式

第一行输入包含${N（}$${1≤}$${N≤}$${100).}$

剩余的${NN}$行中的每一行都包含一条语句，其形式为"${D S}$"，其中${D}$是描述方向的字符（${N=}$北，${E=}$东，${S=}$南，${W=}$西），${S}$是在该方向上采取的步数${（1≤}$${S≤}$${10).}$

输出格式

请确定${x}$的最大值，以便${FJ}$不会踩到割草的单元格。 如果${FJ}$从未访问过任何单元格一次以上，请输出${-1}$。

样例

输入样例

6
N 10
E 2
S 3
W 4
S 5
E 8

输出样例

10

提示

在本例中，${FJ}$在时间${17}$踏上了他之前在时间${7}$踏上的单元格；

因此，${x}$最多只能活${10}$岁，否则他第一次来的草就长不回来了。

他还在时间${26}$踏上了一个牢房，他也在时间${2}$访问了这个牢房；

因此${x}$最多也必须是${24}$。

由于这两个约束中的第一个约束更紧，我们可以看到${x}$最多可以是${10}$。