Nails

JOI is playing by driving nails into a board. JOI arranges the nails in the shape of an equilateral triangle with $N$ nails along each side. Row $a$ from the top ($1 \le a \le N$) contains $a$ nails, and the $b$-th nail from the left in that row ($1 \le b \le a$) is denoted $(a, b)$.

An equilateral triangle whose three vertices are nails is called a good triangle if each of its sides is parallel to a side of the whole triangle and it points in the same direction as the whole triangle. In other words, a good triangle is the triangle whose vertices are the three nails $(a, b)$, $(a + x, b)$, and $(a + x, b + x)$, where $1 \le a < N$, $1 \le b \le a$, and $1 \le x \le N - a$.

JOI wraps a rubber band around a good triangle. A rubber band wrapped around a good triangle encloses every nail on the boundary of and inside that triangle.

Given the number of nails $N$ along one side, the number of rubber bands $M$, and the good triangle wrapped by each rubber band, write a program that computes how many nails are enclosed by at least one rubber band.

The first line contains two integers $N$ and $M$, separated by a space. $N$ is the number of nails along one side of the triangle, and $M$ is the number of rubber bands.

Each of the following $M$ lines describes the good triangle wrapped by one rubber band. The $i$-th line ($1 \le i \le M$) contains three integers $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$), separated by spaces. This means that the $i$-th rubber band wraps the good triangle whose vertices are the nails $(A_i, B_i)$, $(A_i + X_i, B_i)$, and $(A_i + X_i, B_i + X_i)$.

Print, on a single line, the number of nails enclosed by at least one rubber band.

• $2 \le N \le 5000$ : the number of nails along one side
• $1 \le M \le 500000$ ($= 5 \times 10^5$) : the number of rubber bands

The nails on the boundary of and inside the good triangle $(a, b)$, $(a + x, b)$, $(a + x, b + x)$ are exactly the following: for each row $r$ with $a \le r \le a + x$, the nails $(r, c)$ with $b \le c \le b + (r - a)$.

For instance, if $N = 5$ and two rubber bands wrap the good triangles $(2, 2, 1)$ and $(2, 1, 3)$, then every nail except $(1, 1)$, $(4, 4)$, and $(5, 5)$ — that is, $12$ nails — is enclosed by at least one rubber band.