Trunk Roads

JOI City is cut into a grid by $H$ roads that run straight from east to west and $W$ roads that run straight from north to south. Neighbouring parallel roads are $1$ apart. The city will choose $2$ of these $H + W$ roads as trunk roads: one east-west road and one north-south road.

Call the point where the $i$-th east-west road from the north ($1 \le i \le H$) meets the $j$-th north-south road from the west ($1 \le j \le W$) intersection $(i, j)$. The distance between intersection $(i, j)$ and the $m$-th east-west road from the north ($1 \le m \le H$) is $|i - m|$, and the distance between intersection $(i, j)$ and the $n$-th north-south road from the west ($1 \le n \le W$) is $|j - n|$. $A_{i,j}$ residents live near intersection $(i, j)$.

Each resident pays the distance from the intersection where they live to whichever of the two trunk roads is closer. Over all ways of choosing the $2$ trunk roads, find the smallest possible total paid by all residents.

Input is given from standard input in the following format.

H W
A_{1,1} A_{1,2} ... A_{1,W}
...
A_{H,1} A_{H,2} ... A_{H,W}

The first line contains $H$ and $W$ separated by a space. The $i$-th of the next $H$ lines contains $A_{i,1}, A_{i,2}, \dots, A_{i,W}$ separated by spaces.

Print on one line the smallest possible total paid by all residents.

• $2 \le H \le 25$
• $2 \le W \le 25$
• $0 \le A_{i,j} \le 100$ ($1 \le i \le H$, $1 \le j \le W$)