Maximum Packages Delivered

You are given a city represented by an n × n grid and k packages to deliver. Each package is described by six integers:

• pickup time (\(t_p\))
• pickup coordinates (\(x_p, y_p\))
• delivery time (\(t_d\))
• delivery coordinates (\(x_d, y_d\))

Each package must be picked up at or after its pickup time and delivered by its delivery time. The travel time between any two points is determined by the Manhattan distance, given by the formula \[ d((x_1,y_1),(x_2,y_2)) = |x_1 - x_2| + |y_1 - y_2| \] .

Your task is to determine the maximum number of packages that can be delivered in sequence such that the delivery of one package can serve as the starting point for the subsequent package. In other words, if you deliver package j before package i, then the condition \[ t_{p_i} \geq t_{p_j} + d((x_{d_j},y_{d_j}), (x_{p_i},y_{p_i})) \] must hold.

Note: You can choose to start with any package and the packages are not necessarily given in sorted order.

inputFormat

The first line contains two integers n and k where n represents the size of the grid (n × n) and k is the number of packages.

The following k lines each contain 6 space-separated integers:

• pickup time \(t_p\)
• pickup coordinate \(x_p\)
• pickup coordinate \(y_p\)
• delivery time \(t_d\)
• delivery coordinate \(x_d\)
• delivery coordinate \(y_d\)

It is guaranteed that all numbers are positive integers.

outputFormat

Output a single integer: the maximum number of packages that can be delivered sequentially while meeting the time constraints.

## sample

5 3
2 1 2 10 3 3
4 5 1 16 2 4
9 2 5 20 4 4

2