Truy tìm tội phạm

Chọn HSG Bạc Liêu 2012 - Bảng A - Ngày 1 - Bài 3/3
ở một khu Bảo tàng có rất nhiều đồ cổ quý, mỗi món đồ cổ được để ở một phòng khác nhau. Cấu trúc của khu Bảo tàng gồm có n dãy phòng, mỗi dãy gồm m phòng, các phòng được xây dựng theo m hình hình chữ nhật và dãy thứ i được đánh số a[i,1], a[i,2], a[i,3]…a[i,m]. Khách tham quan chỉ có thể vào từ các phòng a[1,1], a[2,1], [3,1],…,a[n,1] và ra từ các phòng a[1,m], a[2,m], a[3,m],…,a[n,m]. Để đm bo trật tự nên Bo tàng quy định: từ phòng a[i,j] khách chỉ có thể đi qua các phòng a[i-1,j+1], a[i,j+1], a[i+1,j+1] và không được quay lại.
 Vào một ngày nọ, có một tên trộm thông minh và tham lam ghé thăm khu Bo tàng. Khi hắn đi qua phòng nào thì lấy cắp món đồ ở phòng đó. Vì tính tham lam nên hắn đã tính toán để khi ra khỏi khu Bo tàng thì tổng giá trị của các món đồ cổ lấy cắp được phi lớn nhất và hắn đã làm được điều đó.  Không cần đến khu Bảo tàng kiểm tra, bạn hãy giúp công an xác định xem tổng giá trị của các món đồ mà tên trộm đã lấy cắp.
Dữ liệu vào: Ghi trong tập tin văn bản TRUYTIM.INP gồm:
- Dòng 1: Gồm 2 số n, m (n,m <= 100)
- n dòng tiếp theo, mỗi dòng gồm m số là giá trị của các món đồ cổ trong phòng tương ứng (giá trị của các món đồ cổ <= 10.000). Các số cách nhau ít nhất một khong trắng.
Dữ liệu ra: Ghi vào tập tin văn bản TRUYTIM.OUT gồm một số duy nhất là tổng giá trị của các món đồ mà tên trộm lấy cắp.
Ví dụ:
   TRUYTIM.INP
      3 4
      5 2 4 6
      4 9 2 4
      7 2 6 6
   TRUYTIM.OUT
      28

                                                           Lời giải tham khảo