數(shù)字矩陣 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic PRoblem Description

bLue 站在了一個(gè) n*m 的填有數(shù)字的矩陣中，他可以選擇從矩陣的四個(gè)頂點(diǎn)之一出發(fā)，到達(dá)斜對(duì)面的頂點(diǎn)。每一步必須向靠近目的地的方向移動(dòng)，且每次移動(dòng)都可以累加所在位置上的數(shù)字。 例如，bLue 選擇從左上角出發(fā)，那么目的地為右下角，則他每次只能向右或向下移動(dòng)一格。 現(xiàn)在他想知道在所有的走法中，能獲得的最大累加和是多少。你能幫助他嗎？

Input

輸入數(shù)據(jù)有多組（數(shù)據(jù)組數(shù)不超過 50），到 EOF 結(jié)束。 對(duì)于每組數(shù)據(jù)： 第 1 行輸入 2 個(gè)整數(shù) n, m (1 <= n, m <= 100)，表示矩陣的行數(shù)和列數(shù)。 接下來 n 行，每行包含 m 個(gè)用空格隔開的整數(shù) aij (0 <= aij <= 10000)，表示這個(gè)數(shù)字矩陣。

Output

對(duì)于每組數(shù)據(jù)，輸出 1 行，包含 1 個(gè)整數(shù)，表示 bLue 能獲得的最大的累加和。

Example Input

3 4 1 2 3 4 1 0 6 5 4 7 2 0 Example Output

28

blablabla: 學(xué)完了動(dòng)態(tài)規(guī)劃回頭看這題也不難。。 thought: 四種方向就是兩種路線，兩種答案。。