Сережа пошел с Марго в магазин «Хмурогруз», который можно представить как матрицу из \(n\) рядов и \(m\) столбцов.
За \(1\) единицу энергии Сережа и Марго могут перейти в соседнюю по стороне клетку. Для ускорения процесса Марго захватила с собой порталы, и в каждой клетке, через которую она проходит, она оставляет один портал (если его там еще нет). Если кто-либо (Сережа или Марго) находится в клетке с порталом, то за \(1\) единицу энергии он может телепортироваться в любую другую клетку с порталом, включая ту, из которой Марго начала.
Они решили разделиться: Сереже надо попасть из верхней левой клетки (клетка с координатами \((1, 1)\)) в нижнюю правую (клетка с координатами \((n, m)\)), а Марго из нижней левой (клетка с координатами \((n, 1)\)) в верхнюю правую (клетка с координатами \((1, m)\)).
За какое минимальное суммарное количество энергии у них это получится сделать?
Обратите внимание, что они могут выбирать время для своих движений. Время не влияет на энергию.
Примечание
В первом наборе входных данных они могут придерживаться следующего плана:
- Марго (красный кружок) идет в клетку \((7, 3)\). Затем она направляется в клетку \((1, 3)\), и Сережа (синий кружок) тоже идет туда.
- Сережа пользуется порталом в этой клетке (клетки с порталами отмечены серым) и попадает в клетку \((7, 3)\). Затем он идет в свой пункт назначения — клетку \((7, 5)\).
- Марго также направляется к концу своего маршрута и попадает в клетку \((1, 5)\).
Суммарная затраченная энергия \((2 + 6) + (2 + 1 + 2) + (2)= 15\), что является ответом.