eolymp
bolt
Try our new interface for solving problems
Problems

Mushroom hunting (RU)

Mushroom hunting (RU)

Time limit 5 seconds
Memory limit 64 MiB

Однажды летним утром Копатыч отправился в гости к Ёжику. Копатыч подумал, что идти в гости с пустыми руками невежливо, и решил по дороге набрать для своего друга больших вкусных грибов. Для этого он взял бо-о-ольшую корзинку и потопал в лес. Мишка хочет, чтобы каждый следующий гриб был больше по весу, чем предыдущий, ведь так гораздо интереснее. Лес представляет собой прямоугольник размера N*M прыжков Кроша (пК). На каждом квадратном пК растёт ровно один гриб. Копатыч хочет собрать как можно больше грибов, при этом не возвращаясь назад (ведь он идёт к Ёжику!), то есть каждый следующий сорванный Копатычем гриб должен находиться южнее и восточнее предыдущего. Копатыч может начать и прекратить сбор грибов, находясь в любом месте леса, после чего он направляется к Ёжику. Какое максимальное количество грибов получит Ёжик в подарок.

Input data

На первой строке два натуральных числа N и M (N,M500) – длина и ширина леса в прыжках Кроша (пК). На каждой из последующих N строк записано по M чисел – вес гриба в граммах на соответствующей поляне. Вес каждого гриба не превышает 1000 граммов.

Output data

Выходной файл должен содержать одно число - максимальное количество грибов, которые получит Ежик от Копатыча.

Examples

Input example #1
3 4
1 6 8 2
3 4 5 3
1 1 3 2
Output example #1
2