你是在曼哈顿工作的狗仔队。
曼哈顿有 $$$r$$$ 从南到北的街道,从西到东依次用数字 $$$1, 2,\ldots, r$$$ 表示,还有 $$$r$$$ 从西到东的街道,从南到北依次用数字 $$$1,2,\ldots,r$$$ 表示。每条从南到北的 $$$r$$$ 街道均与每条从西到东的 $$$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 < t_{i+1}$$$。
目前您位于办公室,位于十字路口 $$$(1, 1)$$$。如果您以最佳方式计划您的工作日,您最多可以拍摄多少位名人?
输入
输入的第一行包含两个正整数 $$$r, n$$$ ($$$1\le r\le 500$$$, $$$1\le n\le 100,000$$$) – 从南到北/从西到东的街道数量和名人数量。
接下来是 $$$n$$$ 行,每行描述一位名人的外貌。这些行中的第 $$$i$$$ 包含 $$$3$$$ 正整数 $$$t_i, x_i, y_i$$$ ($$$1\le t_i\le 1,000,000$$$, $$$1\le x_i, y_i\le r$$$) — 表示第 $$$i$$$ 位名人将出现在路口$$$(x_i, y_i)$$$ 从现在开始 $$$t_i$$$ 分钟后。
对于任何$$$i=1,2,\ldots, n-1$$$,保证$$$t_i<t_{i+1}$$$。
输出
打印一个整数,即您可以拍摄照片的最大名人数量。
示例
输入 #1
10 1 11 6 8
输出 #1
0
输入 #2
6 9 1 2 6 7 5 1 8 5 5 10 3 1 12 4 4 13 6 2 17 6 6 20 1 4 21 5 4
输出 #2
4
输入 #3
10 4 1 2 1 5 10 9 13 8 8 15 9 9
输出 #3
1
输入#4
500 10 69 477 122 73 186 235 341 101 145 372 77 497 390 117 440 494 471 37 522 300 498 682 149 379 821 486 359 855 157 386
输出#4
3
注意
第一个测试用例的解释:城市中只有一个名人,他将在工作日开始后 $$$(6,8)$$$ 恰好 $$$11$$$ 分钟到达十字路口。由于您最初位于 $$$(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$$$ 分钟才能到达那里,因此您在 $$$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$$$,你可以在一分钟后到达十字路口$$$(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$$$ 的照片。