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?
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$$$. 
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$$$.
Print a single integer, the maximum number of celebrities you can take a photo of.
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
    return map(int, sys.stdin.readline().rstrip().split())

def RLL():
    return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
    return int(input())

def print_list(l):
    print(' '.join(map(str, l)))
import bisect as bs
from collections import defaultdict as dc
(r, n) = RL()
dic = dc(set)
dic[0].add((0, 1, 1))
m = 0
for _ in range(n):
    (t, x, y) = RL()
    flag = False
    for last in range(m, -1, -1):
        for (tt, xx, yy) in dic[last]:
            if abs(x - xx) + abs(y - yy) <= t - tt:
                now = last + 1
                dic[now].add((t, x, y))
                if last == m:
                    m += 1
                flag = True
                break
        if flag:
            break
print(m)
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):
    (r, n) = map(int, input().split())
    ts = [0]
    xs = [1]
    ys = [1]
    for _ in range(n):
        (ti, xi, yi) = map(int, input().split())
        if xi - 1 + (yi - 1) > ti:
            continue
        ts.append(ti)
        xs.append(xi)
        ys.append(yi)
    dp = [[(0, 1, 1)]]
    ans = 0
    for i in range(1, len(ts)):
        flag = False
        for j in range(ans, -1, -1):
            for (t, x, y) in dp[j]:
                if abs(xs[i] - x) + abs(ys[i] - y) <= ts[i] - t:
                    if j == ans:
                        ans += 1
                        dp.append([])
                    currans = j + 1
                    flag = True
                    break
            if flag:
                break
        dp[currans].append((ts[i], xs[i], ys[i]))
    print(len(dp) - 1)
T = 1
t = 1
while t <= T:
    main(t)
    t += 1
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline
    (r, n) = map(int, input().split())
    dic = defaultdict(set)
    dic[0].add((0, 1, 1))
    ans = 0
    for _ in range(n):
        (t, x, y) = map(int, input().split())
        f = False
        for i in range(ans, -1, -1):
            for (t_, x_, y_) in dic[i]:
                if abs(x - x_) + abs(y - y_) <= t - t_:
                    dic[i + 1].add((t, x, y))
                    if i == ans:
                        ans += 1
                    f = True
                    break
            if f:
                break
    print(ans)
if __name__ == '__main__':
    main()