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~.

Input

• 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 \le n, m \le 500~);
• ~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 ... 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~.

Output

• Đư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.

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.

Sample Input 1

4 5
1 1 2 2 2
3 3 2 2 2
1 1 3 3 1
5 2 1 1 1

Sample Output 1

8

Sample Input 2

3 3
1 2 3
4 5 6
9 8 7

Sample Output 2

18

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~.