Problem C
Umbral Decoding

You are planning a clever attack against a new encryption algorithm. To succeed, you need to find the key, which is a pair of integers $(p, q)$. We can think of the key as a point on a two-dimensional integer lattice whose location is unknown. However, you know that $(p, q)$ lies in the square spanned by the lattice points $(0, 0)$ and $(n, n)$ for a given $n$, i.e. $0\leq p,q\leq n$.

Your attack has three stages:

1. Identify safe points and their bounds.

2. Eliminate as key candidates those points that lie in the “umbra” of any safe point.

3. Test the remaining points to see which one is the key.

Stage 1 has already been performed and you are given several safe points of the form $(x, y, b)$ as input.

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

Your task in this problem is to count how many points will be left for testing in Stage 3 so that we have an estimate of the amount of work left to complete the attack.

Figure 1: Sample input safe points and umbra (red) and remaining points (blue).

Input

Input begins with two integers $n, k$ on a single line, separated by a space, with $2 \leq n \leq 100\, 000\, 000$, and $0 \leq k \leq 100$. Following that are $k$ lines each containing three integers $x, y, b$ separated by spaces, representing the safe points. The values of $x$ and $y$ are both in the range $[0,n]$. The bound $b$ lies in the range $[0, n]$.

Output

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

4 1
2 2 2

16

30 2
20 20 30
25 22 30

891