18521번 - Jeopardy 다국어

You are playing the final round of an intellectual game. A total of n topics were selected, and each of the n authors prepared a question for each topic. For each topic i and each author j, you know the probability that you will answer the question from the j-th author on the i-th topic.

Before you actually get the question, n − 1 turns are made. Two actions happen during each turn. First, you discard all questions of any single topic. Second, the moderator discards all questions from any single author. Eventually only one question remains. If you answer it correctly, you win the round.

Of course, you discard columns trying to maximize the probability of your victory. On the contrary, the moderator tries do minimize it.

If you both play optimally, what is the probability that you answer the remaining question?

In the first line, there is a single integer n (1 ≤ n ≤ 500), the number of topics and authors. Then follow n lines with n integers on each line. The i-th line corresponds to the i-th topic, and the j-th number on it is the probability that you will answer the question by the j-th author.

The probabilities are given as percentages. All integers in the description of topics are between 0 and 100.

Print a single number: the desired probability as a percentage.