End-to-End
НОИ 2020, Контрола 1
Time Limit: 2s, Memory Limit: 64MiB
Ели има матрица от цифри с N реда и M колони. Във всяка клетка има точно една цифра между 0 и 9, включително.

Момичето може да променя матрицата, като сменя цифрите в различни клетки (потенциално нито една или пък всичките). Смяната на цифра X с цифра Y ѝ отнема |X-Y| секунди (тоест, абсолютната разлика между цифрите).

Ели казва, че е "свързала двата края" на матрицата (горния с долния или левия с десния) ако между тях има път от съседни (имащи обща стена) клетки съдържащи една и съща цифра. Момичето иска да свърже както горния с долния, така и левия с десния край на матрицата. Забележете, че за да постигне това, тя трябва да ползва една и съща цифра, тъй като пътищата се пресичат.

Нека разгледаме следния пример:
2753852
9567342
5294979
3180559
2753852
8888842
5284888
3180559
2753852
9333333
5394979
3380559
2753852
7777342
5297777
3180579
Началната матрица на момичето има четири реда и седем колони. Ето един начин, по който можем да постигнем целта за 16 секунди. Друг начин е следният, постигайки целта за 14 секунди, ползвайки 3-ки. Трети начин да постигнем целта, отново за 14 секунди, този път със 7-ци.

По дадена началната матрица на Ели, можете ли да определите минималното време, за което тя може да свърже краищата ѝ?
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и M. На всеки от следващите N реда ще има по един стринг съставен от M цифри.
Изход
На единствен ред на стандартния изход изведете едно цяло число – минималния брой секунди, достатъчен да се промени матрицата по желания начин.
Ограничения
  • 1 ≤ N, M ≤ 500
Примерен Вход Примерен Изход
4 7 2753852 9567342 5294979 3180559 14
Мрън!