Optimal Mission Assignment for Jimmy Bonds

James Bond is tired of assigning missions manually to his cousins, the Jimmy Bonds. Each month, he receives a list of missions as well as intelligence data giving the success probability for every Jimmy Bond on every mission. Your task is to help Bond find the assignment of missions to his cousins such that the overall probability of all missions being successfully completed is maximized.

Note: The overall probability of success is equal to the product of the individual mission success probabilities. All probabilities are given as percentages. In calculating the overall probability, first convert each percentage to a fraction, multiply them together, and then convert the result back to a percentage.

For example, if a mission has a success chance of 80% and the assigned mission has a success chance of 90%, the overall success probability is computed as (80/100)*(90/100)*100=72.000000%.

Your solution should output the maximum overall success probability as a percentage, formatted to exactly 6 decimal places.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 20), representing the number of missions and the number of Jimmy Bonds. Each of the following n lines contains n float numbers. The j-th number on the i-th line represents the success probability (in percentage) that Jimmy Bond j can complete mission i.

outputFormat

Output the maximum overall probability (in percentage) that all missions are completed successfully. The answer must be printed with exactly 6 decimal places.

sample

2
80 70
50 90

72.000000