Problem H. Store The Matrix

Given a matrix M with r rows and c columns. It is obviously that we need r × c elements to store this matrix.
However, for a specific matrix M, we may be able to represent M as “Matrix-chain multiplication” likes M = A1×A2 · · ·×An, where n ≥ 1 and each Ai
is a matrix with size ri×ci. Then we can use (${∑^n}_i=1$ ri×ci) elements to store {A1, A2 . . . , An} instead of storing M directly.
We want to know: if we represent M in the optimal way, how many elements are needed at least to store M?

Input is given from Standard Input in the following format:
r c
$M_{1,1}$ $M_{1,2}$ ... $M_{1,c}$
$M_{2,1}$ $M_{2,2}$ ... $M_{2,c}$
...
...
...
$M_{r,1}$ $M_{r,2}$ ... $M_{r,c}$
Constraints
1 ≤ r, c ≤ 30
0 ≤ $M_{i,j}$ ≤ 1000(1 ≤ i ≤ r, 1 ≤ j ≤ c) (Note that although all $M_{i,j}$ are non-negative integers in the input,we think the element type is float number with infinity precision and can be negative) .

Print one integer denotes the minimal number of elements needed

3 3
1 0 1
0 0 0
1 0 1

6

2018 东北地区大学生程序设计竞赛