Mô tả và yêu cầu

Quân mã

Trên bàn cờ kích th ướ c ô, g ồm m dòng, n cộ t. C ác dòng đ ượ c đánh số từ 1..m, từ trên xu ố ng
dướ i , các cột đượ c đánh số từ 1..n từ trái qua phải , mỗ i ô ghi một số nguyên d ươ ng. Mộ t quân
mã đ ứng trên mộ t ô của dòng 1 cầ n ph ải nhảy đ ế n mộ t ô nào đó của dòng m theo quy tắ c đi của
quân mã trên bàn cờ Qu ố c tế và ch ỉ đượ c nh ảy từ dòng có ch ỉ số bé đ ế n dòng có ch ỉ số lớn h ơ n.

Quy tắc đi quân mã trên bàn c ở qu ốc tế : Từ ô có hình quân mã, nó có th ể nh ảy tớ i các ô có
chấ m đ ỏ.

Y êu c ầu: Tìm cách nh ảy sao cho tổ ng các số ghi trên các ô mà quân mã nh ảy qua l à l ớn nh ất
(kể cả ô đ ầu ti ên mà quân mã đ ứng).

D ữ liệu:

- D òng đầu ghi 2 số m, n (1≤m,n≤100) cách nhau b ởi dấu cách.

- m dòng sau mỗ i dòng ghi n số nguyên d ươ ng không quá 10000, các số cách nhau 1 d ấ u
cách.

K ết qu ả:

Mộ t số duy nh ấ t l à tổng lớn nh ấ t của các số ghi trên các ô mà quân mã nh ảy qua.

V í dụ:

IN P U T OU TP U T
3 5 26

9 4 5 6 7

3 6 8 9 1

9 6 2 8 3

Giải thích: Quân mã đi theo các ô có số đ ượ c g ạch chân. 9 -> 8-> 9.