Problem K Black and White Boxes

Alice and Bob play the following game.

1. There are a number of straight piles of boxes. The boxes have the same size and are painted either black or white.
2. Two players, namely Alice and Bob, take their turns alternately. Who to play first is decided by a fair random draw.
3. In Alice's turn, she selects a black box in one of the piles, and removes the box together with all the boxes above it, if any. If no black box to remove is left, she loses the game.
4. In Bob's turn, he selects a white box in one of the piles, and removes the box together with all the boxes above it, if any. If no white box to remove is left, he loses the game.

Given an initial configuration of piles and who plays first, the game is a definite perfect information game. In such a game, one of the players has sure win provided he or she plays best. The draw for the first player, thus, essentially decides the winner.

In fact, this seemingly boring property is common with many popular games, such as chess. The chess game, however, is complicated enough to prevent thorough analyses, even by supercomputers, which leaves us rooms to enjoy playing.

This game of box piles, however, is not as complicated. The best plays may be more easily found. Thus, initial configurations should be fair, that is, giving both players chances to win. A configuration in which one player can always win, regardless of who plays first, is undesirable.

You are asked to arrange an initial configuration for this game by picking a number of piles from the given candidate set. As more complicated configuration makes the game more enjoyable, you are expected to find the configuration with the maximum number of boxes among fair ones.

Input

The input consists of a single test case, formatted as follows.

$n$
$p_1$
.
.
.
$p_n$

A positive integer $n$ ($\leq 40$) is the number of candidate piles. Each $p_i$ is a string of characters B and W, representing the $i$-th candidate pile. B and W mean black and white boxes, respectively. They appear in the order in the pile, from bottom to top. The number of boxes in a candidate pile does not exceed 40.

Output

Output in a line the maximum possible number of boxes in a fair initial configuration consisting of some of the candidate piles. If only the empty configuration is fair, output a zero.

Sample Input 1

4
B
W
WB
WB

Sample Output 1

5

Sample Input 2

6
B
W
WB
WB
BWW
BWW

Sample Output 2

10

---