시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1009 210 151 22.239%

문제

비밀 요원 007은 제임스 본드로 유명한 비밀 요원이다. 최근 알려진 정보에 의하면 제임스본드는 대다수 미션을 자신이 직접 수행하지 않는다고 한다. 본드는 미션을 자신과 비슷하게 생긴 사촌들인 지미 본드에게 시킨다. 제임스 본드는 MI6로부터 미션을 받으면, 각 미션을 사촌들에게 하나씩 할당해 준다.

매달 초에 제임스 본드는 미션 목록을 받게 된다. 그 다음에 그는 각각의 지미 본드에 대해서 미션을 성공적으로 수행할 확률을 구한다. 이제, 전체 미션을 성공할 확률이 가장 크게 되게 미션을 지미 본드에게 나누어 주려고 한다. 어떤 미션을 어떤 지미 본드에게 나누어 주어야 할 지를 결정한 다음, 전체 미션을 성공할 확률을 구하는 프로그램을 작성하시오.

모든 미션을 성공적으로 끝낼 확률은 각 미션을 성공적으로 끝낼 확률을 모두 곱하면 된다.

입력

첫째 줄에 미션과 지미 본드의 수인 N이 주어진다. (1 ≤ N ≤ 20)

다음 N개 줄에는 0과 100 사이의 정수가 N개씩 주어진다. i번째 줄의 j번째 숫자는 지미 본드 i가 미션 j를 성공적으로 마칠 확률이며, 퍼센트로 주어진다. 

출력

첫째 줄에 모든 미션을 성공적으로 마칠 확률을 퍼센트로 출력한다. 정답과의 오차는 ±0.000001까지 허용한다.

예제 입력 1

3
25 60 100
13 0 50
12 70 90

예제 출력 1

9.10000

힌트

