Zadanie

Fezjo sa hrá s dominami

Počet bodov: 30, časový limit: 300ms

Fezjo je flákač. Furt fabrikuje fajnové fikcie, prečo nemusí programovať.

Fiškus fyzicky formuje farebnú reťaz z domín. Frfle, keď táto reťaz nie je fakt fest dlhá.

Si frajer, chceš na Fezja flexiť natoľko, že bude ten fidlikár fňukať?

Tak poflirtuj s nápadom, že postavíš dlhšiu reťaz ako on.

Úloha

Dominá pozostávajú zo štvorčekov dvoch farieb - bielej (B) a čiernej (C). Dve dominá vieme položiť vedľa seba v reťazi, ak sú ich dotýkajúce štvorčeky rovnakej farby.

Teda z domín BBCB, CC a BCB vieme postaviť reťaz BCB|BBCB, dĺžky 7 štvorčekov.

Dominá nesmieme otáčať pri ukladaní do reťaze. Domino BC teda nemôžeme otočiť a použiť ako CB.

Na vstupe dostanete popis domín, ktoré má Fezjo k dispozícií. Zistite, akú dlhú reťaz dokáže postaviť.

Vstup a výstup

V prvom riadku vstupu je číslo \(n\) – počet domín.

Každy z nasledujúcich \(n\) riadkov obsahuje popis jedného domina – reťazec z písmen C a B.

Vypíšte dĺžku (počet znakov) najdlhšej reťaze, ktorá sa z nich dá vytvoriť.

Dominá sú dlhé aspoň \(1\) a najviac \(100\) znakov.

\(n\) je postupne \(10\), \(20\), \(1\,000\).

Príklady

Input:

3
BBCB
CC
BCB

Output:

7

Input:

4
CB
BBCC
BCC
BCBBC

Output:

11