Побочной диагональю квадратной матрицы называется диагональ, проходящая из правого верхнего угла матрицы в левый нижний угол. Назовем лесенкой порядка n квадратную матрицу n × n без клеток выше побочной диагонали (ниже на рисунке изображена лесенка пятого порядка).

В клетках лесенки порядка n стоят m спортсменов.

За секунду спортсмен может перейти на соседнюю по стороне клетку лесенки. Перед началом соревнования каждый спортсмен должен выбрать один из кратчайших путей до побочной диагонали.

После стартового свистка соревнование начинается, и все спортсмены начинают двигаться по выбранным путям. Когда спортсмен достигает клетки побочной диагонали, он останавливается и больше не двигается. Соревнование заканчивается, когда все спортсмены доходят до побочной диагонали. Соревнование считается успешным, если в процессе соревнования никакие два спортсмена не оказались одновременно в одной клетке (в том числе в одной клетке побочной диагонали не может остановиться более одного спортсмена). Если один спортсмен в данный момент времени уходит из клетки, а другой приходит в нее, то считается, что они не оказались в одной клетке одновременно. Заметим, что другие крайние случаи (например, если спортсмены идут навстречу друг другу) исключаются, так как выбранные пути кратчайшие.

Даны позиции m спортсменов на лесенке. Требуется выбрать из них наибольшее количество спортсменов (все невыбранные спортсмены удаляются из клеток лесенки до начала движения), так чтобы для них соревнование могло бы быть успешным (то есть существовал такой выбор кратчайших путей для спортсменов, при котором в процессе соревнования никакие два спортсмена не оказались бы одновременно в одной клетке).