Problem Description

The city of JOI is divided into a grid by $ H $ straight roads running east-west and $ W $ straight roads running north-south. The distance between adjacent roads is $ 1 $. The city has decided to select $ 1 $ road from the east-west roads and $ 1 $ road from the north-south roads to be the trunk roads, totaling $ 2 $ trunk roads.

The intersection of the $ i $-th road from the north ($ 1≦i≦H $) and the $ j $-th road from the west ($ 1≦j≦W $) is denoted as intersection $ (i,j) $. The distance between intersection $ (i,j) $ and the $ m $-th road from the north ($ 1≦m≦H $) is $ |i-m| $, and the distance between intersection $ (i,j) $ and the $ n $-th road from the west ($ 1≦n≦W $) is $ |j-n| $. Additionally, there are $ A_{i,j} $ residents living near intersection $ (i,j) $.

Determine the minimum sum of distances from the nearest intersection to the nearest trunk road for all residents in the city when $ 2 $ trunk roads are selected.

Input Format

The input is given from the 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} $

Output Format

Output the minimum sum of distances from the nearest intersection to the nearest trunk road for all residents in the city.

Sample Input and Output

Sample Input #1

3 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Sample Output #1

8

Sample Input #2

5 5
1 2 3 1 5
1 22 11 44 3
1 33 41 53 2
4 92 35 23 1
4 2 6 3 5

Sample Output #2

164

Notes/Hints

Constraints

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

Subtask 1 \[10 points\]

• $A_{i,j}\ =\ 1$ ($1\ ≦\ i\ ≦\ H$, $1\ ≦\ j\ ≦\ W$)

Subtask 2 \[90 points\]

• No additional constraints.

Sample Explanation 1

For example, it is good to select the $ 2 $-nd road from the north and the $ 1 $-st road from the west as trunk roads.

Sample Explanation 2

It is good to select the $ 3 $-rd road from the north and the $ 2 $-nd road from the west as trunk roads.

见题面 Input 部分

见题面 Output 部分