Umbral Decoding

You are planning an attack on a new encryption algorithm. To succeed you must find the key, which is a pair of integers $(p, q)$. Think of the key as a point on the two dimensional integer lattice whose position is unknown. For a given $n$ you do know that $(p, q)$ lies in the square spanned by the lattice points $(0, 0)$ and $(n, n)$, that is, $0 \le p, q \le n$.

The attack has three stages.

1. Identify the safe points and their bounds.
2. Eliminate from the key candidates every point that lies in the umbra of some safe point.
3. Test the remaining points to see which one is the key.

Stage 1 is already done, and several safe points of the form $(x, y, b)$ are given as input.

In stage 2 you eliminate a point $(p, q)$ when it lies in the umbra of some safe point. Point $(p, q)$ is in the umbra of safe point $(x, y, b)$ if and only if

$|x - p|^3 + |y - q|^3 \le b$

Count how many points are left for stage 3, so that the amount of work still needed to finish the attack is known.

Figure 1. Safe points and their umbra (red) and the remaining points (blue), for one example.

The first line holds two integers $n$ and $k$ separated by a space, with $2 \le n \le 10^8$ and $0 \le k \le 100$.

Each of the next $k$ lines holds three integers $x$, $y$, $b$ separated by spaces, describing one safe point. Both $x$ and $y$ are in the range $[0, n]$, and the bound $b$ is also in the range $[0, n]$.

Print the number of points $(p, q)$ with $0 \le p, q \le n$ that do not lie in the umbra of any safe point.