Миле и Невена се судии на натпревар по роботика, каде што групи на ученици се обидуваат да напишат програма за автономна кола. Програмирањето на колата учениците го прават преку пишување на произволен број на функции, каде што секоја функција претставува листа од неколку наредби:

  - NAPRED (со која колата се придвижува еден метар напред),
  - LEVO (колата се ротира 90 степени на лево),
  - DESNO (колата се ротира 90 степени на десно), и
  - Fx (повик до функцијата Fx, па потоа враќање во тековната функција
    и продолжување со извршување на следните наредби).

Миле и Невена сакаат да ги оценуваат учениците така што ќе влезат во автономната кола и ќе патуваат заедно со неа. Сепак, пред да го направат тоа, тие сакаат да знаат колку далеку од почетната позиција ќе дојде колата (за да не залутаат некаде - ако тимот што програмирал е лош), преку разгледување на сите точки (x, y) кои што ќе ги посети колата, и пресметување на максималната вредност на изразот |x|+|y|. Почетната позиција на колата е на локација (0, 0), а програмата започнува со извршување од првата наредба во функцијата F1.

Ваша задача е да напишете програма која што ќе ја пресмета бараната максимална вредност на |x|+|y|. Имајте предвид дека, кај одредени програми, колата никогаш нема да запре со движење. На пример, замислете програма со функција F1: { NAPRED; F2; }, и функција F2: { F1; }. Во случај кога колата бесконечно ќе се оддалечува од почетната локација, потребно е да отпечатите -1.

Влез

Во првата линија е запишан еден цел број N (1 <= N <= 100), кој го означува бројот на функции. Во секоја од следните N линии е дадена по една функција Fx, во следниот формат:

      Fx: { NAREDBA1; NAREDBA2; NAREDBA3; .... }

каде што со x е означен бројот на функцијата. Функциите, на влез, се дадени по редослед, според нивниот број - соодветно прво е дадена функцијата F1, па F2, па F3, ... итн. Една функција може да содржи најмногу 100 наредби.

Забелешка: Во тест случаи кои ќе носат најмалку 30% од поените, ќе важи (1 <= N <= 3) и функциите ќе имаат по најмногу 10 наредби.

Излез

Отпечатете -1, или бараната максимална вредност на изразот |x|+|y|.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
1
F1: { NAPRED; LEVO; LEVO; NAPRED;
 LEVO; LEVO; NAPRED; F1; }

излез
-1

влез
2
F1: { F2; NAPRED; F2; F2; NAPRED; F2; }
F2: { NAPRED; LEVO; NAPRED; LEVO;
 NAPRED; LEVO; NAPRED; LEVO; NAPRED; }

излез
7

влез
2
F1: { NAPRED; LEVO; NAPRED; LEVO;
 NAPRED; LEVO; NAPRED; LEVO; F2; }
F2: { F1; }

излез
2

Објаснување за вториот пример: Види слика.

Објаснување за третиот пример: Колата ќе се врти во круг и ќе ги посетува позициите (0, 0), (1, 0), (1, 1) и (0, 1). Максималната вредност е |1|+|1| = 2.