Mowing the Field

Farmer John is reliable at almost every part of running his farm, with one exception: he is terrible at mowing the grass promptly or in any sensible order.

The farm is a large 2D grid of square unit cells. At time $t = 0$ John starts in one of these cells and mows the grass there, so at first that cell is the only one with cut grass. The rest of his route is given by $N$ statements. For example, if the first statement is "W 10", then for times $t = 1$ through $t = 10$, that is the next 10 units of time, John steps one cell west at a time and mows the grass in every cell he passes. After finishing that statement he stands 10 cells west of where he started at time $t = 10$, and the grass in every cell along the way is cut.

John works so slowly that some of the grass he cuts grows back before he is done. Grass cut at time $t$ reappears at time $t + x$.

John may pass through the same cell several times, but he says he never stepped on a cell whose grass was still cut. That is, every time he steps on a cell, his previous visit to that same cell was at least $x$ units of time earlier, so the grass had already grown back.

Find the largest value of $x$ for which John's claim holds.

The first line contains $N$ ($1 \le N \le 100$). Each of the next $N$ lines contains one statement in the form "D S". D is a character giving a direction, where N is north, E is east, S is south and W is west. S is the number of steps taken in that direction, with $1 \le S \le 10$.

Print on one line the largest value of $x$ for which John never steps on a cell with cut grass. If John never visits any cell more than once, print -1.

In the sample, John steps at time 17 on a cell he already stepped on at time 7, so $x$ can be at most 10. Otherwise the grass from the first visit has not grown back yet. He also steps at time 26 on a cell he visited at time 2, so $x$ is also at most 24. The first constraint is the tighter one, so the largest $x$ is 10.