].One day while she's doing her physics homework, she wonders is it possible to define the physical quantity for matrices.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.A submatrix is obtained by taking nonempty subsets of its rows and columns. Formally, given a nonempty subsequence. 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}
Roundgod has an n times m n×m matrix A = [a_{i,j}] 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 p satisfies a formula p=frac{F}{S} p= S F , where F F is the compressive force and S 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 A with maximum pressure. A submatrix is obtained by taking nonempty subsets of its rows and columns. Formally, given a nonempty subsequence S S of {1,2, ldots, n} {1,2,…,n} and a nonempty subsequence T T of {1, 2, ldots, m} {1,2,…,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} ⎣ ⎢ ⎢ ⎢ ⎡ a S 1 ,T 1 a S 2 ,T 1 ⋮ a S ∣S∣ ,T 1 a S 1 ,T 2 a S 2 ,T 2 ⋮ a S ∣S∣ ,T 2 ⋯ ⋯ ⋱ ⋯ a S 1 ,T ∣T∣ a S 2 ,T ∣T∣ ⋮ a S ∣S∣ ,T ∣T∣ ⎦ ⎥ ⎥ ⎥ ⎤ is a submatrix of A A.
