조직원 매수

한 범죄 조직에 오래 잠입해 첩보 활동을 벌인 끝에, 이제 그 조직을 무너뜨릴 때가 왔다. 그러나 혼자 힘으로는 이 일을 끝내지 못한다. 그래서 조직원 몇 명을 매수해 계획을 진행하려 하는데, 쓸 수 있는 예산이 정해져 있다.

다행히 당신은 사람을 알아보는 재능을 타고났다. 조직을 배반할 마음이 있는 조직원이라면 매수하는 데 돈이 얼마나 드는지 이미 알고, 그가 실제로 변절해 완전히 당신 편이 될 확률까지 안다. 달리 방법이 없으니 이제 조직원에게 직접 접근해 매수를 시도한다.

접근한 조직원에게 건넨 돈은 매수 성공 여부와 상관없이 예산에서 빠져나간다. 돈만 받고 변절하지 않은 조직원은 두 번 다시 매수하려 시도할 수 없다. 접근은 한 번에 한 명씩 하며, 앞선 시도의 결과를 보고 다음에 누구에게 접근할지 정할 수 있다. 남은 예산으로 값을 치를 수 없는 조직원에게는 접근하지 못한다.

조직원마다 요구하는 금액과 변절할 확률이 주어지고 필요한 변절자의 최소 인원이 주어질 때, 가장 좋은 전략을 따랐을 때 계획이 성공할 확률을 구하라.

첫 줄에 테스트 케이스의 수가 주어진다. 이 수는 100을 넘지 않는다.

각 테스트 케이스는 다음과 같이 구성된다.

• 공백으로 구분된 세 정수 $n$, $c$, $m$ ($1 \le n, c \le 16$, $1 \le m \le 1000$)이 한 줄에 주어진다. 차례대로 접근할 수 있는 조직원의 수, 필요한 변절자의 최소 인원, 예산이다.
• 이어지는 $n$개 줄에 두 정수 $b$, $p$ ($0 \le b \le 1000$, $0 \le p \le 100$)가 주어진다. $b$는 그 조직원에게 매수를 시도하는 데 필요한 금액이고, $p$는 그 조직원이 성공적으로 당신 편이 될 확률을 백분율로 나타낸 값이다.

각 테스트 케이스마다 한 줄에, 가장 좋은 전략을 따랐을 때 변절자를 $c$명 이상 확보할 확률을 출력한다. 소수점 아래 일곱째 자리에서 반올림해 소수점 아래 여섯 자리까지 적고, 끝자리가 0이어도 여섯 자리를 모두 채운다. 모든 입력의 정답은 반올림 경계에서 충분히 떨어져 있어 배정밀도 실수 연산으로 계산해도 같은 여섯 자리가 나온다.