jobs-25

Tuco Salamanca has N distributors in New Mexico. He has to distribute methamphetamine in N districts. Each distributor has some probability of getting killed in each district. Given the probability of each distributor not getting killed in each district, Tuco has to assign districts to distributors (one distributor can take only one district) such that the probability of no one getting killed is maximized. Find this value for him.    

Input: 
First line contain N, the number of districts and distributors. Each of next N lines will contain N integers each. The j'th integer on i'th line is the probability that distributor number i will not get killed if assigned to district number i.   

Output: 
Print the probability (correct to 6 decimal digits).   

Constraints: 
1 ≤ N ≤ 20   
0 ≤ Each probability ≤ 100

Notes:
1. Print output correct to 6 digits after decimal point, otherwise it leads to wrong answer.  
2. The probability of no one getting killed is equal to the product of the
probabilities of individual distributors not getting killed.

SAMPLE INPUT
3
25 60 100
13 0 50
12 70 90

SAMPLE OUTPUT
9.100000

Explanation

Distributor 1 is assigned the 3rd district.
Distributor 2 is assigned the 1st district.
Distributor 3 is assigned the 2nd district.
The probability in this case is, 10.130.7=9.1/100

Source: hackerearth | Difficulty: HARD


Solutions: