У вас есть сад, в котором растет трава и сорняки. Ваш сад представляет собой клетчатое поле размером n × m. Строки пронумерованы от 1 до n сверху вниз, а столбцы — от 1 до m слева направо. Каждая клетка обозначается парой (r, c), где r — номер строки, в которой расположены клетка, а c — номер столбца. Каждая клетка содержит либо траву, либо сорняк. Например, сад размера 4 × 5 может выглядеть следующим образом (пустые клетки обозначают траву):
У вас есть газонокосилка, и вы хотите скосить все сорняки. Изначально вы и ваша газонокосилка находитесь в левом верхнем углу сада, то есть в клетке (1, 1). В каждый момент времени вы смотрите либо направо, либо налево. Изначально вы смотрите направо.
За один ход вы можете сделать одно из двух:
1) Пойти на одну клетку в ту сторону, куда вы смотрите.
- если вы смотрите направо: пойти из клетки (r, c) в клетку (r, c + 1)
- если вы смотрите налево: пойти из клетки (r, c) в клетку (r, c - 1)
2) Пойти на одну клетку вниз (то есть из клетки
(r, c) в клетку
(r + 1, c)) и развернуться в другую сторону.
- если вы смотрели направо, вы будете смотреть налево
- если вы смотрели налево, вы будете смотреть направо
Вы не можете выходить за пределы поля. Чтобы скосить сорняк, вы должны оказаться в одной клетке с ним (при этом не имеет значения, в какую сторону вы смотрите). На это действие ход не тратится.
Какое наименьшее количество ходов потребуется, чтобы скосить все сорняки?
Выходные данные
Выведите одно целое число — минимальное количество ходов, которое требуется, чтобы скосить все сорняки.