Optimal ability loadout

Gyeonggeun plays a web game where he fights monsters, and he has collected $N$ attack abilities. To keep track of them he numbered the abilities 1 through $N$.

Ability $i$ has a trigger probability $p_i$ and a damage value $d_i$. When Gyeonggeun issues a trigger command to ability $i$, the ability triggers with probability $p_i$ and deals $d_i$ damage to the opponent, and with probability $1 - p_i$ nothing happens.

Gyeonggeun can now equip and unequip abilities freely. Whenever he gets one attack, the equipped abilities go through this process.

• Pick one of the equipped abilities that has not received a trigger command yet, each with the same probability.
• Issue a trigger command to the picked ability. If the ability triggers, the opponent takes that ability's damage and the attack ends.
• If the ability does not trigger, repeat the same step with the abilities that are left. If every equipped ability has received a trigger command and none of them triggered, the attack ends without damage.

Given the trigger probability and the damage of the $N$ abilities, find the expected damage of one attack when the abilities are equipped so that this expected damage is as large as possible.

The first line has an integer $N$ ($1 \le N \le 20$). The $i$-th of the next $N$ lines has two integers $p_i$ and $d_i$ ($1 \le p_i, d_i \le 100$), separated by a space. Ability $i$ triggers with probability $p_i$ percent, that is $p_i / 100$, and deals $d_i$ damage to the opponent.

Print on one line the maximum expected damage over all ways of equipping the abilities, rounded to six digits after the decimal point. Print all six digits even when the value is an integer.

Equipping more abilities is not always better. An ability that always triggers but deals little damage ends the attack the moment it is picked, which lowers the expected damage.