{"code":"twopaths","name":"Kinh nghiệm (OLP 10&11 - 2019)","description":"Hai anh em An và Bình tham gia một trò chơi thám hiểm trên bảng số $xTremeMaze$.\r\nBảng có kích thước $N$x$M$ ($N$ dòng và $M$ cột). Các ô trong bảng được đánh số từ trái sang phải và từ\r\ntrên xuống dưới.\r\n\r\nTại mỗi ô của bảng có ghi một số nguyên là số điểm kinh nghiệm mà người chơi sẽ nhận được khi\r\nđi vào ô này. Cần lưu ý là số điểm tại một số ô có thể là số âm; khi đó, điểm kinh nghiệm của người\r\nchơi sẽ bị giảm nếu đi vào ô này.\r\n\r\nAn và Bình bắt đầu tại ô trái trên, đánh số là ($1, 1$). Mỗi lượt, một người chỉ có thể di chuyển tới ô\r\nkề cạnh ngay phía dưới hoặc ô kề cạnh ngay bên phải và không được phép đi ra khỏi bảng. Khi đi\r\nqua mỗi ô, người chơi nhận được số điểm kinh nghiệm bằng số nguyên ghi ở ô đó. Hành trình kết\r\nthúc tại ô ($N, M$).\r\n\r\nMục tiêu của trò chơi này là hai anh em đạt được tổng số điểm cao nhất có thể. Theo quy định, các ô\r\nmà An và Bình đi qua không được phép trùng nhau, ngoại trừ ô bắt đầu tại vị trí ($1, 1$) và ô kết thúc\r\ntại vị trí ($N, M$). Quy ước: giá trị điểm kinh nghiệm tại ô ($1, 1$) và ô ($N, M$) đều bằng 0.\r\n\r\n**Yêu cầu**: Hãy viết chương trình tính tổng số điểm kinh nghiệm lớn nhất mà An cùng với Bình đạt\r\nđược.\r\n\r\n

Input

\r\n\r\n- Dòng đầu chứa hai số nguyên $N$ và M ($2 \\le N, M \\le 200$), số dòng và số cột của bảng.\r\n- $N$ dòng tiếp theo, mỗi dòng ghi M số nguyên là số điểm kinh nghiệm tại mỗi ô trên bảng.\r\nĐiểm kinh nghiệm tại mỗi ô có giá trị tuyệt đối không vượt quá 100.\r\n\r\n

Output

\r\n\r\n- Ghi ra duy nhất một số nguyên là tổng điểm lớn nhất mà\r\nAn cùng với Bình đạt được.\r\n\r\n

Scoring

\r\n\r\n - Subtask $1$ ($30\\%$ số điểm): $N \\le 3$ và $M \\le 200$.\r\n - Subtask $2$ ($40\\%$ số điểm): $N \\le 50$ và $M \\le 50$.\r\n - Subtask $3$ ($30\\%$ số điểm): Không có điều kiện gì thêm.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 3 3\r\n 0 2 3\r\n 4 5 6\r\n 7 8 0\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 32\r\n ```","points":300.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}