AT_arc219_g [ARC219G] Traveling Door-to-Door Salesman (Stairs)

**Note: This problem has almost the same setting as Problem C. The differences in the problem statements are shown in red bold.** There is an underground apartment represented by a grid with $ H $ rows and $ W $ columns. The cell at the $ i $ -th row from the top and the $ j $ -th column from the left is denoted as cell $ (i,j) $ . The entrance to the underground apartment is at cell $ (1,1) $ . The underground apartment has $ N $ doors. The $ k $ -th door is located at cell $ (A_k, B_k) $ . Inside the underground apartment, a salesman can perform the following two types of moves any number of times, in any order: - He can walk to a horizontally adjacent cell (left or right) from his current cell. The cost of this move is $ 1 $ . - If his current cell is in column $ 1 $ or column $ W $ , he can move to a vertically adjacent cell (up or down) **by stairs**. The cost of this move is **$ \mathbf{1} $** . His goal is to start from cell $ (1,1) $ , repeat moves, visit all $ N $ cells with doors at least once, and then arrive at cell $ (1,1) $ . Find the minimum total cost needed to achieve his goal.

The input is given from Standard Input in the following format: > $ H $ $ W $ $ N $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_N $ $ B_N $

Output the answer on a single line.

### Sample Explanation 1 By moving as follows, the goal can be achieved with a total cost of $ 28 $ : - Start from cell $ (1,1) $ . - Move $ 1 $ cell down and $ 1 $ cell right from cell $ (1,1) $ to visit cell $ (2,2) $ (cost $ 2 $ ). - Move $ 1 $ cell left and $ 1 $ cell down from cell $ (2,2) $ to visit cell $ (3,1) $ (cost $ 2 $ ). - Move $ 3 $ cells down and $ 2 $ cells right from cell $ (3,1) $ to visit cell $ (6,3) $ (cost $ 5 $ ). - Move $ 1 $ cell right from cell $ (6,3) $ to visit cell $ (6,4) $ (cost $ 1 $ ). - Move $ 2 $ cells right from cell $ (6,4) $ to visit cell $ (6,6) $ (cost $ 2 $ ). - Move $ 2 $ cells right, $ 4 $ cells up, and $ 1 $ cell left from cell $ (6,6) $ to visit cell $ (2,7) $ (cost $ 7 $ ). - Move $ 1 $ cell right, $ 1 $ cell up, and $ 4 $ cells left from cell $ (2,7) $ to visit cell $ (1,4) $ (cost $ 6 $ ). - Move $ 3 $ cells left from cell $ (1,4) $ to arrive at cell $ (1,1) $ (cost $ 3 $ ). ### Constraints - $ 1 \leq H \leq 10^9 $ - $ 2 \leq W \leq 10^9 $ - $ 1 \leq N \leq 3 \times 10^5 $ - $ 1 \leq A_k \leq H $ - $ 1 \leq B_k \leq W $ - $ (A_1, B_1), \dots, (A_N, B_N) $ are distinct. - All input values are integers.