Minimizing Patrol Encounters

A highway has n checkpoints (numbered 1 to n) in a straight line with no branches. The distance between any two consecutive checkpoints is 10 km. All vehicles on this highway must travel at speeds between 60 km/h and 120 km/h. Moreover, vehicles may only change their speeds when they are at a checkpoint.

The patrol department dispatches patrol cars according to the following method: at a given time T_i, a patrol car is sent from checkpoint n_i and drives with constant speed to checkpoint n_i+1, taking exactly t_i seconds for the journey. Note that for such a patrol car the speed is exactly 10×3600/t_i km/h (which is guaranteed to be between 60 and 120 km/h).

A meeting between two vehicles on the same segment is defined in one of two ways:

• They meet if one overtakes the other (i.e. their relative order on the segment changes).
• They meet if they arrive at a checkpoint at exactly the same time (note: if two vehicles depart from the same checkpoint at the same time, that does not count as a meeting).

A target vehicle departs from checkpoint 1 exactly at 6:00 (i.e. 21600 seconds after midnight) and must travel through all n-1 segments to reach checkpoint n. On each segment between checkpoints, the target vehicle may choose any constant speed, which is equivalent to choosing a travel time L (in seconds) for that 10 km segment, where L must satisfy

$$300 \le L \le 600,$$

since 60 km/h requires 600 seconds per segment and 120 km/h requires 300 seconds per segment. (In fact, the vehicle's speed on the segment will be \(\frac{10 \times 3600}{L}\) km/h.)

For each segment the target vehicle’s departure time is fixed (it is the arrival time at the previous checkpoint), but the vehicle can choose its travel time on that segment. For a given segment with departure time D (in seconds) and chosen travel time L, the target vehicle is on that segment from time D to D+L. Meanwhile, a patrol car on that segment departs at time T and is on the segment until time T+t (with its travel time provided as input). Their journeys on the segment may overlap. If they overlap, then to avoid a meeting the following must hold:

• If the target vehicle departs before the patrol car (i.e. D < T), then the target vehicle must be fast enough so that it reaches the next checkpoint before being caught; mathematically, this is achieved if and only if L \le t.
• If the target vehicle departs after the patrol car (i.e. D > T), then the target vehicle must be slow enough so that it never overtakes the patrol car; that is, if and only if L \ge t.
• If the target and patrol car depart at the same time (i.e. D = T), no meeting occurs regardless of their speeds.

Also, if the target vehicle’s journey on the segment does not overlap with the patrol car’s journey at all (i.e. either D+L \le T or T+t \le D), then they will not meet.

Your task is to help the patrol department determine the minimum total number of meetings that the target vehicle will have with any patrol car across its entire journey from checkpoint 1 to checkpoint n, assuming that the target vehicle may choose its travel time on each segment optimally.

---

Input Format

The first line contains two integers n and m, where n is the total number of checkpoints and m is the number of patrol events.

Each of the following m lines contains three integers: T, k and t. Here, T is the departure time (in seconds) of a patrol car from checkpoint k, and t is the time in seconds it takes for that patrol car to travel to checkpoint k+1. It is guaranteed that 1 \le k < n and that the patrol car’s speed (i.e. \(10 \times 3600/t\)) is between 60 km/h and 120 km/h.

---

Output Format

Output a single integer, the minimum total number of meetings between the target vehicle and the patrol vehicles.

inputFormat

The first line contains two space‐separated integers n and m.

Each of the next m lines contains three integers: T, k, and t, representing a patrol event starting at checkpoint k at time T with a travel time of t seconds for the segment from k to k+1.

The target vehicle starts at checkpoint 1 exactly at 21600 seconds (6:00 a.m.) and must traverse each of the n-1 segments by choosing a travel time (in seconds) between 300 and 600.

outputFormat

Output a single integer: the minimum number of encounters the target vehicle will have with patrol cars.

sample

2 1
21600 1 600

0

</p>