시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 39 19 19 50.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째 자리부터 허용한다.

예제 입력 1

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

예제 출력 1

0.21
0.408
W3sicHJvYmxlbV9pZCI6IjkzNjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5ZTRcdWMyMTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDU1YyBcdWJjOTRcdWM4YzQgXHVjODcwXHVjOWMxXHVjNWQwXHVjMTFjXHVjNzU4IFx1YzYyNFx1Yjc5YyBcdWFlMzBcdWFjMDRcdWM1ZDAgXHVhYzc4XHVjZTVjIFx1Y2NhOVx1YmNmNCBcdWQ2NWNcdWIzZDkgXHViMDVkXHVjNWQwLCBcdWIyZjlcdWMyZTBcdWM3NDAgXHVjNzc0XHVjODFjIFx1YWRmOCBcdWM4NzBcdWM5YzFcdWM3NDQgXHVjNjQwXHVkNTc0XHVjMmRjXHVkMGFjIFx1YzJkY1x1YjNjNFx1Yjk3YyBcdWQ1NzRcdWJjZjRcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHViMmY5XHVjMmUwIFx1ZDYzY1x1Yzc5MFx1YzExY1x1YjI5NCBcdWM3NzQgXHVjNzdjXHVjNzQ0IFx1YzEzMVx1YWNmNVx1YzgwMVx1YzczY1x1Yjg1YyBcdWIwNWRcdWIwYmMgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YjJmOVx1YzJlMFx1Yzc0MCBcdWM4NzBcdWM5YzFcdWM2ZDAgXHViYTg3IFx1YmE4NVx1Yzc0NCBcdWI5ZTRcdWMyMThcdWQ1NzQgXHVjNzdjXHVjNzQ0IFx1YzljNFx1ZDU4OVx1ZDU1OFx1YjgyNCBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YjJmOVx1YzJlMFx1YzVkMFx1YWM4YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjNjA4XHVjMGIwXHVjNzQwIFx1ZDU1Y1x1YzgxNVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1ZDU4OVx1ZDc4OFx1YjNjNCBcdWIyZjlcdWMyZTBcdWM3NDAgXHVjMGFjXHViNzhjXHVjNzQ0IFx1ZDMwY1x1YzU0NVx1ZDU1OFx1YjI5NCBcdWIzNzAgXHVjYzljXHViZDgwXHVjODAxXHVjNzc4IFx1YzdhY1x1YjJhNVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYyBcdWM1YjRcdWI1YTQgXHVjODcwXHVjOWMxXHVjNmQwXHVjNzc0IFx1Yzg3MFx1YzljMVx1Yzc0NCBcdWJjMzBcdWJjMThcdWQ1NjAgXHVjMGRkXHVhYzAxXHVjNzc0IFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHViMmY5XHVjMmUwXHVjNzQwIFx1YWRmOFx1YzVkMFx1YWM4YyBcdWM1YjRcdWIyOTAgXHVjODE1XHViM2M0XHVjNzU4IFx1YjNjOFx1Yzc0NCBcdWM5MThcdWM1N2MgXHVkNTYwIFx1YzljMFx1Yjk3YyBcdWM3NzRcdWJiZjggXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhYzhjXHViMmU0XHVhYzAwLCBcdWIyZjlcdWMyZTBcdWM3NDAgXHVhZGY4XHViNGU0XHVjNzc0IFx1YzEzMVx1YWNmNVx1YzgwMVx1YzczY1x1Yjg1YyBcdWJjYzBcdWM4MDhcdWQ1NThcdWM1ZWMgXHVjNjQ0XHViY2JkXHVkNzg4IFx1YjJmOVx1YzJlMFx1Yzc1OCBcdWQzYjhcdWM3NzQgXHViNDIwIFx1ZDY1NVx1Yjk2MFx1YWU0Y1x1YzljMFx1YjNjNCBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWQyYjlcdWJjYzRcdWQ3ODggXHViMmU0XHViOTc4IFx1YmMyOVx1YmM5NVx1Yzc3NCZuYnNwO1x1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWFlMzBcdWM1ZDAgXHViMmY5XHVjMmUwXHVjNzQwIFx1Yzc3NFx1YzgxY1x1YmQ4MFx1ZDEzMCBcdWMyZTRcdWM4MWNcdWI4NWMgXHVjODcwXHVjOWMxXHVjNmQwXHViNGU0XHVjNWQwXHVhYzhjIFx1YzljMVx1YzgxMSBcdWM4MTFcdWFkZmNcdWQ1NThcdWM1ZWMgXHViOWU0XHVjMjE4XHViOTdjIFx1YzJkY1x1YjNjNFx1ZDU1OFx1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1YjljY1x1Yzc3YyBcdWM1YjRcdWI1YTQgXHVjODcwXHVjOWMxXHVjNmQwXHVjNzc0IFx1YjNjOFx1Yzc0NCBcdWJjMWJcdWFjZTBcdWIzYzQgXHViOWU0XHVjMjE4XHViNDE4XHVjOWMwIFx1YzU0YVx1YzU1OFx1YjJlNFx1YmE3NCBcdWIyZjlcdWMyZTBcdWM3NDAgXHViMmU0XHVjMmRjXHViMjk0IFx1YWRmOCBcdWM4NzBcdWM5YzFcdWM2ZDBcdWM3NDQgXHViOWU0XHVjMjE4XHVkNTU4XHViODI0IFx1YzJkY1x1YjNjNFx1ZDU2MCZuYnNwO1x1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWM4NzBcdWM5YzFcdWM2ZDBcdWI0ZTRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNCwgXHVjOTg5IFx1YWRmOFx1YjRlNFx1Yzc3NCBcdWM2OTRcdWFkNmNcdWQ1NjAgXHViM2M4XHVhY2ZjIFx1YmNjMFx1YzgwOFx1ZDU2MCBcdWQ2NTVcdWI5NjBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBcdWIyZjlcdWMyZTBcdWM3NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWJjYzBcdWM4MDhcdWM3OTAgXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsIFx1YWNmY1x1YzVmMCBcdWM3NzRcdWJjODggXHVhY2M0XHVkNjhkXHVjNzc0IFx1YzViNFx1YjI5MCBcdWM4MTVcdWIzYzRcdWM3NTggXHVkNjU1XHViOTYwXHViODVjIFx1YzEzMVx1YWNmNVx1ZDU2MCBcdWM5YzAgXHVhY2M0XHVjMGIwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3NDRcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkNCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWMyMThcdWIyOTQgMTAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MWMgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggbiwgYywgbSAoMSAmbGU7IG4sIGMgJmxlOyAxNiBhbmQgMSAmbGU7IG0gJmxlOyAxMDAwKSA6IFx1YzgxMVx1YzEyMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Yzg3MFx1YzljMVx1YzZkMFx1Yzc1OCBcdWMyMTgsIFx1YjJmOVx1YzJlMFx1Yzc3NCBcdWQ1NDRcdWM2OTRcdWI4NWMgXHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWM4NzBcdWM5YzFcdWM2ZDAgXHVjMjE4LCBcdWM2MDhcdWMwYjA8XC9saT5cclxuXHQ8bGk+blx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggYiwgcCAoMCAmbGU7IGIgJmxlOyAxIDAwMCAsJm5ic3A7MCAmbGU7IHAgJmxlOyAxMDApIDogXHViOWU0XHVjMjE4XHViOTdjIFx1YzJkY1x1YjNjNFx1ZDU1OFx1YjI5NCBcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YWUwOFx1YzU2MSwgXHVhZGY4IFx1Yzg3MFx1YzljMVx1YzZkMFx1Yzc3NCBcdWMxMzFcdWFjZjVcdWM4MDFcdWM3M2NcdWI4NWMgXHViMmY5XHVjMmUwXHVjNzU4IFx1ZDNiOFx1Yzc3NCBcdWI0MjAgXHVkNjU1XHViOTYwKCAlIFx1YWMxMiZuYnNwOyk8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWIyZTRcdWM3NGNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YjJmOVx1YzJlMFx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjNzc0XHVjMGMxXHVjODAxXHVjNzNjXHViODVjIFx1YWNjNFx1ZDY4ZFx1Yzc0NCBcdWM5YzRcdWQ1ODlcdWQ1ODhcdWM3NDQgXHViNTRjLCZuYnNwO2NcdWJhODVcdWM3NTggXHVjODcwXHVjOWMxXHVjNmQwXHVjNzQ0IFx1YjllNFx1YzIxOFx1ZDU1OFx1YjI5NCBcdWIzNzAgXHVjMTMxXHVhY2Y1XHVkNTYwIFx1ZDY1NVx1Yjk2MC4gXHVjNjI0XHVjYzI4XHViMjk0IFx1YzE4Y1x1YzIxOFx1YzgxMCA3XHVjOWY4IFx1Yzc5MFx1YjlhY1x1YmQ4MFx1ZDEzMCBcdWQ1YzhcdWM2YTlcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5MzY4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQnJpYmUiLCJkZXNjcmlwdGlvbiI6IjxwPkFmdGVyIGhhdmluZyBkb25lIGEgbG90IG9mIHNweWluZyBhbmQgaW5cdWZiMDFsdHJhdGluZyBhIGNyaW1pbmFsIG5ldHdvcmssIHlvdSBhcmUgbm93IHJlYWR5IHRvIHRyeSBhbmQgZGlzbWFudGxlIGl0LiBUaGlzLCBob3dldmVyLCByZXF1aXJlcyB0aGUgY29vcGVyYXRpb24gb2YgYSBjZXJ0YWluIG51bWJlciBvZiB0aGUgaGVuY2htZW4uIFRoaXMgaW4gdHVybiByZXF1aXJlcyBtb25leSBpbiBvcmRlciB0byBicmliZSB0aGVtLCBidXQgZHVlIHRvIGJ1ZGdldCBjdXRzLCB5b3Ugb25seSBoYXZlIGEgbGltaXRlZCBhbW91bnQgb2YgbW9uZXkuPFwvcD5cclxuXHJcbjxwPkZvcnR1bmF0ZWx5LCB5b3UgYXJlIGFuIGV4Y2VsbGVudCBqdWRnZSBvZiBjaGFyYWN0ZXIsIHNvIGZvciBlYWNoIG9mIHRoZSBoZW5jaG1lbiB5b3UgYXJlIGNvbnNpZGVyaW5nIHRvIGJyaWJlLCB5b3Uga25vdyB3aGF0IGFtb3VudCBvZiBtb25leSB0aGV5IHdpbGwgYXNrIGZvci4gRnVydGhlcm1vcmUsIHlvdSBrbm93IHRoZSBwcm9iYWJpbGl0eSB0aGF0IHRoZXkgd2lsbCB0aGVuIHN1Y2Nlc3NmdWxseSBjb252ZXJ0LCBhcyBvcHBvc2VkIHRvIHRha2luZyB0aGUgbW9uZXkgYW5kIG1ha2luZyBhIHJ1biBmb3IgaXQuIFRoZXJlIGlzIG5vIHBhcnRpY3VsYXIgcnVzaCwgc28gYWZ0ZXIgZWFjaCBhdHRlbXB0ZWQgY29udmVyc2lvbiB5b3UgY2FuIGVzdGFibGlzaCB3aGV0aGVyIGl0IHdhcyBzdWNjZXNzZnVsIG9yIG5vdCwgYmVmb3JlIHlvdSBtb3ZlIG9uIHRvIHNvbWVvbmUgZWxzZS4gT2YgY291cnNlLCBpZiBpdCB3YXMgbm90IHN1Y2Nlc3NmdWwsIHRoZW4geW91IGNhbm5vdCB0cnkgdG8gYnJpYmUgdGhpcyBoZW5jaG1hbiBhIHNlY29uZCB0aW1lLjxcL3A+XHJcblxyXG48cD5HaXZlbiBhbGwgdGhpcyBpbmZvcm1hdGlvbiBvbiB0aGUgaGVuY2htZW4sIHRoZSBhbW91bnQgb2YgbW9uZXkgdGhhdCB5b3UgaGF2ZSBhdCB5b3VyIGRpc3Bvc2FsLCBhbmQgdGhlIG51bWJlciBvZiBoZW5jaG1lbiB5b3UgbmVlZCB0byBjb252ZXJ0LCBjYW4geW91IHdvcmsgb3V0IHRoZSBwcm9iYWJpbGl0eSB0aGF0IHRoaXMgb3BlcmF0aW9uIHdpbGwgYmUgYSBzdWNjZXNzPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBuLCBjIGFuZCBtICgxICZsZTsgbiwgYyAmbGU7IDE2IGFuZCAxICZsZTsgbSAmbGU7IDEgMDAwKTogdGhlIG51bWJlciBvZiBoZW5jaG1lbiB0aGF0IGFyZSBzdXNjZXB0aWJsZSB0byBicmliZSwgdGhlIG51bWJlciB5b3UgbmVlZCB0byBjb252ZXJ0LCBhbmQgdGhlIGFtb3VudCBvZiBtb25leSB0aGF0IHlvdSBoYXZlLCByZXNwZWN0aXZlbHkuPFwvbGk+XHJcblx0PGxpPm4gbGluZXMgd2l0aCB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIGIgYW5kIHAgKDAgJmxlOyBiICZsZTsgMSAwMDAgYW5kIDAgJmxlOyBwICZsZTsgMTAwKTogdGhlIGFtb3VudCBvZiBtb25leSB5b3UgbmVlZCB0byBicmliZSBlYWNoIGhlbmNobWFuLCBhbmQgdGhlIHByb2JhYmlsaXR5IChhcyBhIHBlcmNlbnRhZ2UpIHRoYXQgaGUgd2lsbCBiZSBzdWNjZXNzZnVsbHkgY29udmVydGVkLCByZXNwZWN0aXZlbHk8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhIHNpbmdsZSBcdWZiMDJvYXRpbmcgcG9pbnQgbnVtYmVyOiB0aGUgcHJvYmFiaWxpdHkgdGhhdCB5b3Ugd2lsbCBzdWNjZWVkIGluIGNvbnZlcnRpbmcgYyBoZW5jaG1lbiwgaWYgeW91IHRha2UgYW4gb3B0aW1hbCBhcHByb2FjaC4gVGhpcyBudW1iZXIgc2hvdWxkIGJlIGFjY3VyYXRlIHVwIHRvIDEwPHN1cD4tNjxcL3N1cD4gcmVsYXRpdmUgb3IgYWJzb2x1dGUgcHJlY2lzaW9uLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d