CF1427C.The Hard Work of Paparazzi

You are a paparazzi working in Manhattan.

Manhattan has $r$ south-to-north streets, denoted by numbers $1, 2,\ldots, r$ in order from west to east, and $r$ west-to-east streets, denoted by numbers $1,2,\ldots,r$ in order from south to north. Each of the $r$ south-to-north streets intersects each of the $r$ west-to-east streets; the intersection between the $x$-th south-to-north street and the $y$-th west-to-east street is denoted by $(x, y)$. In order to move from the intersection $(x,y)$ to the intersection $(x', y')$ you need $|x-x'|+|y-y'|$ minutes.

You know about the presence of $n$ celebrities in the city and you want to take photos of as many of them as possible. More precisely, for each $i=1,\dots, n$, you know that the $i$-th celebrity will be at the intersection $(x_i, y_i)$ in exactly $t_i$ minutes from now (and he will stay there for a very short time, so you may take a photo of him only if at the $t_i$-th minute from now you are at the intersection $(x_i, y_i)$). You are very good at your job, so you are able to take photos instantaneously. You know that $t_i \lt t_{i+1}$ for any $i=1,2,\ldots, n-1$.

Currently you are at your office, which is located at the intersection $(1, 1)$. If you plan your working day optimally, what is the maximum number of celebrities you can take a photo of?

你是一名在曼哈顿工作的狗仔队记者。

曼哈顿有 $r$ 条由南向北的街道，从西到东依次编号为 $1, 2,\ldots, r$；另有 $r$ 条由西向东的街道，从南到北依次编号为 $1,2,\ldots,r$。每条由南向北的街道均与每条由西向东的街道相交；第 $x$ 条由南向北的街道与第 $y$ 条由西向东的街道的交点记为 $(x, y)$。从交点 $(x,y)$ 移动到交点 $(x', y')$ 需要 $|x-x'|+|y-y'|$ 分钟。

你已获悉城中有 $n$ 位名人，并希望尽可能多地拍摄他们的照片。更准确地说，对每个 $i=1,\dots, n$，你知道第 $i$ 位名人将在当前时刻之后恰好 $t_i$ 分钟出现在交点 $(x_i, y_i)$（且他仅在该处短暂停留，因此你仅当在当前时刻之后的第 $t_i$ 分钟恰好位于交点 $(x_i, y_i)$ 时，才能成功为其拍照）。你工作能力极强，可瞬间完成拍照。此外，已知对任意 $i=1,2,\ldots, n-1$，均有 $t_i \lt t_{i+1}$。

目前你位于办公室，其位置为交点 $(1, 1)$。若你对当天工作进行最优规划，最多能拍摄多少位名人的照片？

The first line of the input contains two positive integers $r, n$ ($1\le r\le 500$, $1\le n\le 100,000$) – the number of south-to-north/west-to-east streets and the number of celebrities.

Then $n$ lines follow, each describing the appearance of a celebrity. The $i$-th of these lines contains $3$ positive integers $t_i, x_i, y_i$ ($1\le t_i\le 1,000,000$, $1\le x_i, y_i\le r$) — denoting that the $i$-th celebrity will appear at the intersection $(x_i, y_i)$ in $t_i$ minutes from now.

It is guaranteed that $t_i \lt t_{i+1}$ for any $i=1,2,\ldots, n-1$.

输入的第一行包含两个正整数 $r, n$（$1\le r\le 500$，$1\le n\le 100,000$）——分别表示由南向北/由西向东的街道数量以及名人的数量。

接下来是 $n$ 行，每行描述一位名人的出现信息。其中第 $i$ 行包含三个正整数 $t_i, x_i, y_i$（$1\le t_i\le 1,000,000$，$1\le x_i, y_i\le r$），表示第 $i$ 位名人将在 $t_i$ 分钟后出现在坐标为 $(x_i, y_i)$ 的路口。

保证对任意 $i=1,2,\ldots, n-1$，均有 $t_i \lt t_{i+1}$。

Print a single integer, the maximum number of celebrities you can take a photo of.

输出一个整数，表示你能合影的名人数目的最大值。

Explanation of the first testcase: There is only one celebrity in the city, and he will be at intersection $(6,8)$ exactly $11$ minutes after the beginning of the working day. Since you are initially at $(1,1)$ and you need $|1-6|+|1-8|=5+7=12$ minutes to reach $(6,8)$ you cannot take a photo of the celebrity. Thus you cannot get any photo and the answer is $0$.

Explanation of the second testcase: One way to take $4$ photos (which is the maximum possible) is to take photos of celebrities with indexes $3, 5, 7, 9$ (see the image for a visualization of the strategy):

