Phần thưởng

Sau khi tham gia kỳ thi học sinh giỏi cấp tỉnh lớp 9 THCS trở về, các học sinh trong đội tuyển môn Tin học khá mệt mỏi sau thời gian ôn tập. Cô giáo phụ trách đội tuyển muốn dành tặng các bạn một số phần thưởng. Tuy nhiên, để tăng tính giải trí, cô đã tạo ra một trò chơi. Phần thưởng được trao cho người có điểm cao nhất.

Cách chơi như sau: Sân chơi là một hình chữ nhật đơn vị có kích thước $m \times n$. Học sinh chọn một ô bất kỳ ở cột 1 và bước vào ô đó. Sau đó bước vào ô ở cột liền kề bên phải theo hướng chéo lên một ô hoặc sang phải một ô hoặc chéo dưới một ô. Tức là, nếu học sinh ở ô có tọa độ $(i, j)$ thì có thể bước sang các ô có tọa độ $(i-1, j+1)$ hoặc $(i, j+1)$ hoặc $(i+1, j+1)$.

Biết cách tính điểm khi bước vào ô có tọa độ $(i, j)$ như sau: gọi $a[i,j]$ là giá trị tại ô $(i, j)$. Nếu $a[i,j]$ là số không âm thì tổng điểm của học sinh tăng lên $a[i,j]$, ngược lại nếu $a[i,j]$ là số âm thì tổng điểm của học sinh giảm đi $a[i,j]$ lần. Khi học sinh bước đến một trong các ô ở cột $n$ thì sau khi tính điểm xong sẽ đứng lại, hoàn thành lượt chơi.

Ví dụ:

Với hình chữ nhật bên trên, ta có nhiều cách đi từ cột 1 đến cột 5

• Đi vào từ ô (1,1) => (2,2) => (1,3) => (1,4) => (1,5) thì tổng điểm bằng: $((4 + 3)/3)+6)/2 = 4.167$
• Đi từ vào ô (1,1) => (2,2) => (1,3) => (3,4) -> (3,5) thì tổng điểm bằng: $(4 + 3)/3 + 2 + 1 = 5.3333$

Yêu cầu: Hãy tìm cách đi để có tổng điểm cao nhất.

Vào từ file GIFT.INP gồm nhiều dòng:

• Dòng 1: Ghi hai số nguyên dương $m, n$ là kích thước của lưới ô vuông, $m < 300$, $n < 300$
• $m$ dòng tiếp theo, mỗi dòng ghi $n$ số nguyên $a[i,j]$, với $a[i,j] < 10^5$

Ghi ra file GIFT.OUT tổng điểm cao nhất tìm được làm tròn đến 3 chữ số thập phân.

• $m < 300$, $n < 300$; $a[i,j] < 10^5$.