검은 상자와 흰 상자

앨리스와 밥이 다음 게임을 한다.

1. 탁자 위에 상자를 곧게 쌓은 더미가 여러 개 있다. 상자는 크기가 모두 같고 검은색이나 흰색으로 칠해져 있다.
2. 앨리스와 밥이 번갈아 한 번씩 둔다. 누가 먼저 두는지는 공정한 추첨으로 정한다.
3. 앨리스는 자기 차례에 어느 한 더미에서 검은 상자를 하나 고르고, 그 상자와 그 위에 놓인 상자를 모두 치운다. 치울 검은 상자가 하나도 남아 있지 않으면 앨리스가 진다.
4. 밥은 자기 차례에 어느 한 더미에서 흰 상자를 하나 고르고, 그 상자와 그 위에 놓인 상자를 모두 치운다. 치울 흰 상자가 하나도 남아 있지 않으면 밥이 진다.

처음 더미 구성과 선공이 정해지면 이 게임은 우연이 없는 완전 정보 게임이 된다. 이런 게임에서는 두 사람 중 한 명이 최선을 다하면 반드시 이긴다. 결국 선공을 뽑는 추첨이 승자를 정하는 셈이다.

체스처럼 널리 알려진 게임도 같은 성질이 있다. 다만 체스는 슈퍼컴퓨터로도 완전히 분석하지 못할 만큼 복잡해서, 사람이 즐길 여지가 남아 있다.

이 상자 게임은 그만큼 복잡하지 않아 최선의 수를 찾기가 쉽다. 그래서 처음 구성은 공정해야 한다. 즉 두 사람 모두에게 이길 기회가 남아 있어야 한다. 양쪽이 최선을 다했을 때 이기는 사람이 선공 추첨에 따라 달라지는 구성을 공정하다고 하자. 누가 먼저 두든 한 사람이 항상 이기는 구성은 쓰지 않는다.

후보 더미가 주어진다. 이 중 일부를 골라 처음 구성으로 삼되(하나도 고르지 않아도 된다), 그 구성이 공정해야 한다. 공정한 모든 선택 가운데 상자 개수의 합이 가장 큰 값을 구하여라.

입력은 테스트 케이스 하나로 이루어지며, 형식은 다음과 같다.

n
p1
.
.
.
pn

$n$은 후보 더미의 개수이고 $1 \le n \le 40$인 정수다. 각 $p_i$는 $i$번째 후보 더미를 나타내는 문자열로 문자 B와 W로만 이루어진다. B는 검은 상자, W는 흰 상자를 뜻하며, 더미의 맨 아래부터 맨 위 순서로 적혀 있다. 후보 더미 하나에 들어 있는 상자는 40개를 넘지 않는다.

후보 더미 중 일부로 만든 공정한 처음 구성이 가질 수 있는 상자 개수의 최댓값을 한 줄에 출력한다. 공정한 구성이 빈 구성뿐이면 0을 출력한다.