B - 格子グラフ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

H 行 W 列の格子グラフがあります。 このグラフは、頂点が縦に H 行、横に W 列等間隔に並んでいて、上下左右に隣り合う頂点の間のみ辺が張られています。 くじら君はこのグラフの辺に色を塗って遊ぼうと思っていたのですが、N 個の頂点には、誰のいたずらか 'x' マークが描かれていました。 i 番目の 'x' マークは (r_i, c_i) に書かれています。ただし (a,b) は格子グラフの a 行 b 列目の頂点を表し、左上の頂点を (1,1), 右下の頂点を (H,W) とします。 なんだか気味が悪いので、くじら君は 'x' マークが描かれていない頂点どうしを結ぶ辺だけに色を塗ることにしました。

くじら君は自分が塗ることのできる辺すべてに色を塗ります。 このとき、くじら君が色を塗る辺の本数はいくつでしょうか？

なお、出力は32bit型整数に収まらないことがあります。

制約

  • 入力は全て整数である。
  • 1≦H, W≦10^5
  • 0≦N≦10^3
  • 1≦r_i≦H
  • 1≦c_i≦W
  • 入力に同じ位置の頂点が複数与えられることはない。すなわち、すべての i,j (1≦i<j≦N) に対し、r_i ≠ r_j または c_i ≠ c_j が成り立つ。

入力

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

H W N
r_1 c_1
r_2 c_2
:
r_N c_N

1 行目には、格子グラフの行数 H, 列数 W, 'x' マークが描かれた頂点の個数 N がスペース区切りの整数で与えられる。

N≥1 のとき、2 行目から N+1 行目の各行には、'x' マークが描かれた頂点の位置に関する情報がスペース区切りの整数で与えられる。r_i,c_i(1≤i≤N,1≤r_i≤H,1≤c_i≤W) は、r_i 行 c_i 列目の頂点に 'x' マークが描かれていることを表す。

出力

くじら君が色を塗る辺の本数を出力せよ。

入力例 1

3 4 4
1 4
2 2
2 4
3 1

出力例 1

7

図1: 入力例1

入力例 2

1 5 2
1 2
1 4

出力例 2

0

図2: 入力例2

入力例 3

100000 100000 0

出力例 3

19999800000