Trường THPT Chuyên Hoàng Văn Thụ - Hòa Bình

Bạn được phân công thực tập trong xưởng sản xuất bom Sát Thát.

Mục tiêu lần này của chúng ta là khu vực dàn khoan HD - 189 trên biển Đông.

Khu vực này là một bảng kích thước N x M, trong đó mỗi ô của bảng là một số nguyên.

Bom của xưởng sản xuất có dạng hình thoi. Hình thoi có tâm (x0,y0) và bán kính k là tập hợp tất cả các ô (x,y) thỏa mãn |x - x0| + |y - y0| < k. Bảng dưới minh họa hình thoi có tâm ở (3,2) và bán kính là 2.

Nhiệm vụ của bạn là xác định ném bom vào đâu để tổng giá trị trong các ô bị trúng bom là lớn nhất có thể. Không phần nào của bom bị rơi ra ngoài bảng.

hình thoi có tâm ở (3,2) và bán kính là 2

Input

• Dòng đầu tiên chứa hai số nguyên N và M (1 <= N, M <= 500)
• N dòng tiếp theo, mỗi dòng chứa M số nguyên thuộc đoạn [-10^5,10^5]
• Có 50% test N, M <= 100

Output

• Tổng giá trị lớn nhất các ô bị trúng bom

Example

Input:
5 6

1 1 -10 1 1 1

1 2 1 1 1 1

2 2 2 1 1 1

1 2 1 1 1 1

1 1 1 -10 1 1

Output:
10