Cho bảng lưới ô vuông kích thước ~ n × 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

• Dòng đầu tiên ghi lần lượt hai số nguyên dương ~ n, m ~ ~ (1 ≤ n, m ≤ 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 ~.

Kết quả

Một số nguyên duy nhất là kết quả bài toán.

Ràng buộc

• Có 50% số test có các ô chung cạnh có giá trị khác nhau.
• Có 50% số test còn lại không có ràng buộc gì thêm.

Ví dụ:

Input 1

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

Output 1

8 

Input 2

3 3
1 2 3
4 5 6
9 8 7 

Output 2

18