Minimum Relay Baton Passing Cost

You are given a rectangular field with height \(H\) and width \(W\) (in meters). In this field, there are \(N\) robots positioned at specific coordinates. The robots are arranged in an array and are labeled from \(0\) to \(N-1\). The first robot (robot 0) holds a baton and needs to pass it to the last robot (robot \(N-1\)). The baton can be relayed between any two robots, and the cost of passing the baton from one robot to another is the Manhattan distance between their positions. The Manhattan distance between two points \((x_1, y_1)\) and \((x_2, y_2)\) is given by:

[ |x_1 - x_2| + |y_1 - y_2| ]

Your task is to compute the minimum total cost required to pass the baton from the first robot to the last robot. You may pass the baton through intermediate robots if that results in a lower overall cost.

inputFormat

The first line contains three integers \(H\), \(W\), and \(N\) - the height of the field, the width of the field, and the number of robots, respectively. Each of the next \(N\) lines contains two space-separated integers representing the coordinates \(R_i\) and \(C_i\) of the \(i\)-th robot.

You should read the input from standard input (stdin).

outputFormat

Output a single integer representing the minimum total cost to pass the baton from the first robot to the last robot. The answer should be printed to standard output (stdout).

3 3 3
0 0
1 2
2 2

4