Mountain Climbing with Special Moves

Blue is climbing a mountain where the heights of the peaks are arranged in an \(n \times m\) matrix of positive integers. The element \(a_{i,j}\) represents the height of the peak at cell \((i,j)\). He climbs in a very special way. If he is currently at cell \((p,q)\), his next step can be chosen according to the following rules:

• Move vertically downward to cell \((i, q)\) where \(i > p\) and \(a_{i,q} < a_{p,q}\).
• Move vertically upward to cell \((i, q)\) where \(i a_{p,q}\).
• Move horizontally to the right to cell \((p, j)\) where \(j > q\) and \(a_{p,j} < a_{p,q}\).
• Move horizontally to the left to cell \((p, j)\) where \(j a_{p,q}\).

Blue wishes to know: If he starts from each cell (one by one) and follows an optimal strategy (i.e. choosing his moves so that the maximum mountain height reached is as high as possible), what is the average of these highest reachable heights?

Note: The reachable height from a cell is defined as the maximum \(a_{i,j}\) value among all cells that can be reached (possibly after several moves) following the above move rules. Moves are only allowed if the strict inequality condition holds.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of rows and columns respectively).

Then follow \(n\) lines, each containing \(m\) positive integers. The \(j\)-th integer in the \(i\)-th line is \(a_{i,j}\), the height of the mountain peak at cell \((i, j)\).

You may assume that the grid is small enough to allow a \(O(n*m*(n+m))\) solution.

outputFormat

Output a single number representing the average of the maximum reachable mountain heights starting from every cell. Your answer will be considered correct if it has an absolute or relative error of at most \(10^{-6}\).

sample

2 2
3 1
2 4

3.25