• To move from the office at $(1,1)$ to the intersection $(5,5)$ you need $|1-5|+|1-5|=4+4=8$ minutes, so you arrive at minute $8$ and you are just in time to take a photo of celebrity $3$.
• Then, just after you have taken a photo of celebrity $3$, you move toward the intersection $(4,4)$. You need $|5-4|+|5-4|=1+1=2$ minutes to go there, so you arrive at minute $8+2=10$ and you wait until minute $12$, when celebrity $5$ appears.
• Then, just after you have taken a photo of celebrity $5$, you go to the intersection $(6,6)$. You need $|4-6|+|4-6|=2+2=4$ minutes to go there, so you arrive at minute $12+4=16$ and you wait until minute $17$, when celebrity $7$ appears.
• Then, just after you have taken a photo of celebrity $7$, you go to the intersection $(5,4)$. You need $|6-5|+|6-4|=1+2=3$ minutes to go there, so you arrive at minute $17+3=20$ and you wait until minute $21$ to take a photo of celebrity $9$.

Explanation of the third testcase: The only way to take $1$ photo (which is the maximum possible) is to take a photo of the celebrity with index $1$ (since $|2-1|+|1-1|=1$, you can be at intersection $(2,1)$ after exactly one minute, hence you are just in time to take a photo of celebrity $1$).

Explanation of the fourth testcase: One way to take $3$ photos (which is the maximum possible) is to take photos of celebrities with indexes $3, 8, 10$:

• To move from the office at $(1,1)$ to the intersection $(101,145)$ you need $|1-101|+|1-145|=100+144=244$ minutes, so you can manage to be there when the celebrity $3$ appears (at minute $341$).
• Then, just after you have taken a photo of celebrity $3$, you move toward the intersection $(149,379)$. You need $|101-149|+|145-379|=282$ minutes to go there, so you arrive at minute $341+282=623$ and you wait until minute $682$, when celebrity $8$ appears.
• Then, just after you have taken a photo of celebrity $8$, you go to the intersection $(157,386)$. You need $|149-157|+|379-386|=8+7=15$ minutes to go there, so you arrive at minute $682+15=697$ and you wait until minute $855$ to take a photo of celebrity $10$.

第一个测试用例的解释：城市中只有一位名人，他恰好在工作日开始后 $11$ 分钟出现在交叉路口 $(6,8)$。由于你初始位置为 $(1,1)$，而到达 $(6,8)$ 所需时间为 $|1-6|+|1-8|=5+7=12$ 分钟，因此你无法及时赶到 $(6,8)$ 拍摄该名人。故你无法获得任何照片，答案为 $0$。

第二个测试用例的解释：一种可拍摄 $4$ 张照片的方法（这也是可能的最大值）是拍摄编号为 $3, 5, 7, 9$ 的名人（参见下图以直观理解该策略）：

• 从办公室 $(1,1)$ 移动到交叉路口 $(5,5)$ 需要 $|1-5|+|1-5|=4+4=8$ 分钟，因此你在第 $8$ 分钟抵达，并恰好来得及拍摄名人 $3$。
• 拍摄完名人 $3$ 后，你立即前往交叉路口 $(4,4)$。所需时间为 $|5-4|+|5-4|=1+1=2$ 分钟，因此你在 $8+2=10$ 分钟时抵达，并等待至第 $12$ 分钟，此时名人 $5$ 出现。
• 拍摄完名人 $5$ 后，你立即前往交叉路口 $(6,6)$。所需时间为 $|4-6|+|4-6|=2+2=4$ 分钟，因此你在 $12+4=16$ 分钟时抵达，并等待至第 $17$ 分钟，此时名人 $7$ 出现。
• 拍摄完名人 $7$ 后，你立即前往交叉路口 $(5,4)$。所需时间为 $|6-5|+|6-4|=1+2=3$ 分钟，因此你在 $17+3=20$ 分钟时抵达，并等待至第 $21$ 分钟，此时名人 $9$ 出现。

第三个测试用例的解释：唯一能拍摄 $1$ 张照片的方法（这也是可能的最大值）是拍摄编号为 $1$ 的名人（因为 $|2-1|+|1-1|=1$，你可在恰好 $1$ 分钟后抵达交叉路口 $(2,1)$，从而恰好来得及拍摄名人 $1$）。

第四个测试用例的解释：一种可拍摄 $3$ 张照片的方法（这也是可能的最大值）是拍摄编号为 $3, 8, 10$ 的名人：

• 从办公室 $(1,1)$ 移动到交叉路口 $(101,145)$ 需要 $|1-101|+|1-145|=100+144=244$ 分钟，因此你能在名人 $3$ 出现时（第 $341$ 分钟）成功抵达该地。
• 拍摄完名人 $3$ 后，你立即前往交叉路口 $(149,379)$。所需时间为 $|101-149|+|145-379|=282$ 分钟，因此你在 $341+282=623$ 分钟时抵达，并等待至第 $682$ 分钟，此时名人 $8$ 出现。
• 拍摄完名人 $8$ 后，你立即前往交叉路口 $(157,386)$。所需时间为 $|149-157|+|379-386|=8+7=15$ 分钟，因此你在 $682+15=697$ 分钟时抵达，并等待至第 $855$ 分钟，此时名人 $10$ 出现。