Buffalo's Giant Meal Journey

In a special period, Li Dashaoniu (the Buffalo) is starving because of his well-developed digestive system. One day during class, when he is extremely hungry, he suddenly sees a gigantic dining table in the form of an \(n \times m\) grid (with \(n, m \le 200\)). The table is divided into \(n \times m\) small squares, and each square holds a gigantic round plate full of food that Li Dashaoniu adores (some of which even have negative energy because they might upset his stomach).

Positioned just below the midpoint of the bottom side of the table, he decides to start his meal journey from that location and make his way to the opposite side of the table. However, he has a peculiar eating habit: from any current plate, he will only proceed to the plate directly in front of him, or the one to the left-front, or the one to the right-front.

Your task is to help him obtain the maximum total energy. Note that the starting point for each test case is fixed: it is located just below the middle cell of the last row (i.e. the bottom row's middle plate).

The allowed moves from a cell at position \((i,j)\) are to \((i-1, j-1)\), \((i-1, j)\), or \((i-1, j+1)\) provided that the indices are within the table boundaries. The energy obtained is the sum of the energy values on the plates visited along the path. The goal is to choose a path from the starting plate to any plate in the first row that maximizes the total energy obtained.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(n, m \le 200\)). Each of the next \(n\) lines contains \(m\) integers. The \(j\)-th integer on the \(i\)-th line represents the energy value of the plate at the cell \((i, j)\) (some may be negative).

Note: The starting point is fixed at the middle cell of the last row.

outputFormat

Output a single integer: the maximum total energy that can be obtained by following the allowed moves from the starting plate (bottom row, middle cell) to any plate in the first row.

sample

3 3
1 2 3
-1 -2 -3
4 5 6

6