W3sicHJvYmxlbV9pZCI6IjMwNTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiIwMDciLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YmU0NFx1YmMwMCBcdWM2OTRcdWM2ZDAgMDA3XHVjNzQwIFx1YzgxY1x1Yzc4NFx1YzJhNCBcdWJjZjhcdWI0ZGNcdWI4NWMgXHVjNzIwXHViYTg1XHVkNTVjIFx1YmU0NFx1YmMwMCBcdWM2OTRcdWM2ZDBcdWM3NzRcdWIyZTQuIFx1Y2Q1Y1x1YWRmYyBcdWM1NGNcdWI4MjRcdWM5YzQgXHVjODE1XHViY2Y0XHVjNWQwIFx1Yzc1OFx1ZDU1OFx1YmE3NCBcdWM4MWNcdWM3ODRcdWMyYTRcdWJjZjhcdWI0ZGNcdWIyOTQgXHViMzAwXHViMmU0XHVjMjE4IFx1YmJmOFx1YzE1OFx1Yzc0NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjOWMxXHVjODExIFx1YzIxOFx1ZDU4OVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJjZjhcdWI0ZGNcdWIyOTQgXHViYmY4XHVjMTU4XHVjNzQ0IFx1Yzc5MFx1YzJlMFx1YWNmYyBcdWJlNDRcdWMyYjdcdWQ1NThcdWFjOGMgXHVjMGRkXHVhZTM0IFx1YzBhY1x1Y2QwY1x1YjRlNFx1Yzc3OCBcdWM5YzBcdWJiZjggXHViY2Y4XHViNGRjXHVjNWQwXHVhYzhjIFx1YzJkY1x1ZDBhOFx1YjJlNC4gXHVjODFjXHVjNzg0XHVjMmE0IFx1YmNmOFx1YjRkY1x1YjI5NCBNSTZcdWI4NWNcdWJkODBcdWQxMzAgXHViYmY4XHVjMTU4XHVjNzQ0IFx1YmMxYlx1YzczY1x1YmE3NCwgXHVhYzAxIFx1YmJmOFx1YzE1OFx1Yzc0NCBcdWMwYWNcdWNkMGNcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVkNTU4XHViMDk4XHVjNTI5IFx1ZDU2MFx1YjJmOVx1ZDU3NCBcdWM5MDBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjllNFx1YjJlYyBcdWNkMDhcdWM1ZDAgXHVjODFjXHVjNzg0XHVjMmE0IFx1YmNmOFx1YjRkY1x1YjI5NCBcdWJiZjhcdWMxNTggXHViYWE5XHViODVkXHVjNzQ0IFx1YmMxYlx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVhZGY4XHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM5YzBcdWJiZjggXHViY2Y4XHViNGRjXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWJiZjhcdWMxNThcdWM3NDQgXHVjMTMxXHVhY2Y1XHVjODAxXHVjNzNjXHViODVjIFx1YzIxOFx1ZDU4OVx1ZDU2MCBcdWQ2NTVcdWI5NjBcdWM3NDQgXHVhZDZjXHVkNTVjXHViMmU0LiBcdWM3NzRcdWM4MWMsIFx1YzgwNFx1Y2NiNCBcdWJiZjhcdWMxNThcdWM3NDQgXHVjMTMxXHVhY2Y1XHVkNTYwIFx1ZDY1NVx1Yjk2MFx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVkMDZjXHVhYzhjIFx1YjQxOFx1YWM4YyBcdWJiZjhcdWMxNThcdWM3NDQgXHVjOWMwXHViYmY4IFx1YmNmOFx1YjRkY1x1YzVkMFx1YWM4YyBcdWIwOThcdWIyMDRcdWM1YjQgXHVjOGZjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNWI0XHViNWE0IFx1YmJmOFx1YzE1OFx1Yzc0NCBcdWM1YjRcdWI1YTQgXHVjOWMwXHViYmY4IFx1YmNmOFx1YjRkY1x1YzVkMFx1YWM4YyBcdWIwOThcdWIyMDRcdWM1YjQgXHVjOGZjXHVjNWI0XHVjNTdjIFx1ZDU2MCBcdWM5YzBcdWI5N2MgXHVhY2IwXHVjODE1XHVkNTVjIFx1YjJlNFx1Yzc0YywgXHVjODA0XHVjY2I0IFx1YmJmOFx1YzE1OFx1Yzc0NCBcdWMxMzFcdWFjZjVcdWQ1NjAgXHVkNjU1XHViOTYwXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJhYThcdWI0ZTAgXHViYmY4XHVjMTU4XHVjNzQ0IFx1YzEzMVx1YWNmNVx1YzgwMVx1YzczY1x1Yjg1YyBcdWIwNWRcdWIwYmMgXHVkNjU1XHViOTYwXHVjNzQwIFx1YWMwMSBcdWJiZjhcdWMxNThcdWM3NDQgXHVjMTMxXHVhY2Y1XHVjODAxXHVjNzNjXHViODVjIFx1YjA1ZFx1YjBiYyBcdWQ2NTVcdWI5NjBcdWM3NDQgXHViYWE4XHViNDUwIFx1YWNmMVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiJcclxuPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiZjhcdWMxNThcdWFjZmMgXHVjOWMwXHViYmY4IFx1YmNmOFx1YjRkY1x1Yzc1OCBcdWMyMThcdWM3NzggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDIwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1YWNmYyAxMDAgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBOXHVhYzFjXHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM3NTggalx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVjOWMwXHViYmY4IFx1YmNmOFx1YjRkYyBpXHVhYzAwIFx1YmJmOFx1YzE1OCBqXHViOTdjIFx1YzEzMVx1YWNmNVx1YzgwMVx1YzczY1x1Yjg1YyBcdWI5YzhcdWNlNjAgXHVkNjU1XHViOTYwXHVjNzc0XHViYTcwLCBcdWQzN2NcdWMxM2NcdWQyYjhcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYWE4XHViNGUwIFx1YmJmOFx1YzE1OFx1Yzc0NCBcdWMxMzFcdWFjZjVcdWM4MDFcdWM3M2NcdWI4NWMgXHViOWM4XHVjZTYwIFx1ZDY1NVx1Yjk2MFx1Yzc0NCBcdWQzN2NcdWMxM2NcdWQyYjhcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM4MTVcdWIyZjVcdWFjZmNcdWM3NTggXHVjNjI0XHVjYzI4XHViMjk0ICZwbHVzbW47MC4wMDAwMDFcdWFlNGNcdWM5YzAgXHVkNWM4XHVjNmE5XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwNTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCT05EIiwiZGVzY3JpcHRpb24iOiI8cD5FdmVyeW9uZSBrbm93cyBvZiB0aGUgc2VjcmV0IGFnZW50IGRvdWJsZS1vaC1zZXZlbiwgdGhlIHBvcHVsYXIgQm9uZCAoSmFtZXMgQm9uZCkuIEEgbGVzc2VyIGtub3duIGZhY3QgaXMgdGhhdCBoZSBhY3R1YWxseSBkaWQgbm90IHBlcmZvcm0gbW9zdCBvZiBoaXMgbWlzc2lvbnMgYnkgaGltc2VsZjsgdGhleSB3ZXJlIGluc3RlYWQgZG9uZSBieSBoaXMgY291c2lucywgSmltbXkgQm9uZHMuIEJvbmQgKEphbWVzIEJvbmQpIGhhcyBncm93biB3ZWFyeSBvZiBoYXZpbmcgdG8gZGlzdHJpYnV0ZSBhc3NpZ24gbWlzc2lvbnMgdG8gSmltbXkgQm9uZHMgZXZlcnkgdGltZSBoZSBnZXRzIG5ldyBtaXNzaW9ucyBzbyBoZSBoYXMgYXNrZWQgeW91IHRvIGhlbHAgaGltIG91dC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RXZlcnkgbW9udGggQm9uZCAoSmFtZXMgQm9uZCkgcmVjZWl2ZXMgYSBsaXN0IG9mIG1pc3Npb25zLiBVc2luZyBoaXMgZGV0YWlsZWQgaW50ZWxsaWdlbmNlIGZyb20gcGFzdCBtaXNzaW9ucywgZm9yIGV2ZXJ5IG1pc3Npb24gYW5kIGZvciBldmVyeSBKaW1teSBCb25kIGhlIGNhbGN1bGF0ZXMgdGhlIHByb2JhYmlsaXR5IG9mIHRoYXQgcGFydGljdWxhciBtaXNzaW9uIGJlaW5nIHN1Y2Nlc3NmdWxseSBjb21wbGV0ZWQgYnkgdGhhdCBwYXJ0aWN1bGFyIEppbW15IEJvbmQuIFlvdXIgcHJvZ3JhbSBzaG91bGQgcHJvY2VzcyB0aGF0IGRhdGEgYW5kIGZpbmQgdGhlIGFycmFuZ2VtZW50IHRoYXQgd2lsbCByZXN1bHQgaW4gdGhlIGdyZWF0ZXN0IHByb2JhYmlsaXR5IHRoYXQgYWxsIG1pc3Npb25zIGFyZSBjb21wbGV0ZWQgc3VjY2Vzc2Z1bGx5LjxcL3A+XHJcblxyXG48cD5Ob3RlOiB0aGUgcHJvYmFiaWxpdHkgb2YgYWxsIG1pc3Npb25zIGJlaW5nIGNvbXBsZXRlZCBzdWNjZXNzZnVsbHkgaXMgZXF1YWwgdG8gdGhlIHByb2R1Y3Qgb2YgdGhlIHByb2JhYmlsaXRpZXMgb2YgdGhlIHNpbmdsZSBtaXNzaW9ucyBiZWluZyBjb21wbGV0ZWQgc3VjY2Vzc2Z1bGx5LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgd2lsbCBjb250YWluIGFuIGludGVnZXIgTiwgdGhlIG51bWJlciBvZiBKaW1teSBCb25kcyBhbmQgbWlzc2lvbnMgKDEgJmxlOyBOICZsZTsgMjApLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIE4gbGluZXMgd2lsbCBjb250YWluIE4gaW50ZWdlcnMgYmV0d2VlbiAwIGFuZCAxMDAsIGluY2x1c2l2ZS4gVGhlIGotdGggaW50ZWdlciBvbiB0aGUgaXRoIGxpbmUgaXMgdGhlIHByb2JhYmlsaXR5IHRoYXQgSmltbXkgQm9uZCBpIHdvdWxkIHN1Y2Nlc3NmdWxseSBjb21wbGV0ZSBtaXNzaW9uIGosIGdpdmVuIGFzIGEgcGVyY2VudGFnZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1heGltdW0gcHJvYmFiaWxpdHkgb2YgSmltbXkgQm9uZHMgc3VjY2Vzc2Z1bGx5IGNvbXBsZXRpbmcgYWxsIHRoZSBtaXNzaW9ucywgYXMgYSBwZXJjZW50YWdlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiBPdXRwdXRzIHdpdGhpbiAmcGx1c21uOzAuMDAwMDAxIG9mIHRoZSBvZmZpY2lhbCBzb2x1dGlvbiB3aWxsIGJlIGFjY2VwdGVkLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==