Combination of Physics and Maths

题号：NC209994
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

Roundgod has an $n \times m$ matrix $A = [a_{i,j}]$ . One day while she's doing her physics homework, she wonders is it possible to define the physical quantity for matrices.

As we all know, the pressure $p$ satisfies a formula $p=\frac{F}{S}$ , where $F$ is the compressive force and $S$ is the base area.

To describe it in maths, Roundgod puts forward that the compressive force of a matrix equals the sum of all its entries, while the base area of a matrix equals the sum of the entries in its last row. Then she can calculate the pressure for a matrix with the same formula.

Your goal is to find the submatrix of $A$ with maximum pressure.

A submatrix is obtained by taking nonempty subsets of its rows and columns. Formally, given a nonempty subsequence $S$ of $\{1,2, \ldots, n\}$ and a nonempty subsequence $T$ of $\{1, 2, \ldots, m\}$ , then
$\begin{bmatrix} a_{S_1, T_1} & a_{S_1, T_2} & \cdots & a_{S_1, T_{|T|}} \\ a_{S_2, T_1} & a_{S_2, T_2} & \cdots & a_{S_2, T_{|T|}} \\ \vdots & \vdots & \ddots & \vdots \\ a_{S_{|S|}, T_1} & a_{S_{|S|}, T_2} &\cdots & a_{S_{|S|}, T_{|T|}} \end{bmatrix}$

is a submatrix of $A$ .

输入描述:

There are multiple test cases. The first line of input contains an integer , indicating the number of test cases. For each test case:
The first line contains two integers , the number of rows and columns of the matrix, respectively.
Each of the next  lines contains  integers, specifying the matrix .

输出描述:

For each test case, print the maximum pressure within an absolute or relative error of no more than  in one line.

示例1

输入

复制

输出

复制

4.50000000

说明

is one of submatrices of  with maximum pressure .