Mushroom Foraging
One summer morning, Kopatych decided to visit Hedgehog. Not wanting to arrive empty-handed, he planned to gather some large, delicious mushrooms for his friend along the way. To accomplish this, he took a very large basket and ventured into the forest. Kopatych's goal is to collect mushrooms in such a way that each one is heavier than the last, as he finds this more exciting. The forest is a rectangular area measuring N by M Krosh's jumps (cK). There is exactly one mushroom growing on each square of this grid. Kopatych aims to collect as many mushrooms as possible without retracing his steps (since he is on his way to Hedgehog!). This means that each subsequent mushroom he picks must be located further south and further east than the previous one. Kopatych can begin and end his mushroom collection from any point in the forest, after which he will proceed to Hedgehog. What is the maximum number of mushrooms that Hedgehog will receive as a gift?
Input
The first line contains two natural numbers N and M (N, M ≤ 500) — representing the length and width of the forest in Krosh's jumps (cK). Each of the following N lines contains M numbers, indicating the weight of the mushroom in grams at each corresponding clearing. The weight of each mushroom does not exceed 1000 grams.
Output
The output should be a single number — the maximum number of mushrooms that Hedgehog will receive from Kopatych.