pulse

The two famous bug-countries United Bug Land and Al-Bugida are at war. Tzutzu, the best spy from United Bug Land, has to infiltrate in Al-Bugida to end the war once and for all.

The war zone between the two countries is an $N \times N$ matrix, so that United Bug Land is situated at coordinates $(1, 1)$ and Al-Bugida is situated at coordinates $(N, N)$. Tzutzu starts his mission from coordinates $(1, 1)$ and each day he can choose to move one unit up, down, left or right or he can stay still without ever leaving the world map.

Unfortunately, the war zone is monitored by $P$ pulsating radars from Al-Bugida, that Tzutzu needs to avoid at all costs. The radars are positioned at coordinates $(X_i, Y_i)$, and scan the surrounding area up to a radius of $R_i$. More precisely, every $R_i$ days the radars scan their surroundings starting with day $0$, the start of Tzutzu’s mission. In the first day, every radar is scanning the immediate vicinities, detecting presence of spies in the exact coordinates $(X_i , Y_i)$. In the following days, the detection radius increases by $1$, expanding the monitored area by $1$ in the four cardinal directions from any previously detected zone. At day $R_i$, the radar resets, starting again from scanning the immediate vicinities.

Task

Help Tzutzu by computing the minimum number of days he has to spend in the war zone, in order to accomplish its mission while avoiding the radars!

Input data

The first line contains two integers $N$, $P$. The following $P$ lines contains integers $X_i$, $Y_i$, $R_i$ each.

Output data

You need to write a single line with an integer: the minimum number of days Tzutzu has to spend in the war zone.

Constraints and clarifications

• $1 ≤ N ≤ 500$
• $1 ≤ P ≤ 150 \ 000$
• $1 \leq X_i, Y_i \leq N$
• $1 \leq R_i \leq 6$
• There may be more than one radar in the same coordinates.
• Tzutzu can always reach his destination.
• For tests worth $10$ points, $N \leq 10$.
• For tests worth $20$ more points, $R_i = 1, \forall\ i$
• For tests worth $20$ more points, $N \leq 50$.

Example 1

stdin

5 1
3 3 3

stdout

9

Explanation

In the first sample case, a valid path for Tzutzu is:

Example 2

stdin

5 1
3 3 4

stdout

11

Explanation

In the second sample case, a valid path for Tzutzu is: