Город N, в отличие от города M, расположен на склоне одного холма. Чистоту улиц этого города обеспечивает единственная поливальная машина. Бензин нынче дорог, поэтому движение муниципального транспорта «в гору» признано слишком расточительным.

Карта города представляет собой прямоугольник, разбитый на H × W клеток, где H и W — высота и ширина карты в клетках соответственно. Часть клеток заняты зданиями, остальные соответствуют улицам и площадям, которые и требуется помыть.

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

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