割草

题目描述

农夫约翰在管理农场的各个方面都很可靠，只有一个例外：他不善于及时或合乎逻辑地割草。

农场可以看作一个大型二维方格矩阵。

$t=0$ 时，约翰从某个方格处开始割草，该方格最初是唯一被割草的方格。

剩余的割草方式可用 $N$ 条语句序列形容。

例如，如果第一个语句是 “$W 10$”，则对于时间 $t=1$ 到 $t=10$（即接下来的 $10$ 个单位时间），每单位时间约翰将向西移动一个方格的距离。

完成这一系列移动后，他共向西移动十个方格的距离，并沿途割草。

约翰的前进速度十分缓慢，以至于在他修剪完所有草之前，一些修剪过的草可能会重新长出。

在时间 $t$ 割下的草会在时间 $t+x$ 重新长出。

约翰的割草方式可能会让他多次重访同一个方格。

可约翰却指出自己从未遇到过已经割过草的方格。

也就是说，当他到达某一方格时，距离他上次到达该方格，至少过了 $x$ 的时间。

请确定能够满足约翰从未遇到过已经割过草的方格的 $x$ 的最大值。

输入格式

第一行包含整数 $N$。

接下来 $N$ 行，每行包含一个语句，格式为 “$D S$”，其中 $D$ 是描述方向的字符（$N =$ 北，$E =$ 东，$S =$ 南，$W =$ 西），$S$ 是沿该方向移动的次数。

输出格式

请确定 $x$ 的最大值。

如果约翰从未进入过同一方格两次或以上，则输出 $-1$。

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

10

提示

#### 数据范围 $1\le N\le 100,1\le S\le 10$

样例解释

在此样例中，约翰在 $t=17$ 时进入的方格曾在 $t=7$ 时进入过，因此 $x$ 不能超过 $10$。

在 $t=26$ 时进入的方格曾在 $t=2$ 时进入过，因此 $x$ 不能超过 $24$。

综上，$x$ 最大为 $10$。

来源

童程童美