Ваня оказался во дворце, который можно представить как таблицу из комнат размера n × m. В каждой комнате находится ровно один сундук, при этом в комнате в i-м ряду и j-м столбце находится сундук вида aij. При этом в каждом сундуке типа x ≤ p - 1 находится ключ, открывающий любой сундук типа x + 1, а все сундуки типа 1 не заперты. Сундук типа p ровно один, и в нём находится сокровище.
Ваня начинает в клетке (1, 1) (верхний левый угол). Какое минимальное расстояние ему нужно пройти, чтобы получить сокровище? Считается, что расстояние между двумя клетками (r1, c1) (то есть клетки в строке r1 и столбце c1) и (r2, c2) равно |r1 - r2| + |c1 - c2|.
Выходные данные
Выведите единственное целое число — минимальное расстояние, которое потребуется преодолеть Ване, чтобы забрать сокровище из сундука типа p.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4 3
2 1 1 1
1 1 1 1
2 1 1 3
|
5
|
|
2
|
3 3 9
1 3 5
8 9 7
4 6 2
|
22
|
|
3
|
3 4 12
1 2 3 4
8 7 6 5
9 10 11 12
|
11
|