[ARC063F] すぬけ君の塗り絵 2

平面上有一个左下角坐标 $(0,0)$ 右上角坐标 $(W,H)$ 的矩形，起初长方形内部被涂白。 现在给定 $n$ 个点，你每次在以下 $4$ 种操作中选择一种： - 将矩形内 $x<x_i$ 的区域涂黑 - 将矩形内 $x>x_i$ 的区域涂黑 - 将矩形内 $y<y_i$ 的区域涂黑 - 将矩形内 $y>y_i$ 的区域涂黑 现在你需要最大化操作后白色矩阵周长。

[problemUrl]: https://atcoder.jp/contests/arc063/tasks/arc063_d $ xy $ 平面上に、左下の頂点の座標が $ (0,\ 0) $、右上の頂点の座標が $ (W,\ H) $ で、各辺が $ x $ 軸か $ y $ 軸に平行な長方形があります。最初、長方形の内部は白く塗られています。 すぬけ君はこの長方形の中に $ N $ 個の点を打ちました。$ i $ 個目 ($ 1\ ≦\ i\ ≦\ N $) の点の座標は $ (x_i,\ y_i) $ でした。 すぬけ君は各 $ 1\ ≦\ i\ ≦\ N $ に対し、長方形の - $ x\ をみたす領域 $ - $ x\ >\ x_i $ をみたす領域 - $ y\ をみたす領域 $ - $ y\ >\ y_i $ をみたす領域 の $ 4 $ つの中から $ 1 $ つを選び、その領域を黒く塗ります。 塗りつぶしが終わったあとに残る白い長方形の周長を最大化するように塗る領域を選ぶとき、その最大の周長を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ W $ $ H $ $ N $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ : $ $ x_N $ $ y_N $

塗りつぶしが終わったあとに残る白い長方形の周長の最大値を出力せよ。

10 10 4
1 6
4 1
6 9
9 4

32

5 4 5
0 0
1 1
2 2
4 3
5 4

12

100 100 8
19 33
8 10
52 18
94 2
81 36
88 95
67 83
20 71

270

100000000 100000000 1
3 4

399999994

### 制約 - $ 1\ ≦\ W,\ H\ ≦\ 10^8 $ - $ 1\ ≦\ N\ ≦\ 3\ \times\ 10^5 $ - $ 0\ ≦\ x_i\ ≦\ W $ ($ 1\ ≦\ i\ ≦\ N $) - $ 0\ ≦\ y_i\ ≦\ H $ ($ 1\ ≦\ i\ ≦\ N $) - $ W $, $ H $ (21:32 追記), $ x_i $, $ y_i $ は整数である - $ i\ ≠\ j $ ならば $ x_i\ ≠\ x_j $ かつ $ y_i\ ≠\ y_j $ である ### Sample Explanation 1 このケースでは、すぬけ君は以下の図のように長方形を塗りつぶすと残った白い長方形の周長が $ 32 $ となり、これが最大値である。 !\[842bb3939c9721d978d4e122b0bfff55.png\](https://atcoder.jp/img/arc063/842bb3939c9721d978d4e122b0bfff55.png)