配点 : $1600$ 点

問題文

$xy$ 平面上に、左下の頂点の座標が $(0, 0)$、右上の頂点の座標が $(W, H)$ で、各辺が $x$ 軸か $y$ 軸に平行な長方形があります。最初、長方形の内部は白く塗られています。

すぬけ君はこの長方形の中に $N$ 個の点を打ちました。$i$ 個目 ($1 \leq i \leq N$) の点の座標は $(x_i, y_i)$ でした。

すぬけ君は各 $1 \leq i \leq N$ に対し、長方形の

• $x < x_i$ をみたす領域
• $x > x_i$ をみたす領域
• $y < y_i$ をみたす領域
• $y > y_i$ をみたす領域

の $4$ つの中から $1$ つを選び、その領域を黒く塗ります。

塗りつぶしが終わったあとに残る白い長方形の周長を最大化するように塗る領域を選ぶとき、その最大の周長を求めてください。

制約

• $1 \leq W, H \leq 10^8$
• $1 \leq N \leq 3 \times 10^5$
• $0 \leq x_i \leq W$ ($1 \leq i \leq N$)
• $0 \leq y_i \leq H$ ($1 \leq i \leq N$)
• $W$, $H$ (21:32 追記), $x_i$, $y_i$ は整数である
• $i \neq j$ ならば $x_i \neq x_j$ かつ $y_i \neq y_j$ である

入力

入力は以下の形式で標準入力から与えられる。

$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

このケースでは、すぬけ君は以下の図のように長方形を塗りつぶすと残った白い長方形の周長が $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