题目内容

塔子哥是一名冒险家，经过了漫长的旅途，他终于到达了传说中的神秘迷宫。在迷宫里，塔子哥发现了一张 $n$ 行 $m$ 列的二维矩阵，矩阵的每个元素都代表着一个位置，同时每个位置还对应着一个花费值。这个花费值代表着从当前位置走到下一个位置需要消耗的时间。塔子哥站在矩阵的左上角，他每一步可以走上、下、左、右四种方向中的一个，花费的时间为这两个相邻元素的差的绝对值。

此时，塔子哥已经花费了很多时间在迷宫中行走，而他又发现了一件奇怪的事情，就是在这个迷宫中存在传送阵。这个传送阵可以让他瞬间从一个位置传送到另一个位置，而且不会消耗任何时间。不过这个传送阵有两个个限制，这个传送阵只能使用一次，并且只能从一个数字到达另一个相同的数字。这就意味着，如果他想要使用这个传送阵，他需要在同一个数字出现两次之后，才能将这个数字作为传送阵的起点或终点。

为了尽快走出这个迷宫，塔子哥想知道，从左上角走到右下角最少需要多少时间。

输入描述

第一行输入两个正整数 $n$ 和 $m$ 。代表矩阵的行和列。

接下来的 $n$ 行，每行输入 $m$ 个正整数 $a_{ij}$ ，代表矩阵的元素

$1\leq n,m \leq 500$

$1\leq a_{ij} \leq 10^9$

输出描述

一个整数，代表最少需要花费的时间。

样例$1$

输入

3 3
1 3 5
2 1 4
2 5 6

输出

5