Mushroom Foraging#211
One summer morning, a farmer set out to visit his friend. Believing it impolite to arrive empty-handed, he decided to gather some large, delicious mushrooms for his friend along the way. To do this, the farmer took a large basket and walked into the forest. The farmer wants each mushroom he picks to be heavier than the previous one, as this is more interesting to him.
The forest is a rectangle of size N \times M meters. There is exactly one mushroom growing in each square of the grid. The farmer wants to collect as many mushrooms as possible without retracing his path (as he is on his way to his friend!). This means that each mushroom he picks must be located strictly south and strictly east of the previous one. The farmer may start and end his mushroom collection at any location in the forest, after which he sets off to his friend. What is the maximum number of mushrooms the friend can receive as a gift?
The first line contains two natural numbers and (1 \leq N, M \leq 500) — the length and width of the forest in meters. Each of the next lines contains numbers — the weight in grams of the mushroom at the corresponding square. The weight of each mushroom does not exceed grams.
Output a single number — the maximum number of mushrooms that the friend can receive from the farmer.
Example 1