题目描述

一名快递员要在 $N\times M$ 的网格地图上依次送达 $K$ 个取件点。他每一步可以走到上、下、左、右相邻的格子，也可以走到右下或左上的斜对角格子，但不能走出地图。也就是说，从 $(x,y)$ 出发，一步可以到达 $(x+1,y)$、$(x-1,y)$、$(x,y+1)$、$(x,y-1)$、$(x+1,y+1)$、$(x-1,y-1)$ 中仍在地图内的格子。

他按给定顺序依次经过这 $K$ 个取件点，起点就是第 $1$ 个点，同一个点可以经过多次。请计算到达最后一个点所需的最少总步数。

输入格式

第一行三个正整数 $N$、$M$、$K$，表示地图的大小和取件点的数量。

接下来 $K$ 行，每行两个整数 $X_i$、$Y_i$，表示第 $i$ 个取件点的坐标。

输出格式

输出一个整数，表示按顺序经过所有取件点的最少步数。

样例

5 4 3
1 1
2 3
5 4

5

6 6 4
2 2
5 3
5 3
1 6

10

1 5 2
1 1
1 5

4

样例解释

样例 1 中，第 1 段横纵变化方向相同，走 2 步；第 2 段同向，走 3 步，共 $5$ 步。

样例 2 中，三段最少步数分别为 $3,0,7$，共 $10$ 步。

样例 3 中只有一条横线，走 $4$ 步。

数据范围与约定

对于 $100\%$ 的数据，$1\le N,M\le 10^9$，$1\le K\le 10^6$，$1\le X_i\le N$，$1\le Y_i\le M$。