Mogu Mogu (hard)

問題文

$H$ 行 $W$ 列のグリッドがある。各グリッドにはおにぎりが置かれており、お腹の空いたoさんは次のように $N$ 回の操作を行っておにぎりを食べることにした。操作中の $i$ $(1 \leq i \leq N)$ はその操作が何番目の操作かを示す。

• 上から $y_i$ 行目、左から $x_i$ 列目のグリッドに、おにぎりが置いてあればそのおにぎりを食べる。置いていない場合、そのグリッドから斜め四方向に進み、それぞれ最初におにぎりのあるグリッドに到着した場合はそのおにぎりを食べる。

$N$ 回の操作の後、食べられずに残ったおにぎりの個数を求めよ。

制約

• $1 \leq HW \leq 10^5$
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq y_i \leq H , 1 \leq x_i \leq W (1 \leq i \leq N)$

入力

入力はすべて整数である。

H W
N
y_1 x_1
y_2 x_2
...
y_N x_N

出力

$N$ 回の操作の後、食べられずに残ったおにぎりの個数を出力せよ。

サンプル

4 4
3
2 2
3 2
2 2

10

3回の操作によるおにぎりの状況の変化は次の通りです。

####    ####    ####    .#.#
#### -> #.## -> #.## -> #.##
####    ####    #.##    ...#
####    ####    ####    ####

3 4
4
1 1
1 1
2 2
2 4

6

4回の操作によるおにぎりの状況の変化は次の通りです。

####    .###    .###    .#.#    .#.#
#### -> #### -> #.## -> #.## -> #.#.
####    ####    ####    .#.#    .#.#

3 3
5
2 2
2 2
1 2
1 2
3 2

0

この例において、グリッド上のおにぎりはoさんに全て食べられています。(ｳﾏｳﾏ)