Во една фабрика биле произведени N парови патики од исти модел и исти број. Тие биле набрзина спакувани во кутии, но не било внимавано да има и лева и десна патика во секоја кутија. Сега кутиите треба да се пратат до продавниците, но претходно мора да се преуредат така што во секоја кутија да има точно по еден пар од лева и десна патика.

За точно да се распределат патиките во кутиите, кутиите биле наредени на една лента, една до друга. Задачата точно да ги распредели патиките му е дадена на робот кој се движи по шина и може да ги пристапи кутиите поставени на лентата. Но, роботот покрај движењето по шината може да изврши само уште една операција со назив ЗАМЕНИ. Во операција ЗАМЕНИ, роботот заменува една произволна патика од една кутија со друга произволна патика од кутија која е соседна на дадената.

Со колку најмалку операции ЗАМЕНИ роботот може точно да ги распредели патиките во кутиите како што треба (во секоја кутија да има точно една лева и точно една десна патика)?

Влез

Во првиот ред се наоѓа бројот на кутии N (1<=N<=1 000 000).
Во следните i-редови се наоѓаат по два знака кои означуваат какви патики има во i-тата кутија (D- десна патика, L- лева патика). Кутиите се дадени во истиот редослед како што се наредени на лентата.
Забелешка:Во случаи кои носат 50% од поените ќе важи дека 1 <= N <= 1 000.

Излез

Во единствениот ред се печати најмалиот број на операции ЗАМЕНИ кои треба да ги направи роботот за точно да ги распредели патиките во кутиите.

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

Временско ограничување: 2 seconds
Мемориско ограничување: 256 megabytes

Примери

влез
3
LL
DL
DD

излез
2

влез
4
LL
DD
LL
DD

излез
2

влез
3
DL
DL
LD

излез
0

Објаснување за првиот тест пример: Роботот треба да направи најмалку 2 операции ЗАМЕНИ. Во првата опрација ќе замени една лева патика од првата кутија со една десна патика од втората кутија. По оваа операција, во првата кутија ќе има една лева и една десна патика, а во втората ќе има две леви патики. Во втората операција ќе замени една лева патика од втората кутија со една десна патика од третата кутија. По ова во сите три кутии ќе има по една лева и една десна патика.

Објаснување за вториот тест пример: Роботот треба да направи најмалку две операции ЗАМЕНИ. Во првата операција ЗАМЕНИ може да се замени една лева патика од првата кутија со една десна патика од втората кутија. Во втората операција може да се замени една лева патика од третата кутија со една десна патика од четвртата кутија.