#P1063. 火山

火山

题目背景

面条老师现在正在一个小岛上旅游,这个小岛上有很多火山口。火山爆发了!所有火山口一起爆发了!

题目描述

小岛的地图可以看作是一个 RRCC 列的网格。

现在一共有 NN 个火山口正在喷发。第 ii 个火山口在第 xix_i 行,第 yiy_i 列的格子上。

每个火山口会影响曼哈顿距离小于等于 22 的所有格子,请问有多少个格子没被影响。

曼哈顿距离:“第 xx 行第 yy 列”与“第 aa 行第 bb 列”之间的曼哈顿距离为 xa+yb|x-a|+|y-b|,即行数距离与列数距离之和。如果看不懂的话,可以看看下面的样例。

输入格式

第一行三个整数 R,C,NR,C,N

接下来 NN 行每行两个整数,第 ii 行的两个整数分别为 xix_iyiy_i

输出格式

一行一个整数,表示有多少个格子没被影响。

8 10 3
3 4
4 9
6 8
46

样例解释

数据规模与约定

  • 对于 30%30\% 的数据,保证所有火山的影响范围都在小岛内,且互相之间没有重叠的影响区域。
  • 对于 60%60\% 的数据,保证所有火山的影响范围都在小岛内
  • 对于 100%100\% 的数据,1R,C10001\le R,C \le 10001N1041\le N\le 10^41xiR1\le x_i\le R1yiC1\le y_i\le C