C. Тяжелая работа папарацци
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы папарацци, работающий на Манхэттене.

На Манхэттене есть $$$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$$$-я знаменитость будет на перекрестке $$$(x_i, y_i)$$$ ровно через $$$t_i$$$ минут (и она останется там на очень короткое время, так что вы можете сфотографировать ее только в том случае, если на $$$t_i$$$-й минуте вы находитесь на перекрестке $$$(x_i, y_i)$$$). Вы очень хорошо справляетесь со своей работой, поэтому можете делать снимки мгновенно. Известно, что $$$t_i < t_{i+1}$$$ для любого $$$i=1,2,\ldots, n-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$$$ минут.

Гарантируется, что $$$t_i<t_{i+1}$$$ для каждого $$$i=1,2,\ldots, n-1$$$.

Выходные данные

Выведите одно целое число  — максимальное количество знаменитостей, которые вы сможете сфотографировать.

Примеры
Входные данные
10 1
11 6 8
Выходные данные
0
Входные данные
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
Выходные данные
4
Входные данные
10 4
1 2 1
5 10 9
13 8 8
15 9 9
Выходные данные
1
Входные данные
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
Выходные данные
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$$$.