Description:
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 < 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?
Input Format:
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<t_{i+1}$$$ for any $$$i=1,2,\ldots, n-1$$$.
Output Format:
Print a single integer, the maximum number of celebrities you can take a photo of.
Note:
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$$$.