Alice and Bob play the following 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.
The input consists of a single test case, formatted as follows.
n p1 . . . pn
A positive integer n (≤ 40) is the number of candidate piles. Each pi 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 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.
4 B W WB WB
6 B W WB WB BWW BWW