Thành phố JOI được chia thành dạng bàn cờ bởi \(H\) con đường thẳng theo hướng đông - tây và \(W\) con đường thẳng theo hướng bắc - nam. Khoảng cách giữa hai con đường song song liên tiếp bằng \(1\). Thành phố sẽ chọn một đường theo hướng đông - tây và một đường theo hướng bắc - nam trong số \(H+W\) con đường này làm hai tuyến đường chính.

Gọi giao điểm của con đường thứ \(i\) tính từ phía bắc và con đường thứ \(j\) tính từ phía tây là giao lộ \((i,j)\), với \(1 \le i \le H\) và \(1 \le j \le W\). Khoảng cách từ giao lộ \((i,j)\) đến con đường thứ \(m\) tính từ phía bắc là \(|i-m|\), còn khoảng cách đến con đường thứ \(n\) tính từ phía tây là \(|j-n|\). Có \(A_{i,j}\) cư dân sống gần giao lộ \((i,j)\).

Với mỗi cư dân, xét khoảng cách từ giao lộ gần nơi họ sống nhất đến tuyến đường chính gần hơn trong hai tuyến đã chọn. Hãy tìm giá trị nhỏ nhất có thể của tổng khoảng cách này trên tất cả cư dân trong thành phố.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(H,W\).
• Trong \(H\) dòng tiếp theo, dòng thứ \(i\) chứa \(W\) số nguyên \(A_{i,1},A_{i,2},\ldots,A_{i,W}\).

Dữ liệu ra

In ra tổng khoảng cách nhỏ nhất từ giao lộ gần mỗi cư dân nhất đến tuyến đường chính gần hơn trong hai tuyến đã chọn.

Ràng buộc

• \(2 \le H \le 25\).
• \(2 \le W \le 25\).
• \(0 \le A_{i,j} \le 100\) với mọi \(1 \le i \le H\), \(1 \le j \le W\).

Phân nhóm

1. Nhóm 1 (10 điểm): \(A_{i,j}=1\) với mọi \(1 \le i \le H\), \(1 \le j \le W\).
2. Nhóm 2 (90 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

8

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

164

Nguồn

JOI 2017/2018, vòng loại, bài 3: Trunk Road. Đề bài của Ban tổ chức Olympic Tin học Nhật Bản.