Đào kim cương


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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

There are no comments at the moment.