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 |
