P3705 [SDOI2017] Freshmen Welcome Ball

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$.

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 a single number, the maximum value of $C$. Round to $6$ decimal places. Your output must exactly match the standard output.

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