Whack-A-Mole Robot

Problem Description:

A mole is an animal that loves digging tunnels, but every once in a while it emerges above ground to get some fresh air. Inspired by this behavior, Aniu has developed a whack-a-mole game. In an (n \times n) grid, at specific time instances, a mole appears in one of the grid cells. You control a robot that can move one cell per time unit (up, down, left, or right) or remain stationary. The robot’s movement from a cell ((i,j)) is restricted to its adjacent cells: ((i-1,j)), ((i+1,j)), ((i,j-1)), or ((i,j+1)), and it cannot leave the grid. The game starts at time (0), and you may choose the robot’s initial position arbitrarily.

If at time (t) a mole appears in a cell and the robot is located in the same cell, the mole is whacked. Given the time and location of each mole appearance over a period, write a program to determine the maximum number of moles that can be whacked by controlling the robot optimally.

inputFormat

Input:

The first line contains two integers (n) and (m), where (n) is the size of the grid and (m) is the number of moles. The following (m) lines each contain three integers (t), (r) and (c) indicating that a mole appears at time (t) in the cell at row (r) and column (c). It is guaranteed that (1 \le r,c \le n) and that the times (t) are given in strictly increasing order.

outputFormat

Output:

Output a single integer: the maximum number of moles that can be whacked by the optimal movement of the robot.

sample

5 3
1 2 2
3 2 3
6 5 5

2