Ma trận tăng

Một ma trận $a$ kích thước $n\times m$ được gọi là tăng nếu mọi hàng đều tăng ngặt từ trái sang phải ($a_{i,1}<a_{i,2}<\dots <a_{i,m}$) và mọi cột đều tăng ngặt từ trên xuống dưới ($a_{1,j}<a_{2,j}<\dots <a_{n,j}$).

Cho một ma trận gồm các số nguyên không âm. Hãy thay mỗi giá trị $0$ bằng một số nguyên dương sao cho ma trận thu được là ma trận tăng và tổng các phần tử của nó lớn nhất có thể, hoặc cho biết điều đó là không thể.

Dữ liệu đảm bảo mọi giá trị $0$ chỉ nằm ở các ô bên trong, tức là không nằm ở hàng đầu, hàng cuối, cột đầu hay cột cuối.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số hàng và số cột của ma trận.
• $n$ dòng tiếp theo, mỗi dòng chứa $m$ số nguyên không âm $a_{i,1},a_{i,2},\dots ,a_{i,m}$.

Dữ liệu ra

In ra tổng lớn nhất có thể của các phần tử sau khi thay hết các số $0$ bằng số nguyên dương sao cho ma trận là ma trận tăng. Nếu không tồn tại cách thay nào, in ra $-1$.

Ràng buộc

• $3\le n,m\le 500$
• $0\le a_{i,j}\le 8000$
• Với mọi $a_{i,j}=0$ ta có $1<i<n$ và $1<j<m$.

Ví dụ