Found one interesting task. I will think over the decision and it would be nice to hear your suggestions:

Each month, James Bond receives a list of missions. Based on his wealth of experience, he calculates the probability of successfully completing the missions of each of his cousins Jimi Bond number X.

Your program must process this data and find such a separation of missions between cousins to get the greatest chance that all missions will be successfully completed.

Note: the probability that all missions will be successfully completed is equal to the product of the probabilities that individual missions will be completed successfully.

Input format

The first line contains an integer N - the number of missions (1 <= N <= 20). The next N lines contain N integers from 0 to 100, inclusive. The j-th integer on the i-th line means the probability that cousin i will successfully complete the mission j. The probability is given as a percentage.

Output format

Print the maximum probability of successful completion of all missions, as a percentage.

Conclusion that differs from the official response by no more than +0.000001 will be accepted.

Examples

`input input input 2 2 3 100 100 0 50 25 60 100 50 50 50 0 13 0 50 12 70 90 output output output 50.000000 25.00000 9.10000`

Explanation of the 3rd example:

If Jimmy 1 is assigned to the 3rd mission, Jimmy 2 is assigned to the 1st mission, and Jimmy 3 is assigned to the 2nd mission, then we will get the success rate equal to 1.0 * 0.13 * 0.7 = 0.091 = 9.1%. All other mission distribution options are less likely to succeed.

** PS** Question to the administration: I often solve problems of this type (sports programming) and, if I offer them to solve (too often) on this forum, would you consider that I flood your website and will not follow this ban?

d can easily be less than bc. This greedy strategy does not take into account. - Fiztex