Description

The school is holding a freshmen welcome ball. As an experienced senior, Cathy is responsible for pairing up dance partners.

There are $n$ boys and $n$ girls at the ball. Each pair consists of one boy and one girl, forming a one-to-one matching.

Cathy collected relationship information between these students, such as whether two people knew each other before, and computed $a_{i,j}$.

Cathy also needs to consider how convenient it is for two people to dance together, for example whether their height and weight differences are too large, and computed $b_{i,j}$, which represents the incompatibility when the $i$-th boy dances with the $j$-th girl.

Of course, there are many other issues to consider.

Cathy wants to first use a program to find a plan based on $a_{i,j}$ and $b_{i,j}$, and then manually fine-tune the result.

A plan consists of $n$ pairs of partners. Suppose the joy levels of the pairs are $a'_1, a'_2, ..., a'_n$, and the incompatibility levels are $b'_1, b'_2, ..., b'_n$. Let $C=\frac {a'_1+a'_2+...+a'_n}{b'_1+b'_2+...+b'_n}$. Cathy wants to maximize the value of $C$.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain $n$ integers. In the $i$-th line, the $j$-th number denotes $a_{i,j}$.

The next $n$ lines each contain $n$ integers. In the $i$-th line, the $j$-th number denotes $b_{i,j}$.

Output Format

Output a single number, the maximum value of $C$. Round to $6$ decimal places. Your output must exactly match the standard output.

3
19 17 16
25 24 23
35 36 31
9 5 6
3 4 2
7 8 9

5.357143

Hint

Constraints:

• For $10\%$ of the testdata, $1 \le n \le 5$.
• For $40\%$ of the testdata, $1 \le n \le 18$.
• Additionally, for $20\%$ of the testdata, $b_{i,j} = 1$.
• For $100\%$ of the testdata, $1 \le n \le 100, 1 \le a_{i,j}, b_{i,j} \le 10^4$.

Translated by ChatGPT 5