Задано поле, состоящее из \(2\) строк и \(m\) столбцов. Строки занумерованы от \(1\) до \(2\) сверху вниз. Столбцы занумерована от \(1\) до \(m\) слева направо.
Робот начинает в клетке \((1, 1)\). За одну секунду он может проделать любое из двух действий:
- перейти в соседнюю по стороне клетку: наверх, направо, вниз или налево;
- остаться в той же клетке.
Роботу запрещено выходить за пределы поля.
Изначально все клетки, кроме клетки \((1, 1)\) заблокированы. Каждая клетка \((i, j)\) содержит значение \(a_{i,j}\) — момент, когда данная клетка будет разблокирована. Робот может перейти в клетку \((i, j)\), если до начала хода прошло хотя бы \(a_{i,j}\) секунд.
Робот должен посетить все клетки, не входя ни в какую клетку дважды или больше (считается, что робот вошел в клетку \((1, 1)\) на старте). Он может закончить в любой клетке.
Какое минимальное время у него это может занять?
Выходные данные
На каждый набор входных данных выведите одно целое число — минимальное количество секунд, которые могут потребоваться роботу, чтобы посетить все клетки, не входя ни в какую клетку дважды или больше.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
0 0 1
4 3 2
5
0 4 8 12 16
2 6 10 14 18
4
0 10 10 10
10 10 10 10
2
0 0
0 0
|
5
19
17
3
|