B. Maximize the Mean
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a $$$n \times n$$$ grid. You can perform the following operation:

  • Select any row or column in the grid and replace each integer in that row or column with the mean of the integers in that row or column.

Your task is to maximize the minimum value in the grid by performing the operations any number of times.

Input

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the size of the grid.

Each of the following $$$n$$$ lines contains $$$n$$$ integers $$$a_{i,j}$$$ ($$$1 \leq a_{i,j} \leq 10^9$$$) — the elements of the grid.

Output

Output the maximum possible minimum value in the grid after the operations.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a-b|}{\max(1,|b|)}\le 10^{-6}$$$.

Example
Input
2
7 8
1 2
Output
4.5000000
Note

In the first example, we can obtain the answer in the following way:

  1. Choose column $$$1$$$: $$$ \begin{pmatrix} \color{orange}7 & 8 \\ \color{orange}1 & 2 \end{pmatrix} \rightarrow \begin{pmatrix} \color{orange}4 & 8 \\ \color{orange}4 & 2 \end{pmatrix} $$$
  2. Choose column $$$2$$$: $$$ \begin{pmatrix} 4 & \color{orange}8 \\ 4 & \color{orange}2 \end{pmatrix} \rightarrow \begin{pmatrix} 4 & \color{orange}5 \\ 4 & \color{orange}5 \end{pmatrix} $$$
  3. Choose row $$$1$$$: $$$ \begin{pmatrix} \color{orange}4 & \color{orange}5 \\ 4 & 5 \end{pmatrix} \rightarrow \begin{pmatrix} \color{orange}{4.5} & \color{orange}{4.5} \\ 4 & 5 \end{pmatrix} $$$
  4. Choose row $$$2$$$: $$$ \begin{pmatrix} 4.5 & 4.5 \\ \color{orange}4 & \color{orange}5 \end{pmatrix} \rightarrow \begin{pmatrix} 4.5 & 4.5 \\ \color{orange}{4.5} & \color{orange}{4.5} \end{pmatrix} $$$

Now, the minimal number in the grid is $$$4.5$$$.