시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 26 11 11 44.000%

문제

한 범죄 조직에서의 오랜 기간에 걸친 첩보 활동 끝에, 당신은 이제 그 조직을 와해시킬 시도를 해보려 한다. 하지만 당신 혼자서는 이 일을 성공적으로 끝낼 수 없다. 그래서 당신은 조직원 몇 명을 매수해 일을 진행하려 하지만, 당신에게 주어진 예산은 한정되어 있다.

다행히도 당신은 사람을 파악하는 데 천부적인 재능이 있다. 그래서 어떤 조직원이 조직을 배반할 생각이 있다면, 당신은 그에게 어느 정도의 돈을 줘야 할 지를 이미 알고 있다. 게다가, 당신은 그들이 성공적으로 변절하여 완벽히 당신의 편이 될 확률까지도 알고 있다. 특별히 다른 방법이 존재하지 않기에 당신은 이제부터 실제로 조직원들에게 직접 접근하여 매수를 시도하려 한다. 만일 어떤 조직원이 돈을 받고도 매수되지 않았다면 당신은 다시는 그 조직원을 매수하려 시도할 수 없다.

각 조직원들에 대한 정보, 즉 그들이 요구할 돈과 변절할 확률이 주어지고, 당신이 필요한 최소한의 변절자 수가 주어질 때, 과연 이번 계획이 어느 정도의 확률로 성공할 지 계산할 수 있을까?

입력

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

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

  • 공백으로 구분된 세 개의 정수 n, c, m (1 ≤ n, c ≤ 16 and 1 ≤ m ≤ 1000) : 접선할 수 있는 조직원의 수, 당신이 필요로 하는 최소한의 조직원 수, 예산
  • n줄에 걸쳐 두 개의 정수 b, p (0 ≤ b ≤ 1 000 , 0 ≤ p ≤ 100) : 매수를 시도하는 데 필요한 금액, 그 조직원이 성공적으로 당신의 편이 될 확률( % 값 )

출력

각 테스트 케이스에 대해 다음을 출력한다.

  • 당신이 가장 이상적으로 계획을 진행했을 때, c명의 조직원을 매수하는 데 성공할 확률. 오차는 소수점 7째 자리부터 허용한다.

예제 입력

2
4 3 1000
300 40
300 50
300 60
300 70
4 2 1000
100 80
700 50
400 20
500 20

예제 출력

0.21
0.408

힌트