Tập Luyện

Cho một bảng số nguyên không âm kích thước $n\times m$, ô $(i,j)$ có giá trị $a_{i,j}$.

Có hai người di chuyển trong bảng:

• Người 1 xuất phát tại ô $(1,1)$ và kết thúc tại ô $(n,m)$. Tại mỗi bước, từ ô $(i,j)$ người này có thể đi đến $(i+1,j)$ hoặc $(i,j+1)$.
• Người 2 xuất phát tại ô $(n,1)$ và kết thúc tại ô $(1,m)$. Tại mỗi bước, từ ô $(i,j)$ người này có thể đi đến $(i,j+1)$ hoặc $(i-1,j)$.

Hai người phải gặp nhau tại đúng một ô trên bảng. Ô gặp nhau này không được tính giá trị cho bất kỳ ai. Tất cả các ô khác mà ít nhất một trong hai người đi qua (bao gồm ô xuất phát và ô kết thúc của mỗi người) đều được cộng vào tổng giá trị, mỗi ô tính tối đa một lần.

Hãy chọn đường đi của hai người sao cho tổng giá trị thu được là lớn nhất.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $n$ dòng tiếp theo, mỗi dòng chứa $m$ số nguyên mô tả bảng giá trị.

Dữ liệu ra

• Một số nguyên duy nhất là tổng giá trị lớn nhất thu được.

Ràng buộc

• $3\le n,m\le 1000$
• $0\le a_{i,j}\le {10}^5$

Ví dụ