어디로 피해야하지?

$N \times N$ 크기의 격자판에 $K$ 개의 물폭탄이 놓여있다. 세기가 $p$인 물폭탄은 물폭탄이 놓인 칸을 포함하여 위, 아래, 왼쪽, 오른쪽 네 방향으로 $p$ 개 칸으로 물줄기가 나가며 공격한다. 예를 들어, 세기가 $1$인 물폭탄은 총 $5$ 칸을, 세기가 $2$인 물폭탄은 총 $9$ 칸을 공격한다. 하지만 격자판 밖으로 물줄기가 나가는 경우는 무시한다.

$K$ 개의 물폭탄의 위치와 세기가 주어졌을 때, 격자판에서 공격을 받지 않는 안전한 칸의 수를 구하는 프로그램을 작성하라.

예를 들어, 다음 그림과 같이 $5 \times 5$ 크기의 격자에 $3$ 개의 물폭탄이 주어진 경우를 생각해보자. 모든 물폭탄의 세기는 $4$이다. 즉, 물폭탄이 있는 칸으로부터 왼쪽, 오른쪽, 위, 아래로 연속한 $4$ 칸은 공격을 받는다.

물폭탄이 터졌을 때는 다음과 같다. 물줄기를 맞지 않고 안전한 칸은 총 $4$ 개임을 알 수 있다.

입력 형식

첫 줄에 격자판의 크기를 나타내는 정수 $N$과 물폭탄의 개수를 나타내는 정수 $K$가 공백으로 구분되어 주어진다. ($2 \le N \le 1\,000\,000\,000;$ $1 \le K \le 300\,000$)

이어지는 $K$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 물폭탄의 좌표를 나타내는 두 정수 $x_i$와 $y_i$, $i$ 번째 물폭탄의 세기를 나타내는 정수 $p_i$가 공백으로 구분되어 주어진다. ($1 \le x_i, y_i, p_i \le N$)

서로 다른 두 물폭탄이 같은 위치에 있을 수 있음에 유의하라.

출력 형식

첫 줄에 공격을 받지 않는 안전한 칸의 수를 출력한다.

예제

5 3
2 2 4
5 3 4
3 4 4

4

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설