Tourism

Interview

Time limit1sMemory limit128 MB

Summary

Visit the given sights in order on a grid with extra northeast diagonals and minimize the total number of road segments traveled.

Level: Medium4 of 10
Topics: Shortest path, Math
Solved: No attempts yet

Problem

A city has a $W \times H$ grid of roads plus northeast diagonal moves (except on the north/east border). Visit $N$ sights in order starting at the first. Minimize the number of road segments traveled, counting repeats.

Input

Line 1: $W$ , $H$ , $N$ . Next $N$ lines: coordinates $(X_i, Y_i)$ .

Output

Print the minimum number of road segments.

Examples1

Example 1
Input
```
4 3 3
1 1
3 3
4 1
```
Expected output
```
5
```