#2055. MOVE

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Nguồn: Free Contest 7

Cho một bàn cờ hình chữ nhật gồm m hàng và n cột. Mỗi ô trên bàn cờ này có ghi một giá trị nguyên. Xuất phát từ ô (1, 1) , bạn cần di chuyển đến ô (m, n) . Ở mỗi bước, bạn được di chuyển sang phải một ô hoặc xuống dưới một ô. Hãy tìm cách di chuyển để tổng giá trị của các ô trên đường đi là lớn nhất.

Dữ liệu vào:

  • Dòng đầu tiên chứa hai số nguyên dương m n\ (1 ≤ m, n ≤500) ;
  • m dòng tiếp theo, mỗi dòng chứa n số nguyên là giá trị các ô trên bàn cờ. Các ô này có giá trị tuyệt đối không quá 10000 .

Dữ liệu ra:

  • In ra tổng giá trị lớn nhất tìm được.

Ví dụ:

Dữ liệu vào:
5 5
-9 -1 -3 6 -6
8 -3 3 -7 2
4 -3 1 -10 -9
-4 -8 -2 -3 -10
-7 7 5 4 3
Dữ liệu ra:
11