Похід по гриби
Одного літнього ранку Копатич відправився в гості до Їжачка. Копатич подумав, що йти в гості з пустими руками неввічливо, і вирішив по дорозі назбирати для свого друга великих смачних грибів. Для цього він взяв ве-е-елику корзинку і пішов у ліс. Копатич хоче, щоб кожен наступний гриб був більшим за вагою, ніж попередній, адже так набагато цікавіше. Ліс являє собою прямокутник розміром N*M стрибків Кроша (сК). На кожному квадратному сК росте рівно один гриб. Копатич хоче зібрати якомога більше грибів, при цьому не повертаючись назад (адже він іде до Їжачка!), тобто кожен наступний зірваний Копатичем гриб повинен знаходитись південніше і східніше попереднього. Копатич може почати і завершити збір грибів, знаходячись у довільному місці лісу, після чого він направляється до Їжачка. Яку максимальну кількість грибів отримає Їжачок в подарунок?
Вхідні дані
У першому рядку задано два натуральних числа N та M (N,M ≤ 500) – довжина і ширина лісу в стрибках Кроша (сК). У кожному з наступних N рядків записано по M чисел – вага гриба в грамах на відповідній поляні. Вага кожного гриба не перевищує 1000 грамів.
Вихідні дані
Вихідний файл повинен містити єдине число - максимальну кількість грибів, які отримає Їжачок від Копатича.