Moles are animals that love to dig holes, but every once in a while, they like to poke their heads out of the ground to get some fresh air. Based on this characteristic, A-Niu has created a mole-whacking game: in an $n \times n$ grid, moles will appear in certain grid cells at certain times to get some air. You can control a robot to whack the moles. If a mole appears in a grid cell at time $i$ and the robot is also in the same grid cell, the mole will be whacked. At each time step, the robot can only move one cell or stay in its current position. The robot's movement is defined as moving from its current grid cell to an adjacent grid cell, i.e., from the grid cell at coordinates $(x, y)$ to one of the four grid cells $(x-1, y)$, $(x+1, y)$, $(x, y-1)$, or $(x, y+1)$. The robot cannot move outside the $n \times n$ grid. At the start of the game, you can freely choose the robot's initial position.

Given the times and locations where the moles appear over a period of time, write a program to enable the robot to whack as many moles as possible during this period.

Input

The first line contains $n$ ($n \le 1000$) and $m$ ($m \le 10000$), where $m$ represents the number of moles that appear during this period. The following $m$ lines each contain three data points: time, x, and y, indicating that a mole appears at the grid cell at row $x$ and column $y$ at time units after the game starts. The time values are given in increasing order. Note that multiple moles may appear at the same time, but only one mole can appear at the same location at the same time.

Output

The output contains only a single positive integer, representing the maximum number of moles that can be whacked.

Examples

Input 1

2 2
1 1 1
2 2 2

Output 1

1