최적의 능력 구성

경근이는 몬스터와 싸우는 웹게임에서 공격 능력 $N$개를 모았다. 관리하기 편하도록 각 능력에 1 이상 $N$ 이하의 번호를 붙였다.

$i$번 능력에는 발동 확률 $p_i$와 피해량 $d_i$가 정해져 있다. $i$번 능력에 발동 명령을 내리면 $p_i$의 확률로 능력이 발동해 상대에게 $d_i$만큼의 피해를 입히고, $1 - p_i$의 확률로 아무 일도 일어나지 않는다.

이제 경근이는 능력을 자유롭게 장착하고 해제한다. 공격 기회를 한 번 얻으면 장착한 능력으로 다음 과정이 진행된다.

• 아직 발동 명령을 내리지 않은 능력 중 하나를 같은 확률로 고른다.
• 고른 능력에 발동 명령을 내린다. 능력이 발동하면 상대가 그 능력의 피해량만큼 피해를 입고 공격 기회가 끝난다.
• 능력이 발동하지 않으면 남은 능력을 대상으로 같은 과정을 반복한다. 장착한 능력에 모두 발동 명령을 내렸는데도 발동한 능력이 하나도 없으면 피해 없이 공격 기회가 끝난다.

능력 $N$개의 발동 확률과 피해량이 주어질 때, 한 번의 공격 기회에서 상대가 입는 피해량의 기댓값이 최대가 되도록 능력을 장착했을 때 그 기댓값을 구하라.

첫째 줄에 자연수 $N$ ($1 \le N \le 20$)이 주어진다. 이어지는 $N$개의 줄 중 $i$번째 줄에는 두 정수 $p_i$, $d_i$ ($1 \le p_i, d_i \le 100$)가 공백을 사이에 두고 주어진다. $i$번 능력은 $p_i$%, 즉 $p_i / 100$의 확률로 발동하고 상대에게 $d_i$만큼의 피해를 입힌다.

능력을 가장 유리하게 장착했을 때 얻는 피해량의 기댓값의 최댓값을 소수점 아래 여섯째 자리까지 반올림해 한 줄에 출력한다. 값이 정수여도 소수점 아래 여섯 자리를 모두 적는다.

능력을 많이 장착한다고 항상 유리하지는 않다. 반드시 발동하지만 피해량이 작은 능력을 함께 장착하면 그 능력이 먼저 뽑히는 순간 공격 기회가 끝나서 기댓값이 오히려 낮아진다.