# Problem C

Esthetic Fences

You are given $n$ fence parts, each colored either blue or red. Each fence part has a length and a color. We need to build a triangular fence using some or all of these parts. For esthetic reasons, adjacent parts of this triangular fence have to have different colors. What is the largest product of side lengths that can be achieved, where the colors of the fence parts alternate between red and blue around the entire triangle? Degenerate triangles are not allowed. That is, the triangle must fence off a strictly positive area.

## Input

The first line of input contains a single integer,
$n$, the number of fence
parts, where $3\leq n\leq
20$. This is followed by $n$ lines consisting of an integer
length, $\ell $, for the
fence part and either `r` or `b` indicating that the fence part is red or
blue, respectively. Each fence part length satisfies
$1\leq \ell \leq 30$. The
sum of the lengths of all fence parts is at most $30$.

## Output

Output a single integer, the largest product of the lengths of the three sides of a triangular fence whose parts alternate in color between red and blue. If no such triangular fence can be constructed, then output $0$.

Sample Input 1 | Sample Output 1 |
---|---|

6 3 r 3 r 1 r 1 b 2 r 5 b |
60 |

Sample Input 2 | Sample Output 2 |
---|---|

4 1 r 1 b 1 r 1 b |
0 |