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 < 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?

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

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 $ .