You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

一场比赛需要一个简单题。

题目描述

在一个 $n*n$ 的二维平面上，在某些时刻的某些点会出现一枚金币，具体的说，有 $m$ 次事件，对于第 $i$ 次事件，给出 $time_i,x_i,y_i$ ,表示在 $time_i$时刻的 $x_i,y_i$ 位置出现了一枚金币。注意，在 $time_i + 1$ 时刻这枚金币会消失。你想要在二维平面移动以收集金币，具体的说，在某一时刻，你和某一枚金币处于同一位置，你将获得这枚金币。你可以在每一时刻选择移动一格或者停在原地不动，移动一格是指将你的 $x$ 坐标或 $y$ 坐标 $\pm 1$ 。你的初始起点可以随意选定。请输出你能收集的最大金币数量。数据保证不会出现同一时刻同一地点存在两枚金币。

输入格式

第一行两个整数 $n,m$ 含义如题面所述。

接下来有 $m$ 行，每行三个整数 $time_i,x_i,y_i$ ,含义如题面所述。

输出格式

一行一个整数，表示你能收集到的最大金币数

2 2	         
1 1 1		
2 2 2

1

数据范围

对于 $10\%$ 的数据 $n=1,m\le5000,time_i\le1e9$，保证$time_i$不降。

对于另外 $30\%$ 的数据 $n\le100,m\le5000 ,time_i\le50$，保证$time_i$不降。

对于另外 $60\%$ 的数据 $n\le10^9,m\le5000,time_i\le10^9$，保证$time_i$不降。