National Olympiad in Informatics, China, 1997

In a tourist city, the streets are in the arrangement of a grid (see figure below). The streets that run east-west are known as landscape streets and the streets that run north-south are known as vacant streets. Landscape streets contain many popular attractions that are suitable for sightseeing tourists. Vacant streets do not contain any establishments worthwhile for tourists to visit. Due to the large number of tourists, landscape streets are designated to be one-way, and individuals may only travel from west to east (left to right on the diagram). However, one may travel in any direction they wish on vacant streets.

A tourist would like to tour the city. He has assigned a score to each landscape street section based on the quality of the sights around it. The score of each landscape is an integer from ~-100~ to ~+100~. The more the tourist likes the sights on that street, the higher the score that he assigns. It is not possible for all of the lines to receive negative scores.

The tourist can begin and end the tour at any two intersections in the city. He would like the overall score of the trip to be as large as possible. Please write a program to help him find an optimal tour route.

Input Specification

The first line of input contains two space-separated integers ~M~ and ~N~ ~(1 \le M \le 100, 1 \le N \le 20\,000)~, representing the number of landscape streets and the number of vacant streets respectively. The following ~M~ lines each contain ~N-1~ integers from ~-100~ to ~100~, representing the landscape score that the tourist has assigned to the corresponding landscape street sections, in order from north to south, then from west to east.

Output Specification

The output should contain one line - an integer representing the maximum total score obtainable from an optimal tour route.

Sample Input

3 6
-50 -47 36 -30 -23
17 -19 -34 -13 -8
-42 -3 -43 34 -45

Sample Output

84

Explanation

The best route is: start at the intersection of the west-most vacant street and the second north-most landscape street. Pass through the landscape streets with scores ~17~, ~-3~, ~36~, and ~34~ for a total of ~17-3+36+34 = 84~.

Problem translated to English by Alex.