Everyone knows of the secret agent double-oh-seven, the popular Bond (James Bond). A lesser known fact is that he actually did not perform most of his missions by himself; they were instead done by his cousins, the Jimmy Bonds. Bond (James Bond) has grown weary of having to assign missions to the Jimmy Bonds every time he gets new missions, so he has asked you to help him out.

Every month Bond (James Bond) receives a list of missions. Using his detailed intelligence from past missions, for every mission and every Jimmy Bond he calculates the probability of that particular mission being successfully completed by that particular Jimmy Bond. Your program should process that data and find the arrangement that results in the greatest probability that all missions are completed successfully. Each Jimmy Bond is assigned exactly one mission, and each mission to exactly one Jimmy Bond.

Note: The probability that all missions are completed successfully equals the product of the probabilities of the individual missions being completed successfully.

The first line contains an integer \(N\), the number of Jimmy Bonds and the number of missions (\(1 \le N \le 20\)).

The following \(N\) lines each contain \(N\) integers between \(0\) and \(100\), inclusive. The \(j\)-th integer on the \(i\)-th line is the probability (given as a percentage) that Jimmy Bond \(i\) would successfully complete mission \(j\).

Output the maximum probability of the Jimmy Bonds successfully completing all the missions, as a percentage.

Note: Outputs within \(±0.000001\) of the official solution will be accepted.

riseoj 작성

출처 COCI 2006/2007 Contest 1