Đào kim cương
An đang chơi một game đào kim cương. Cậu sẽ có một bảng $N$ hàng, $M$ cột. Ô ở hàng thứ $i$ và cột thứ $j$ có giá trị $a_{i,j}$.
Cậu cần chọn một ô $(x,y)$ và độ dài cạnh $k$. Những ô có khoảng cách Manhattan đến ô $(x,y)$ không quá $k$ (các ô được chọn cần thuộc bảng và tạo thành hình thoi) sẽ được chọn và tính tổng giá trị. Giá trị càng cao thì điểm càng lớn.
Hãy giúp An tìm giá trị lớn nhất có thể.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N, M \ (0<N,M\le200)$;
- $N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên $a_{i,j} \ (|a_{i,j}| \le 10^9)$.
Kết quả
- Kết quả bài toán.
Ví dụ
Ví dụ 1
input
3 4
1 2-2 3
1-2 1 3
4 3 1-2
output
5
Comments