Description

农夫约翰在管理农场的所有方面都相当可靠，除了一个：他在及时或有逻辑地割草方面非常糟糕。

农场是一个由方格单元组成的二维网格。约翰从某个单元开始，在时间 $t=0$ 割掉该单元的草，因此最初该单元是唯一一个草被割掉的地方。约翰接下来的割草路线由一系列 $N$ 条指令描述。例如，如果第一条指令是 “W 10”，那么在时间 $t=1$ 到 $t=10$（即接下来的 10 个时间单位），约翰将每次向西移动一格，沿途割掉经过的所有草。完成这段移动后，他将在时间 $t=10$ 时位于距离起点向西 10 格远的单元，并且沿途所有经过的格子的草都被割掉。

约翰的割草速度非常慢，以至于在他完成所有割草之前，有些已经割过的草可能会重新长出来。任何在时间 $t$ 被割掉的草，将会在时间 $t+x$ 后重新长出来。

约翰的割草路径可能会让他多次访问同一个单元，但他注意到，每次访问一个单元时，他从未遇到过已经被割过的草。也就是说，每次访问一个单元时，他距离上一次访问该单元的时间间隔至少是 $x$，以确保草已经重新长出来。

请你确定最大的可能值 $x$，使得约翰的观察始终有效。

输入格式（文件 mowing.in）：

• 第一行输入包含整数 $N$，其中 $1 \leq N \leq 100$。
• 接下来的 $N$ 行，每行包含一个指令，形式为 "D S"，其中 $D$ 是描述方向的字符（N=北，E=东，S=南，W=西），$S$ 是在该方向上移动的步数（$1 \leq S \leq 10$）。

输出格式（文件 mowing.out）：

请确定最大的 $x$ 值，使得约翰从未踩在已经被割过草的单元上。如果约翰从未多次访问同一个单元，请输出 $-1$。

示例输入：

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

示例输出：

10

在这个例子中，约翰在时间 $t=17$ 踩在了一个他在时间 $t=7$ 访问过的单元上，因此 $x$ 必须至多为 10，否则草在他第一次访问后还没有重新长出来。他还在时间 $t=26$ 踩在了一个他在时间 $t=2$ 访问过的单元上，因此 $x$ 还必须至多为 24。由于第一个限制更严格，我们可以确定 $x$ 的最大值为 10。