original problem
(http://codeforces.net/contest/366/problem/E)
Here we have the complexity of a way to play a song is defined as the maximum of complexities of moving between adjacent pairs of the sequence. so we can redefine it as the maximum mxDIS(s[i], s[i+1]) for each i (0 <= i < n-1) where mxDIS(n, m) is the maximum (|x1-x2| + |y1-y2|) among all cells in which a[x1][y1] = n and a[x2][y2] = m.

I've already solved the original problem and now my question is:
How can we solve the problem if the complexity of a way to play a song is defined as the sum of complexities of moving between adjacent pairs? For example, the input: 3 3 3 3
1 2 3
1 2 3
1 2 3
2 1 3
should print the answer 7.
Explanation: we will start at cell (1, 2) and move to cell (3, 1) with complexity of 3(|1-3| + |2-1|) then to cell (1, 3) with complexity of 4(|3-1| + |1-3|) so the final answer is 4 + 3 = 7.
any help would be appreciated :D and thanks in advance.