cho.sh

Black and White Boxes

Given up to 40 piles of black and white boxes, pick a subset so the first-player draw decides the winner and maximize total boxes.

Hard8Game theoryDynamic programmingBit manipulationNo attempts yetTime limit2sMemory limit512 MB

Problem

Alice and Bob play the following game.

  1. Several straight piles of boxes stand on a table. All boxes have the same size, and each one is painted black or white.
  2. Alice and Bob move alternately. A fair random draw decides who moves first.
  3. On her turn Alice picks a black box in one of the piles and removes that box together with every box above it. If no black box is left anywhere, she loses.
  4. On his turn Bob picks a white box in one of the piles and removes that box together with every box above it. If no white box is left anywhere, he loses.

Once the starting piles and the first player are fixed, the game has perfect information and no chance element. In such a game one of the two players wins by playing best. The draw for the first move therefore decides the winner.

Well known games such as chess share this property. Chess is complicated enough that even a supercomputer cannot analyze it completely, which leaves people room to enjoy playing it.

This box game is not that complicated, and best play is easier to find. A starting configuration should therefore be fair, meaning both players keep a chance to win. Call a configuration fair when the player who wins under best play depends on the draw. A configuration in which one player wins no matter who moves first is not wanted.

You are given a set of candidate piles. Choose some of them as the starting configuration (choosing none is allowed) so that the configuration is fair. Among all fair choices, report the largest total number of boxes.

Input

The input is a single test case in the following format.

n
p1
.
.
.
pn

nn is the number of candidate piles, an integer with 1≤n≤401 \le n \le 40. Each pip_i is a string over the characters B and W describing the ii-th candidate pile. B is a black box and W is a white box, listed from the bottom of the pile to the top. A candidate pile holds at most 40 boxes.

Output

Print in one line the largest total number of boxes in a fair starting configuration made of some of the candidate piles. If the empty configuration is the only fair one, print 0.