못 (Nails)

JOI 군은 판에 못을 박으며 놀고 있다. JOI 군은 한 변에 $N$개의 못이 놓이도록 못을 정삼각형 모양으로 배치했다. 위에서 $a$번째 줄($1 \le a \le N$)에는 $a$개의 못이 있으며, 그중 왼쪽에서 $b$번째($1 \le b \le a$) 못을 $(a, b)$로 나타낸다.

세 못을 꼭짓점으로 하는 정삼각형이 전체 정삼각형의 세 변과 각각 평행하고 전체 정삼각형과 같은 방향을 향하면, 이 삼각형을 좋은 정삼각형이라고 부른다. 즉 좋은 정삼각형이란 세 못 $(a, b)$, $(a + x, b)$, $(a + x, b + x)$를 꼭짓점으로 하는 정삼각형이다(단, $1 \le a < N$, $1 \le b \le a$, $1 \le x \le N - a$).

JOI 군은 고무줄로 좋은 정삼각형의 둘레를 감싸려고 한다. 하나의 좋은 정삼각형을 감싼 고무줄은 그 삼각형의 내부와 경계에 있는 모든 못을 감싼다.

한 변에 놓인 못의 개수 $N$, 고무줄의 개수 $M$, 그리고 각 고무줄이 감싸는 좋은 정삼각형이 주어질 때, 한 개 이상의 고무줄에 감싸인 못의 개수를 구하는 프로그램을 작성하여라.

첫째 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다. $N$은 정삼각형 한 변에 놓인 못의 개수이고, $M$은 고무줄의 개수이다.

다음 $M$개의 줄에는 각 고무줄이 감싸는 좋은 정삼각형의 정보가 주어진다. $i$번째 줄($1 \le i \le M$)에는 세 정수 $A_i$, $B_i$, $X_i$($1 \le A_i < N$, $1 \le B_i \le A_i$, $1 \le X_i \le N - A_i$)가 공백으로 구분되어 주어진다. 이는 $i$번째 고무줄이 세 못 $(A_i, B_i)$, $(A_i + X_i, B_i)$, $(A_i + X_i, B_i + X_i)$를 꼭짓점으로 하는 좋은 정삼각형을 감싸고 있음을 뜻한다.

한 개 이상의 고무줄에 감싸인 못의 개수를 한 줄에 출력하여라.

• $2 \le N \le 5000$ : 한 변에 놓인 못의 개수
• $1 \le M \le 500000$ ($= 5 \times 10^5$) : 고무줄의 개수

좋은 정삼각형 $(a, b)$, $(a + x, b)$, $(a + x, b + x)$의 내부와 경계에 있는 못은 다음과 같다: $a \le r \le a + x$인 각 줄 $r$에 대해, $b \le c \le b + (r - a)$를 만족하는 못 $(r, c)$이다.

예를 들어 $N = 5$이고 두 고무줄이 각각 좋은 정삼각형 $(2, 2, 1)$과 $(2, 1, 3)$을 감싼다면, 못 $(1, 1)$, $(4, 4)$, $(5, 5)$를 제외한 12개의 못이 한 개 이상의 고무줄에 감싸인다.