비밀번호 뚫기

비밀번호는 추측하기 어려운 것을 골라 쓰지 않으면 그다지 안전하지 않다. 그런데 대부분의 사용자는 그만큼 조심하지 않고 "123456" 같은 비밀번호를 마음 편히 쓴다. 실제로 자주 쓰이는 비밀번호를 모아 둔 목록이 돌아다니고, 공격자는 그 목록으로 시스템에 침입한다. 그리고 그 방법은 꽤 자주 통한다.

당신은 이런 목록으로 해킹을 많이 해 봐서 목록에 있는 비밀번호 하나하나가 정답일 확률을 잘 알고 있다. "123456"을 비밀번호로 쓰는 사람이 그렇게 많다는 점에는 매번 놀란다. 이번에 새로 뚫을 계정이 생겼고, 목록에 있는 비밀번호를 한 번에 하나씩 입력해서 정답을 찾을 때까지 시도하기로 했다. 뚫으려는 계정이 주어진 목록 안의 비밀번호를 쓴다는 것은 확실하다.

시도 순서를 가장 좋게 잡았을 때, 정답을 찾기까지 시도하는 횟수의 기댓값을 구하라.

첫째 줄에 목록에 들어 있는 비밀번호의 개수인 양의 정수 $N$이 주어진다. 다음 $N$개 줄에는 비밀번호, 공백 하나, 그 비밀번호가 정답일 확률이 차례로 주어진다.

비밀번호는 알파벳 대소문자와 숫자로만 이루어진 문자열이고, 길이는 $1$ 이상 $12$ 이하이다. 확률은 소수점 아래 넷째 자리까지 주어지는 실수이다. $N$은 $500$ 이하이고, 모든 확률의 합은 $1$이다. 목록에 같은 비밀번호가 두 번 나오지는 않는다.

가장 좋은 순서로 시도했을 때 정답을 찾기까지 시도하는 횟수의 기댓값을 한 줄에 출력한다.

모든 확률이 소수점 아래 넷째 자리까지 주어지므로 기댓값도 소수점 아래 넷째 자리로 딱 떨어진다. 반올림하거나 자리를 줄이지 말고, 소수점 아래 넷째 자리까지 그대로 출력한다. 답이 $1$이면 1.0000을 출력한다.