You are a paparazzi working in Manhattan.

Manhattan has r south-to-north streets, denoted by numbers 1, 2,…, r in order from west to east, and r west-to-east streets, denoted by numbers 1,2,…,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,..., 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,…, 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

The first line of the input contains two positive integers r, n (1≤ r≤ 500, 1≤ n≤ 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≤ t_i≤ 1,000,000, 1≤ x_i, y_i≤ 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,…, n-1.

Output

Print a single integer, the maximum number of celebrities you can take a photo of.

Examples

Input


10 1
11 6 8


Output


0


Input


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


Output


4


Input


10 4
1 2 1
5 10 9
13 8 8
15 9 9


Output


1


Input


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


Output


3

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. 

<image>

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.

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
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')

class SegmentTree:

	def __init__(self, data, default=-10 ** 6, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(200001)]
pp = [0] * 200001

def SieveOfEratosthenes(n=200000):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
(r, n) = map(int, input().split())
M = 2 * r
A = [(0, 1, 1)] + [tuple(map(int, input().split())) for _ in range(n)]
DP = [-n] * (n + 1)
DP[0] = 0
ii = 0
besti = -n
for i in range(1, n + 1):
	(t, x, y) = A[i]
	while A[ii][0] + M <= t:
		besti = max(besti, DP[ii])
		ii += 1
	b = besti + 1
	j = i
	while j > 0:
		j -= 1
		(to, xo, yo) = A[j]
		if DP[j] >= b and abs(xo - x) + abs(yo - y) <= t - to:
			b = DP[j] + 1
		if t - to >= M:
			break
	DP[i] = b
print(max(DP))


import sys
input = sys.stdin.readline
(r, n) = map(int, input().split())
M = 2 * r
A = [(0, 1, 1)] + [tuple(map(int, input().split())) for _ in range(n)]
DP = [-n] * (n + 1)
DP[0] = 0
ii = 0
besti = -n
for i in range(1, n + 1):
	(t, x, y) = A[i]
	while A[ii][0] + M <= t:
		besti = max(besti, DP[ii])
		ii += 1
	b = besti + 1
	j = i
	while j > 0:
		j -= 1
		(to, xo, yo) = A[j]
		if DP[j] >= b and abs(xo - x) + abs(yo - y) <= t - to:
			b = DP[j] + 1
		if t - to >= M:
			break
	DP[i] = b
print(max(DP))


import os, sys, atexit
from io import BytesIO
sys.stdout = BytesIO()
_write = sys.stdout.write
sys.stdout.write = lambda s: _write(s.encode())
atexit.register(lambda : os.write(1, sys.stdout.getvalue()))
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
(r, n) = map(int, input().split())
a = [[0, 1, 1]] + [list(map(int, input().split())) for _ in range(n)]
mem = [0] * (n + 1)
ma = [0] * (n + 1)
for (i, (t, x, y)) in enumerate(a[1:], 1):
	ix = i - 1
	cur = -(1 << 25)
	while ix > -1:
		(t1, x1, y1) = a[ix]
		if mem[ix] > cur and abs(x - x1) + abs(y - y1) <= t - t1:
			cur = mem[ix]
		if a[ix][0] <= t - 1000:
			if ma[ix] > cur:
				cur = ma[ix]
			break
		ix -= 1
	mem[i] = cur + 1
	ma[i] = max(ma[i - 1], mem[i])
print(ma[-1])


import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
			self.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')
import time
start_time = time.time()
import collections as col
import math
from functools import reduce

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def solve():
	(R, N) = getInts()
	dp = [-10 ** 5 - 1] * (N + 1)
	A = [(0, 1, 1)] + [tuple(getInts()) for i in range(N)]
	max_dp = [0] * (N + 1)
	M = 2 * R
	dp[0] = 0
	for i in range(1, N + 1):
		(t, x, y) = A[i]
		best = 0
		if i >= M:
			dp[i] = max_dp[i - M] + 1
		best = dp[i]
		for j in range(i - 1, max(-1, i - M), -1):
			(t0, x0, y0) = A[j]
			if dp[j] >= best and abs(x - x0) + abs(y - y0) <= t - t0:
				best = dp[j] + 1
		dp[i] = best
		max_dp[i] = max(max_dp[i - 1], dp[i])
	return max_dp[N]
print(solve())


from sys import stdin

def input0():
	return stdin.readline()
(r, n) = map(int, input0().split())
points = []
for i in range(n):
	p = list(map(int, input0().split()))
	points.append(p)
dp = []
m = []
for i in range(n):
	best = 0
	j = i - 1
	while j > -1:
		if points[i][0] - points[j][0] < 2 * r:
			if dp[j] + 1 > best and dp[j] != 0:
				if points[i][0] - points[j][0] >= abs(points[i][1] - points[j][1]) + abs(points[i][2] - points[j][2]):
					best = dp[j] + 1
		else:
			break
		j -= 1
	if best == 0 and j == -1:
		if abs(points[i][1] - 1) + abs(points[i][2] - 1) <= points[i][0]:
			best = 1
	if j >= 0:
		if m[j] + 1 > best:
			best = m[j] + 1
	if len(m) == 0:
		m.append(best)
	else:
		m.append(max(best, m[-1]))
	dp.append(best)
print(max(dp[-1], m[-1]))


import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = 1
for tc in range(TC):
	(R, N) = map(int, input().split())
	T = [0 for _ in range(N + 1)]
	X = [0 for _ in range(N + 1)]
	Y = [0 for _ in range(N + 1)]
	V = [0 for _ in range(N + 1)]
	M = [0 for _ in range(N + 1)]
	X[0] = 1
	Y[0] = 1
	result = 0
	for j in range(1, N + 1):
		(t, x, y) = map(int, input().split())
		T[j] = t
		X[j] = x
		Y[j] = y
		r = -N
		for i in range(j - 1, max(-1, j - 2 * R - 1), -1):
			if t - T[i] >= 2 * R:
				r = max(r, M[i] + 1)
				break
			if V[i] >= r and abs(x - X[i]) + abs(y - Y[i]) <= t - T[i]:
				r = max(r, V[i] + 1)
		V[j] = r
		M[j] = max(M[j - 1], r)
	print(M[-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)
main()


import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(R, N) = [int(x) for x in input().split()]
T = [0]
X = [1]
Y = [1]
inf = 1 << 20
dp = [-inf] * (N + 1)
dp[0] = 0
farMax = -inf
farIndex = 0
for i in range(1, N + 1):
	(t, x, y) = [int(x) for x in input().split()]
	T.append(t)
	X.append(x)
	Y.append(y)
	while t - T[farIndex] >= 2 * R:
		farMax = max(farMax, dp[farIndex])
		farIndex += 1
	best = max(dp[i], farMax)
	for j in range(farIndex, i):
		if best < dp[j] and t - T[j] >= abs(X[j] - x) + abs(Y[j] - y):
			best = dp[j]
	dp[i] = best + 1
print(max(dp))


(n, m) = map(int, input().split())
A = []
for i in range(m):
	(t, a, b) = map(int, input().split())
	if a - 1 + (b - 1) <= t:
		w = 0
	else:
		w = -1
	for j in range(len(A) - 1, -1, -1):
		if A[j][4] <= w:
			break
		elif A[j][3] > w:
			if t - A[j][0] >= abs(A[j][1] - a) + abs(A[j][2] - b):
				w = A[j][3]
	if len(A) == 0:
		if w >= 0:
			A.append((t, a, b, w + 1, 1))
	elif w >= 0:
		A.append((t, a, b, w + 1, max(w + 1, A[-1][-1])))
if A:
	print(A[-1][-1])
else:
	print(0)


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(r, n) = map(int, input().split())
C = [tuple(map(int, input().split())) for i in range(n)]
DP = [-1] * n
MAX = [-1] * n
for i in range(n):
	(t, x, y) = C[i]
	if t >= abs(x - 1) + abs(y - 1):
		DP[i] = 1
	if t > r * 2:
		MAX[i] = 1
		break
for i in range(n):
	MAX[i] = max(MAX[i], MAX[i - 1])
	play = max(MAX[i], DP[i])
	if play == -1:
		continue
	(t0, x0, y0) = C[i]
	for j in range(i + 1, n):
		(t, x, y) = C[j]
		if t >= t0 + abs(x - x0) + abs(y - y0):
			DP[j] = max(DP[j], play + 1)
		if t > t0 + r * 2:
			MAX[j] = play + 1
			break
ANS = max(max(MAX), max(DP))
if ANS == -1:
	print(0)
else:
	print(ANS)


import sys
input = sys.stdin.readline
(r, n) = [int(i) for i in input().split()]
m = 2 * r
cs = []
for _ in range(n):
	c = tuple((int(i) for i in input().split()))
	if c[1] + c[2] - 2 <= c[0]:
		cs.append(c)
if cs:
	ans = [-1] * n
	k = 0
	best = 0
	best2 = 0
	for i in range(len(cs)):
		while cs[k][0] + m <= cs[i][0]:
			best = max(best, ans[k])
			k += 1
		max_ans = best
		prev_i = i - 1
		while prev_i >= 0:
			if ans[prev_i] > max_ans and abs(cs[prev_i][1] - cs[i][1]) + abs(cs[prev_i][2] - cs[i][2]) <= cs[i][0] - cs[prev_i][0]:
				max_ans = ans[prev_i]
			prev_i -= 1
			if cs[i][0] - cs[prev_i][0] >= m:
				break
		ans[i] = max_ans + 1
		best2 = max(best2, ans[i])
	print(best2)
else:
	print(0)


import sys
from io import BytesIO, IOBase

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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
		self.BUFSIZE = 8192

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.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 = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.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:
			self.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 get_int():
	return int(input())

def get_ints():
	return list(map(int, input().split(' ')))

def get_int_grid(n):
	return [get_ints() for _ in range(n)]

def solve_c():
	(r, n) = get_ints()
	celebs = [(0, 1, 1)] + [tuple(get_ints()) for _ in range(n)]
	dp = [-float('inf')] * (n + 1)
	dp[0] = 0
	dp_max = [0] * (n + 1)
	M = 2 * r
	for idx in range(1, n + 1):
		(t, x, y) = celebs[idx]
		m = 0
		if idx >= M:
			dp[idx] = dp_max[idx - M] + 1
		m = dp[idx]
		for jdx in range(idx - 1, max(-1, idx - M), -1):
			(ta, xa, ya) = celebs[jdx]
			if dp[jdx] >= m and abs(x - xa) + abs(y - ya) <= t - ta:
				m = dp[jdx] + 1
		dp[idx] = m
		dp_max[idx] = max(dp[idx], dp_max[idx - 1])
	return dp_max[-1]
print(solve_c())


from sys import stdin
input = stdin.readline
(r, n) = map(int, input().split())
inp = [[0, 1, 1]] + [list(map(int, input().split())) for _ in range(n)]
dp = [0 for _ in range(n + 1)]
mAx = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
	(t, x, y) = inp[i]
	curr = -(1 << 30)
	for j in range(i - 1, -1, -1):
		(tt, xx, yy) = inp[j]
		if mAx[j] < curr:
			break
		if abs(xx - x) + abs(yy - y) <= t - tt:
			curr = max(curr, dp[j] + 1)
	dp[i] = curr
	mAx[i] = max(curr, mAx[i - 1])
print(mAx[-1])


import os
import sys
from io import BytesIO, IOBase
(r, n) = map(int, input().split())
ts = [0]
xs = [1]
ys = [1]
ans = [0]
maxans = [0]

def toolong(i, j):
	dis = abs(xs[i] - xs[j]) + abs(ys[i] - ys[j])
	return dis > ts[i] - ts[j]
for i in range(1, n + 1):
	(t, x, y) = map(int, input().split())
	ts.append(t)
	xs.append(x)
	ys.append(y)
	curans = -int(1000000000.0)
	for j in range(i - 1, -1, -1):
		if maxans[j] < curans:
			break
		if not toolong(i, j):
			curans = max(curans, ans[j])
	curans += 1
	ans.append(curans)
	maxans.append(max(maxans[-1], curans))
print(maxans[-1])


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
			self.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')
(r, n) = map(int, input().split())
ts = [0]
xs = [1]
ys = [1]
ans = [0]
maxans = [0]

def toolong(i, j):
	dis = abs(xs[i] - xs[j]) + abs(ys[i] - ys[j])
	return dis > ts[i] - ts[j]
for i in range(1, n + 1):
	(t, x, y) = map(int, input().split())
	ts.append(t)
	xs.append(x)
	ys.append(y)
	curans = -int(1000000000.0)
	for j in range(i - 1, -1, -1):
		if maxans[j] < curans:
			break
		if not toolong(i, j):
			curans = max(curans, ans[j])
	curans += 1
	ans.append(curans)
	maxans.append(max(maxans[-1], curans))
print(maxans[-1])


(r, n) = map(int, input().split())
A = []
for i in range(n):
	(t, x, y) = map(int, input().split())
	if x - 1 + (y - 1) > t:
		continue
	w = 0
	if len(A) == 0:
		A.append((t, x, y, w + 1, 1))
	else:
		for ev in reversed(A):
			if ev[4] <= w:
				break
			elif ev[3] > w and t - ev[0] >= abs(ev[1] - x) + abs(ev[2] - y):
				w = ev[3]
		A.append((t, x, y, w + 1, max(w + 1, A[-1][-1])))
if A:
	print(A[-1][-1])
else:
	print(0)


(r, n) = map(int, input().split())
ts = [0]
xs = [1]
ys = [1]
ans = [0]
maxans = [0]

def toolong(i, j):
	dis = abs(xs[i] - xs[j]) + abs(ys[i] - ys[j])
	return dis > ts[i] - ts[j]
for i in range(1, n + 1):
	(t, x, y) = map(int, input().split())
	ts.append(t)
	xs.append(x)
	ys.append(y)
	curans = -int(1000000000.0)
	for j in range(i - 1, -1, -1):
		if maxans[j] < curans:
			break
		if not toolong(i, j):
			curans = max(curans, ans[j])
	curans += 1
	ans.append(curans)
	maxans.append(max(maxans[-1], curans))
print(maxans[-1])


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(r, n) = map(int, input().split())
t = [0]
x = [1]
y = [1]
cdp = [0]
dp = [0]
for i in range(1, n + 1):
	(ti, xi, yi) = map(int, input().split())
	t.append(ti)
	x.append(xi)
	y.append(yi)
	mx = -10 ** 9
	for j in range(i)[::-1]:
		if cdp[j] < mx:
			break
		if abs(xi - x[j]) + abs(yi - y[j]) <= abs(ti - t[j]):
			mx = max(mx, dp[j])
	mx += 1
	dp.append(mx)
	cdp.append(max(cdp[-1], mx))
print(cdp[-1])


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(r, n) = list(map(int, input().split()))
(tl, xl, yl) = ([0], [1], [1])
d = [0]
dv = [0]
for i in range(1, n + 1):
	(t, x, y) = list(map(int, input().split()))
	tl.append(t)
	xl.append(x)
	yl.append(y)
	mv = int(-1000000000.0)
	for j in reversed(range(0, i)):
		if dv[j] < mv:
			break
		if tl[j] + abs(x - xl[j]) + abs(y - yl[j]) <= t:
			mv = max(mv, d[j])
	mv += 1
	d.append(mv)
	dv.append(max(dv[-1], mv))
print(dv[-1])


def jõuab(a, b):
	return a[0] - b[0] >= abs(a[1] - b[1]) + abs(a[2] - b[2])
a = [[[0, 1, 1]]]
b = int(input().strip().split(' ')[1])
for i in range(b):
	if a[-1] != []:
		a.append([])
	j = len(a) - 1
	c = list(map(int, input().strip().split(' ')))
	while j > 0:
		for k in a[j - 1]:
			if jõuab(c, k):
				a[j].append(c)
				j = 0
				break
		j -= 1
print(len(a) - 1) if a[-1] != [] else print(len(a) - 2)


import sys
input = sys.stdin.readline
(r, n) = map(int, input().split())
m = 2 * r
cs = [(0, 1, 1)] + [tuple(map(int, input().split())) for _ in range(n)]
ans = [-n] * (n + 1)
ans[0] = 0
k = 0
best = -n
for i in range(1, n + 1):
	(t, x, y) = cs[i]
	while cs[k][0] + m <= t:
		best = max(best, ans[k])
		k += 1
	b = best + 1
	j = i
	while j > 0:
		j -= 1
		(to, xo, yo) = cs[j]
		if ans[j] >= b and abs(xo - x) + abs(yo - y) <= t - to:
			b = ans[j] + 1
		if t - to >= m:
			break
	ans[i] = b
print(max(ans))


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.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(io.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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(R, N) = map(int, input().split())
TXY = [[0, 1, 1]] + [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (N + 1)
mas = [0] * (N + 1)
for (i, (t, x, y)) in enumerate(TXY[1:], 1):
	left = i - 1
	ma = -(1 << 62)
	while left >= 0:
		(tl, xl, yl) = TXY[left]
		dp_left = dp[left]
		if ma < dp_left and abs(xl - x) + abs(yl - y) <= t - tl:
			ma = dp_left
		if tl < t - 1000:
			if mas[left] > ma:
				ma = mas[left]
			break
		left -= 1
	dp[i] = ma + 1
	mas[i] = max(mas[i - 1], ma + 1)
print(mas[-1])


from sys import stdin, stdout, setrecursionlimit
from collections import deque
import bisect
R = lambda : stdin.readline().strip()
RL = lambda f=None: list(map(f, R().split(' '))) if f else list(R().split(' '))
output = lambda x: stdout.write(str(x) + '\n')
output_list = lambda x: output(' '.join(map(str, x)))

def dist(pos, dest):
	return abs(pos[0] - dest[0]) + abs(pos[1] - dest[1])

def solve(pos, i, spent, celeb, dic):
	if i >= len(celeb):
		return 0
	if spent in dic:
		return dic[spent]
	ch2 = solve(pos, i + 1, spent, celeb, dic)
	if dist(pos, celeb[i][1:]) > celeb[i][0] - spent:
		ch1 = ch2
	else:
		ch1 = 1 + solve(celeb[i][1:], i + 1, celeb[i][0], celeb, dic)
	dic[spent] = max(ch1, ch2)
	return dic[spent]
(r, n) = RL(int)
celeb = []
maxi = []
(tl, xl, yl) = ([0], [1], [1])
d = [0]
dv = [0]
for i in range(1, n + 1):
	(t, x, y) = RL(int)
	tl.append(t)
	xl.append(x)
	yl.append(y)
	mv = int(-1000000000.0)
	for j in reversed(range(0, i)):
		if dv[j] < mv:
			break
		if tl[j] + abs(x - xl[j]) + abs(y - yl[j]) <= t:
			mv = max(mv, d[j])
	mv += 1
	d.append(mv)
	dv.append(max(dv[-1], mv))
print(dv[-1])


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 sys, os, io
input = sys.stdin.readline
(r, n) = map(int, input().split())
from bisect import *
(T, X, Y) = ([0] * n, [0] * n, [0] * n)
for i in range(n):
	(T[i], X[i], Y[i]) = map(int, input().split())
T = [0] + T
X = [1] + X
Y = [1] + Y
dp = [0] + [-float('inf')] * n
cum_max = [0] * (n + 1)
for (i, (t, x, y)) in enumerate(zip(T[1:], X[1:], Y[1:])):
	max_dist = max(x - 1, r - x) + max(y - 1, r - y)
	if t - max_dist < 0:
		ind = 0
	else:
		ind = bisect_left(T, t - max_dist)
		dp[i + 1] = cum_max[ind - 1] + 1
	for j in range(i, max(-1, ind - 1), -1):
		if dp[j] < 0:
			continue
		dist = abs(X[i + 1] - X[j]) + abs(Y[i + 1] - Y[j])
		if dist <= T[i + 1] - T[j]:
			dp[i + 1] = max(dp[i + 1], dp[j] + 1)
			if dp[i + 1] > cum_max[j]:
				break
	cum_max[i + 1] = max(cum_max[i], dp[i + 1])
ans = max(dp)
print(ans)