27115번 - 통신소

대한민국 공군은 비행하는 전투기와 지상에서 원활하게 통신하기 위하여 여러 위치에 통신소를 설치하였다. 지금까지 $K$개의 통신소를 배치하였는데, 각 통신소는 $\left(y_i,x_i\right)$의 위치에서 전파 세기가 $p_i$인 전파를 발생시켜 $\left| y_i - y \right| + \left| x_i - x \right| \leq p_i$인 모든 정수 $y$, $x$에 대하여 $\left(y,x\right)$에서 비행하는 전투기와 통신할 수 있다. 서로 다른 위치에서 발생한 전파가 서로 만나더라도 전파 세기는 변함없다.

지도의 세로 크기 $N$과 가로 크기 $M$, 통신소 $K$개의 위치와 전파 세기가 주어졌을 때, 지도 안에서 비행하는 전투기가 적어도 하나의 통신소와 통신할 수 있는 정수 격자점 $\left(y,x\right)$의 개수를 구하여라.

첫 번째 줄에 지도의 세로 크기 $N$과 가로 크기 $M$, 통신소의 개수 $K$가 공백으로 구분되어 정수로 주어진다. $(1\leq N,M\leq 3\,000;$ $1\leq K\leq 300\,000)$

두 번째 줄부터 $K+1$번째 줄까지, 설치한 통신소 $i$의 세로 위치 $y_i$, 가로 위치 $x_i$와 전파 세기 $p_i$가 공백으로 구분되어 정수로 주어진다. $(1\leq y_i\leq N;$ $1\leq x_i\leq M;$ $1\leq p_i\leq 3\,000)$

통신소의 위치가 중복되는 입력은 주어지지 않는다.

지도 안에서 전투기가 적어도 하나의 통신소와 서로 통신할 수 있는 정수 격자점의 개수를 출력한다.