У вас есть сад, в котором растет трава и сорняки. Ваш сад представляет собой клетчатое поле размером 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)
  

• если вы смотрели направо, вы будете смотреть налево
  

• если вы смотрели налево, вы будете смотреть направо
  

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

Какое наименьшее количество ходов потребуется, чтобы скосить все сорняки?