All Survived?

You are playing a first-person shooter with your friends. In this game, $n$ players are divided into two teams that fight each other. Each player wears a balloon on top of the head, and players try to pop the balloons of the players on the opposing team.

Players are numbered from 1 through $n$. These numbers are called the action orders. Each player also has a real number called the hit probability. The game consists of $n$ phases. In the $i$-th phase ($i = 1, \dots, n$), the player with action order $i$ (the attacker) takes the following action.

• If the attacker's balloon has already been popped, the attacker is dead and the phase is skipped without any action.
• If all opposing team members are dead, the phase is skipped as well.
• Otherwise, the attacker chooses one living opposing player as the target. The choice may depend on the results of previous actions. The attack succeeds with the attacker's hit probability, regardless of the target. If the attack succeeds, the target's balloon is popped and the target is killed.

The game ends when all phases are completed.

You do not want any player on your team to be killed. Choose targets optimally and calculate the probability that all players on your team stay alive until the game ends. Assume that the opposing players choose their targets at random.

The input consists of multiple datasets. The number of datasets does not exceed 50. Each dataset has the following format.

$n$ $s_1$ $p_1$ $\vdots$ $s_n$ $p_n$

$n$ is the number of players, an integer from 2 to 300. For each $i = 1, \dots, n$, $s_i$ is either "Ally" or "Enemy", meaning the player with action order $i$ is on your team or the opposing team. $p_i$ is the hit probability, a real number from 0 to 1 with 9 digits after the decimal point. Both teams have at least one player.

The input ends with a line containing 0.

For each dataset, print one line containing the probability that all players on your team stay alive when targets are chosen optimally. The absolute or relative error must be at most $10^{-9}$.