Косіння поля#10594
Фермер Джон досить надійний в усіх аспектах управління своєю фермою, за винятком одного: він абсолютно не вміє косити траву своєчасно та організовано.
Ферма являє собою велику двовимірну сітку квадратних клітинок, кожна з яких має одиничну площу. У момент часу t = 0 Фермер Джон починає перебувати в одній із цих клітинок і косить траву в ній, тож спочатку це єдина клітинка зі скошеною травою. Подальший маршрут Фермера Джона описується послідовністю з команд. Наприклад, якщо перша команда має вигляд "W 10", то в моменти часу від t = 1 до t = 10 (тобто протягом наступних одиниць часу) Фермер Джон на кожному кроці переміщається на одну клітинку на захід, скошуючи траву в кожній відвіданій клітинці. Після виконання цих кроків у момент часу t = 10 він опиниться на клітинок західніше своєї початкової позиції, скосивши траву в усіх клітинках, через які він пройшов.
Фермер Джон пересувається настільки повільно, що частина скошеної ним трави може встигнути вирости знову ще до того, як він закінчить косити. Будь-яка трава, скошена в момент часу , знову виростає в момент часу t + x.
Маршрут Фермера Джона може призвести до того, що він кілька разів відвідає одну й ту саму клітинку. Проте він помічає, що ніколи не відвідує клітинку, поки трава в ній усе ще скошена. Іншими словами, кожного разу, коли він відвідує клітинку, його попереднє відвідування цієї ж клітинки має відбутися щонайменше за одиниць часу до цього, щоб трава встигла вирости знову.
Визначте максимально можливе значення , при якому спостереження Фермера Джона залишається правильним.
У першому рядку міститься ціле число n~(1 \le n \le 100). У кожному з наступних рядків міститься команда вигляду "d s", де — символ, що задає напрямок ( = північ, = схід, = південь, = захід), а s~(1 \le s \le 10) — кількість кроків, які необхідно зробити в цьому напрямку.
Виведіть максимальне значення , при якому Фермер Джон ніколи не наступає на клітинку зі скошеною травою. Якщо Фермер Джон жодну клітинку не відвідує більше одного разу, виведіть .
У цьому прикладі Фермер Джон відвідує клітинку в момент часу , яку він раніше відвідував у момент часу . Отже, має бути не більше ; інакше трава після першого відвідування ще не встигла б вирости. Він також відвідує клітинку в момент часу , яку раніше відвідував у момент часу , тому також має бути не більше . Оскільки перше з цих двох обмежень є суворішим, отримуємо, що може бути не більше .
Приклад 1