問題文

縦 H 行、横 W 列のマス目があります。 上から i 行目、左から j 列目のマスをマス (i,j) と呼ぶことにします。

それぞれのマスには、1 つの駒が置いてあります。 ショウさんは、このうち K 個の駒をマス目上から取り除きました。 i 番目の取り除いた駒は、マス (R_i,C_i) にあった駒です。

今からショウさんは、次の操作を 0 回以上行います。

• 駒を 1 つ選び、その駒が現在置かれているマスから、隣接する別のマスへと移動させる。 このとき、移動先のマスに別の駒があっても構わない。 なお、2 つのマスが隣接するとは、2 つのマスが辺を共有することを意味する。

ショウさんの目的は、マス目上のすべての駒が同じマスに置いてあるようにすることです。 ショウさんが目的を達成するために必要な最小の操作回数を求めてください。

制約

• 1 \leq H \leq 10^5
• 1 \leq W \leq 10^5
• 0 \leq K \leq \min(10^5,H \times W -1)
• 1\leq R_i \leq H
• 1\leq C_i \leq W
• (R_i,C_i) \neq (R_j,C_j) (i\neq j)
• 入力される値はすべて整数である。

入力例 1

2 3 3
1 2
2 1
2 2

出力例 1

3

操作を行う前の段階で駒が置かれているマスは、マス (1,1), (1,3), (2,3) の 3 つです。 次のように 3 回操作することで、すべての駒が同じマスに置かれます。

• マス (1,1) に置いてある駒をマス (1,2) へ移動させる。
• マス (1,2) に置いてある駒をマス (1,3) へ移動させる。
• マス (2,3) に置いてある駒をマス (1,3) へ移動させる。

2 回以下の操作で目的を達成することはできないので、3 が答えとなります。

入力例 2

5 5 10
2 2
2 5
1 3
2 4
2 3
1 5
2 1
1 4
1 2
1 1

出力例 2

28

入力例 3

100000 100000 0

出力例 3

500000000000000

入力例 4

2 2 3
1 2
2 1
2 2

出力例 4

0