Скошування поля

Фермер Джон косить траву.

Ферма представлена двовимірною сіткою квадратних клітинок. Фермер Джон починає з однієї з цих клітинок у момент часу t = 0, косячи траву в цій клітинці. Спочатку трава викошена лише в цій клітинці. Подальші дії фермера Джона описуються послідовністю з n команд. Наприклад, якщо перша команда "W 10", то протягом часу від t = 1 до t = 10 (тобто, наступні 10 одиниць часу), фермер Джон буде рухатися по 1 клітинці на захід, косячи траву в кожній клітинці на своєму шляху.

Фермер Джон косить траву так повільно, що вона може встигнути вирости знову, перш ніж він завершить процес. Будь-яка клітинка трави, яку викосили в момент часу t, виросте знову в момент часу t + x.

Згідно з послідовністю команд, фермер Джон може відвідувати деякі клітинки багато разів, але він не хоче відвідувати клітинки, в яких трава ще не виросла. Тобто, кожен раз, коли він відвідує клітинки, його попередній візит у цю клітинку повинен бути не менше ніж на x одиниць часу раніше, щоб викошена в цій клітинці трава встигла вирости знову.

Визначте максимальне значення x, при якому буде виконуватися побажання фермера Джона.

Вхідні дані

Перший рядок вводу містить n (1 ≤ n ≤ 100). Кожен з наступних n рядків містить одну команду у вигляді "d s", де d - це символ напрямку (N = північ, E = схід, S = південь, W = захід), а s (1 ≤ s ≤ 10) - кількість кроків, виконаних у цьому напрямку.

Вихідні дані

Будь ласка, визначте максимальне значення x, таке, що фермер Джон ніколи не ступить на клітинку, де трава ще не виросла. Якщо фермер Джон ніколи не заходить у клітинку повторно, виведіть -1.

Приклади

Примітка

У цьому прикладі в момент часу 17 фермер Джон потрапить у клітинку, в якій він вже був у момент часу 7. Тому x має бути не більше ніж 10, інакше до моменту другого відвідування трава не встигне вирости. У момент часу 26 він також потрапить у клітинку, в якій він був у момент часу 2. Отже, x має бути не більше ніж 24. З цих двох обмежень вибираємо менше - 10.