Cho bảng lưới ô vuông kích thước \(n \times m\), các dòng được đánh số từ trên xuống dưới theo thứ tự từ 1 đến \(n\), các cột được đánh số từ trái sang phải theo thứ tự từ 1 đến \(m\), ô nằm giao ở dòng \(i\) cột \(j\) là ô \((i,j)\). Trên mỗi ô \((i,j)\) được gán một số nguyên dương, trong đó ô \((1,1)\) luôn có giá trị là 1.

Một dãy các ô có giá trị giống nhau từ ô \((u,v)\) đến ô \((s,t)\) với hai ô liên tiếp có cạnh chung được gọi là đường đi từ ô \((u,v)\) đến ô \((s,t)\).

Một vùng là tập hợp các ô sao cho hai ô bất kỳ trong vùng đều có đường đi đến nhau và không có đường đi đến các ô vùng khác.

Có thể thay đổi giá trị của tất cả các ô trong một vùng thành số 1 với chi phí được tính bằng tích của giá trị một ô với số lượng ô của vùng đó.

Yêu cầu: Hãy cho biết tổng chi phí nhỏ nhất để thay đổi giá trị của một số vùng trong bảng lưới sao cho từ ô \((1,1)\) có đường đi đến ô \((n,m)\) với tất cả các ô trên đường đi đều có giá trị 1.

Dữ liệu vào: Từ tệp văn bản VLUOI.INP:

• Dòng đầu tiên ghi lần lượt hai số nguyên dương \(n,\ m\ (1 \leq n,m \leq 1000)\);

• \(n\) dòng tiếp theo, mỗi dòng ghi \(m\) số nguyên dương cho biết giá trị của các ô trên lưới, trong đó số thứ \(j\ (j = 1..m)\) của dòng thứ \(i\ (i = 1\ldots n)\) là giá trị của ô \((i,j)\), giá trị của các ô là số nguyên dương không vượt quá \(10^{4}\).

Kết quả: Đưa ra tệp văn bản VLUOI.OUT một số nguyên duy nhất là kết quả bài toán.

Ví dụ:

Giải thích: Các số in đậm là các vùng được thay đổi để có kết quả tốt nhất.

Trong ví dụ 1, chi phí để chuyển các vùng về giá trị 1 là:

Vùng các ô \((2,1);(2,2)\) có chi phí \(3 \times 2 = 6\).

Vùng có ô \((4,2)\) có chi phí \(2 \times 1 = 2\)

Do vậy tổng chi phí là \(6 + 2 = 8\)

Ràng buộc:

+ Có 50% số test tương ứng với 50% số điểm các ô chung cạnh có giá trị khác nhau.

+ Có 50% số test còn lại tương ứng 50% số điểm không có ràng buộc gì thêm.