题目描述

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

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

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

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

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

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

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

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

输出样例

10

提示

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

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

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

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

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