School
Petro Pyatochkin is a student who used to take the trolleybus to school. However, after a fare increase, he found it quicker and more convenient to walk. Petro lives in the city of Ideal, which is laid out as a rectangle of m×n blocks, each block being a perfect square. The city's boundary doesn't follow the edges of the blocks but instead cuts through them, either halving them or slicing off quarter blocks at the corners, as shown in Fig. 1.
Fig. 1. Diagram of the city of Ideal. The city boundaries are marked with a thick black line.
Petro starts his journey from the southernmost and easternmost corner of the city blocks and heads to the northernmost and westernmost corner, where his school is located. These starting and ending points are marked with bold dots in Fig. 1. Petro can only walk along the boundaries of the blocks (since the blocks themselves are built up) and can move from one block vertex to the next only perpendicularly to the street direction, parallel to the city boundaries. At each intersection, the time t for horizontal (east-west) and vertical (north-south) movement is specified. Each traffic light operates in cycles: for the first t seconds, horizontal movement is allowed and vertical movement is prohibited; for the next t seconds, vertical movement is allowed and horizontal is prohibited; from the (2t+1)-th second to the 3t-th second, horizontal movement is allowed again, and so on. Note that the value of t can vary at different intersections. Petro can walk one block side in a minute and cross the street in a second when the traffic lights permit. He avoids crossing on a red light or stepping outside the city limits for safety reasons.
Your task is to help Petro find the shortest time it will take him to reach school. When Petro leaves home, all traffic lights are initially set to allow horizontal movement.
Input
The first line contains the natural numbers m and n, representing the city's width and height. These numbers do not exceed 250.
Following this, there are n rows. For i and j such that 1 ≤ i ≤ n, 1 ≤ j ≤ m, the j-th number of the (i+1)-th row indicates the duration of movement at the corresponding intersection. This number is a natural number not exceeding 500. Each row lists intersections from the westernmost to the easternmost, with the first row describing the northernmost intersections and the last row describing the southernmost.
Output
Output the shortest time interval (in seconds) that Petro needs to reach school.
Explanation of the example
Petro can reach school in 187 seconds: he leaves home and immediately crosses the road horizontally; waits 2 seconds for the traffic light to allow vertical movement, then crosses north; reaches the opposite corner of the block in 120 seconds and, since the traffic light allows horizontal movement, immediately crosses the street and continues east to the next intersection. He manages to cross vertically in the last second allowed by the traffic light, then crosses the road one final time to reach the school. Petro's path is marked on the diagram. The number in the block corner on the diagram indicates the seconds Petro needs to reach that corner.
It's clear that Petro cannot reach school faster than 187 seconds. If he didn't have to wait for the green light at all, he could reach school in at least 185 seconds (walking along the blocks three times and crossing the street five times). However, before he first crosses north — regardless of how many blocks he walks east — he must wait at least 2 seconds.
Fig. 2. One of the optimal paths for Petro to school for the given example input data.