P3431 [POI 2005] AUT-The Bus

The streets of Byte City form a regular, chessboardlike network - they are either north-south or west-east directed. We shall call them NS- and WE-streets. Furthermore, each street crosses the whole city. Every NS-street intersects every WE- one and vice versa. The NS-streets are numbered from $1$ to $n$, starting from the westernmost. The WE-streets are numbered from $1$ to $m$, beginning with the southernmost. Each intersection of the $i$'th NS-street with the $j$'th WE-street is denoted by a pair of numbers $(i,j)$ (for $1\le i\le n$, $1\le j\le m$). There is a bus line in Byte City, with intersections serving as bus stops. The bus begins its itinerary by the $(1,1)$ intersection, and finishes by the $(n,m)$ intersection. Moreover, the bus may only travel in the eastern and/or northern direction. There are passengers awaiting the bus by some of the intersections. The bus driver wants to choose his route in a way that allows him to take as many of them as possible. (We shall make an assumption that the interior of the bus is spacious enough to take all of the awaiting passengers, regardless of the route chosen.)TaskWrite a programme which: reads from the standard input a description of the road network and the number of passengers waiting at each intersection,finds, how many passengers the bus can take at the most,writes the outcome to the standard output.

无

无