Рассмотрим коридор, которой может быть представлен как матрица из $$$2$$$ строк и $$$n$$$ столбцов. Определим ячейку на пересечении $$$i$$$-й строки и $$$j$$$-го столбца как $$$(i, j)$$$. Расстояние между ячейками $$$(i_1, j_1)$$$ и $$$(i_2, j_2)$$$ равно $$$|i_1 - i_2| + |j_1 - j_2|$$$.

В клетке $$$(1, 1)$$$ стоит робот-пылесос. Некоторые клетки коридора чистые, остальные — грязные (клетка, в которой стоит робот, чистая). Вы хотите очистить коридор, поэтому вы планируете запустить робота для этой работы.

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

Однако в программе робота есть серьезная ошибка. Если в какой-то момент есть несколько ближайших (к текущей позиции робота) грязных клеток, то робот ломается.

Вы хотите сами очистить коридор так, чтобы робот не сломался. До запуска робота вы можете очистить несколько (возможно, ноль) грязных клеток вручную. Однако вы не хотите делать много грязной работы сами, когда у вас есть такой замечательный, умный (хоть и неправильно запрограммированный) робот, чтобы это делать. Обратите внимание, что вы не можете сделать чистую клетку грязной.

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