최적의 능력 구성 Batch 컴파일 명령

경근이는 요즘 여러 능력을 가지고 몬스터들과 싸우는 웹게임을 열심히 하고 있다. 경근이는 지금 N개의 공격 능력을 가지고 있다. 경근이는 능력들을 편하게 관리하고자 각 능력에 1 이상 N 이하의 자연수 번호를 붙였다.

i번 능력에는 그 능력이 발동될 확률 p_i와 상대에게 입히는 피해량 d_i가 책정되어 있다. 따라서 경근이가 i번 능력에 발동 명령을 내리면, p_i의 확률로 능력이 발동되어 상대에게 d_i만큼의 피해를 입히고, (1 - p_i)의 확률로 능력이 발동되지 않아 아무 일도 일어나지 않는다.

열심히 게임을 한 결과, 경근이는 드디어 게임 내에서 모든 능력을 자유롭게 장착하고 해제할 수 있게 되었다! 이제 경근이는 상대가 입을 피해량의 기댓값이 최대가 되도록 하기 위해 어떤 능력들을 장착해야 할지를 알고 싶다. 경근이가 어떤 능력(들)을 장착한 채로 상대방을 공격할 기회를 얻었다면, 아래 과정이 일어난다:

• 하나의 능력만 장착했을 때: 해당 능력에 발동 명령을 내린 후, 그 결과와 상관 없이 공격 기회를 잃는다.
• 두 개 이상의 능력을 장착했을 때: 가지고 있는 모든 능력들 중 하나를 임의로 고른다. 모든 능력을 고를 확률은 서로 같다. 고른 능력에 발동 명령을 내린다. 만약 이 능력이 발동되었다면, 공격 기회를 잃고 과정이 끝난다. 하지만 이 능력이 발동되지 않았다면, 아직 발동 명령을 내려 보지 않은 능력들 중 하나를 동일한 확률로 무작위하게 고른 후, 다시 발동 명령을 내린다. 만약 능력이 발동되었다면 공격 기회를 잃은 후 과정을 끝내고, 발동되지 않았다면 같은 과정을 더 이상 발동 명령을 내려 보지 않은 능력이 없을 때까지 반복한다. 모든 능력에 발동 명령을 내렸음에도 발동된 능력이 하나도 없으면 공격 기회를 잃는다.

현재 경근이가 가지고 있는 N개의 능력이 발동될 확률과 상대에게 입히는 피해량이 주어질 때, 한 번의 공격 기회에서 피해량의 기댓값이 최대가 되도록 하기 위해 장착해야 할 능력의 집합을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 자연수 N (1 ≤ N ≤ 20)이 주어진다. 다음 N개의 줄에는 능력들의 정보가 주어진다. 이 중 i (1 ≤ i ≤ N)번째 줄에는 i번 능력이 발동될 확률과 상대에게 입히는 피해량을 의미하는 두 정수 p_i, d_i (1 ≤ p_i , d_i ≤ 100)이 공백을 사이로 두고 주어진다. 이는 i번 능력은 p_i% ( = p_i / 100)의 확률로 발동하는 능력이며 상대에게 d_i만큼의 피해를 입힌다는 의미이다.

출력

가지고 있는 능력들을 적절히 장착하여 얻을 수 있는 피해량의 기댓값의 최댓값을 출력한다. 정답과의 절대/상대 오차가 10^- 8 이하이면 올바른 답안으로 처리된다.

부분문제

입출력 예제

첫 번째 예제의 경우 1번 능력은 100% 발동하지만 피해량이 너무 낮아 이를 사용하지 않고 2번 능력만 사용하는 것이 피해량의 기댓값이 더 높다.