Description

Moles like to dig holes, but at certain times they will stick their heads out of the ground to breathe.

Based on this, Aniu designed a whack-a-mole game: on an $n \times n$ grid, at certain times a mole will pop up in some cell.

You can control a robot to whack moles. If at time $i$ a mole appears in some cell and the robot is in the same cell, then this mole will be killed by the robot.

At each time step, the robot can move by one cell or stay where it is. Moving means going from the current cell to an adjacent cell, i.e., from the cell with coordinates $(i, j)$ to one of $(i-1, j)$, $(i+1, j)$, $(i, j-1)$, $(i, j+1)$. The robot cannot leave the $n \times n$ grid.

At the start of the game, you may choose the robot’s initial position arbitrarily.

Given the times and locations where moles appear over a period of time, write a program to maximize the number of moles the robot can kill during this period.

Input Format

The first line contains $n, m\ (1 \le n \le 10^3, 1 \le m \le 10^4)$, where $m$ is the number of moles that appear during this period.

Each of the next $m$ lines contains three integers $t, x, y\ (1 \le t \le 2.5 \times 10^7, 1 \le x, y \le n)$, meaning that $t$ time units after the game starts, a mole appears in row $x$, column $y$.

The values of $t$ are given in nondecreasing order.

Note that multiple moles may appear at the same time, but at most one mole appears at the same location at the same time.

Output Format

Output a single non-negative integer, the maximum number of moles that can be killed.

2 2	         
1 1 1		
2 2 2

1

Hint

Translated by ChatGPT 5