C - Educación física

Time limit: 1 s
Memory limit: 256 MiB
Languages: C, C++, Java, JavaScript, ... (details)

Como en toda escuela, en la de Fito se dan clases de educación física. Desafortunadamente, hay muchos grupos, pero solo un profesor. Por lo cual los $n$ grupos tienen que dar la clase juntos. 

Al comienzo de la clase los estudiantes de cada grupo forman fila, luego el profesor ordena los grupos en cierto orden, pero sin cambiar la fila formada en cada grupo. Después de tener una sola fila, los estudiantes comenzan a enumerarse de la siguiente forma: "Uno", "Dos", "Uno", "Dos", etc. Los estudiantes que dijeron "Uno" forman el primer grupo y los restantes el segundo. El primer grupo va a jugar futbol y el segundo voleibol. A los chicos les gusta jugar futbol, pero a las chicas no, por lo que el profesor quiere arreglarlos en un orden de forma tal que la mayor cantidad de chicos le toque jugar futbol. Ayúdalo a encontrar la mayor cantidad de muchachos que pueden juegar al futbol.

Input

La primera línea de la entrada contiene un entero $n$ ($1 \le n \le 100{\,}000$) - la cantidad de grupos. Las siguientes $n$ líneas contienen la descripción de la fila formada en cada grupo. Cada una es un string de letras B y G . La letra B significa un chico y la G una chica. La primera letra en el string corresponde al primer estudiante en la fila. La cantidad total de estudiantes no es mayor que $1000000$.

Output

Imprima un único entero - la mayor cantidad de chicos que puede jugar al futbol.

Sample test(s)

Input
4 BB GBG BGG GG
Output
3

Hints

En el ejemplo no es posible que todos los chicos juegen al futbol, pero si los ordenamos así: BGG , BB , GG , GBG , pueden jugar 3.