Vanya 所在的宫殿可以表示为 n × m 的网格。每个房间包含一个箱子,位于第 i 行第 j 列的房间包含 aij 类型的箱子。每个 x ≤ p - 1 类型的箱子都包含一把钥匙,可以打开任何 x + 1 类型的箱子,并且所有类型 1 的箱子都没有上锁。 p型箱子只有一个,里面有宝藏。
Vanya 从单元格 (1, 1)(左上角)开始。为了得到宝藏,Vanya 必须步行的最短总距离是多少?考虑单元格 (r1, c1)(r1 行和 c1 列中的单元格)和 (r2, c2) 之间的距离等于 |r1 - r2| + |c1 - c2|。
输入
输入的第一行包含三个整数 n、m 和 p (1 ≤ n, m ≤ 300, 1 ≤ p ≤ n·m)——分别代表宫殿的行数和列数以及不同类型箱子的数量。
以下 n 行每行包含 m 个整数 aij (1 ≤ aij ≤ p)——对应房间中箱子的类型。保证对于从1到p的每个x,至少有一个这种类型的箱子(即,存在一对r和c,使得arc = x)。另外,还保证只有一个 p 类型的箱子。
输出
打印一个整数 - Vanya 为了从 p 类型的箱子中取出宝藏而必须行走的最小可能总距离。
示例
输入 #1
3 4 3 2 1 1 1 1 1 1 1 2 1 1 3
输出 #1
5
输入 #2
3 3 9 1 3 5 8 9 7 4 6 2
输出 #2
22
输入 #3
3 4 12 1 2 3 4 8 7 6 5 9 10 11 12
输出 #3
11