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

**注：この問題は C 問題とほとんど同じ設定です。問題文中の相違点を赤い太字で示します。** $ H $ 行 $ W $ 列のグリッドで表される地下アパートがあります。上から $ i $ 行目・左から $ j $ 列目のマスをマス $ (i,j) $ と表記します。 地下アパートの出入り口はマス $ (1,1) $ にあります。 地下アパートにはドアが $ N $ 個あります。 $ k $ 個目のドアはマス $ (A_k, B_k) $ にあります。 地下アパート内で、セールスマンは以下の $ 2 $ 種類の移動を好きな順番で何回でも行えます。 - 現在いるマスから左か右に隣接するマスに徒歩で移動できる。この移動はコストを $ 1 $ 消費する。 - 現在いるマスが $ 1 $ 列目または $ W $ 列目の場合、そこから上か下に隣接するマスに**階段で**移動できる。この移動はコストを **$ \mathbf{1} $** 消費する。 セールスマンの目標は、マス $ (1,1) $ から出発して移動を繰り返し、ドアのある $ N $ 個のマスすべてを $ 1 $ 回以上訪問してからマス $ (1,1) $ に到着することです。 セールスマンが目標を達成するために消費する総コストの最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ N $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_N $ $ B_N $

答えを $ 1 $ 行に出力せよ。

### Sample Explanation 1 以下のように移動することで、総コスト $ 28 $ で目標を達成できます。 - マス $ (1,1) $ から出発する。 - マス $ (1,1) $ から下に $ 1 $ マス、右に $ 1 $ マス移動し、マス $ (2,2) $ を訪れる(コスト $ 2 $ )。 - マス $ (2,2) $ から左に $ 1 $ マス、下に $ 1 $ マス移動し、マス $ (3,1) $ を訪れる(コスト $ 2 $ )。 - マス $ (3,1) $ から下に $ 3 $ マス、右に $ 2 $ マス移動し、マス $ (6,3) $ を訪れる(コスト $ 5 $ )。 - マス $ (6,3) $ から右に $ 1 $ マス移動し、マス $ (6,4) $ を訪れる(コスト $ 1 $ )。 - マス $ (6,4) $ から右に $ 2 $ マス移動し、マス $ (6,6) $ を訪れる(コスト $ 2 $ )。 - マス $ (6,6) $ から右に $ 2 $ マス、上に $ 4 $ マス、左に $ 1 $ マス移動し、マス $ (2,7) $ を訪れる(コスト $ 7 $ )。 - マス $ (2,7) $ から右に $ 1 $ マス、上に $ 1 $ マス、左に $ 4 $ マス移動し、マス $ (1,4) $ を訪れる(コスト $ 6 $ )。 - マス $ (1,4) $ から左に $ 3 $ マス移動し、マス $ (1,1) $ に到着する(コスト $ 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) $ は相異なる - 入力される値はすべて整数