CF1427C The Hard Work of Paparazzi

你是一名在曼哈顿工作的狗仔队。 曼哈顿有 $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)$ 才能为他拍照）。你拍照的速度极快，可以瞬间完成拍照。已知 $t_i < t_{i+1}$ 对于所有 $i=1,2,\ldots,n-1$ 都成立。 你现在在办公室，位置是交点 $(1, 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)$。 保证 $t_i < t_{i+1}$ 对于所有 $i=1,2,\ldots,n-1$ 都成立。

输出一个整数，表示你最多能为多少位名人拍照。

第一个样例解释：城里只有一位名人，他将在第 $11$ 分钟出现在交点 $(6,8)$。你现在在 $(1,1)$，需要 $|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$ 分钟，到达时是第 $10$ 分钟，等到第 $12$ 分钟为第 $5$ 位名人拍照。 - 拍完第 $5$ 位名人后，前往交点 $(6,6)$，需要 $|4-6|+|4-6|=2+2=4$ 分钟，到达时是第 $16$ 分钟，等到第 $17$ 分钟为第 $7$ 位名人拍照。 - 拍完第 $7$ 位名人后，前往交点 $(5,4)$，需要 $|6-5|+|6-4|=1+2=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$ 分钟，因此可以在第 $341$ 分钟赶到，为第 $3$ 位名人拍照。 - 拍完第 $3$ 位名人后，前往交点 $(149,379)$，需要 $|101-149|+|145-379|=282$ 分钟，到达时是第 $623$ 分钟，等到第 $682$ 分钟为第 $8$ 位名人拍照。 - 拍完第 $8$ 位名人后，前往交点 $(157,386)$，需要 $|149-157|+|379-386|=8+7=15$ 分钟，到达时是第 $697$ 分钟，等到第 $855$ 分钟为第 $10$ 位名人拍照。 由 ChatGPT 4.1 翻译