Road Work

Per repairs roads. The work happens on roads that have one lane in each direction. When Per closes the lane in one direction, all traffic has to use the other lane, so only one direction of travel is allowed at any moment. Per is often assigned to direct the traffic through that lane.

No car moves before Per gives it a "go" signal, and every car drives through the maintained segment at the same speed. Because there is only one lane, the cars going in one direction must leave the segment before a car from the other direction can enter. For safety, cars driving in the same direction have to keep a distance of at least 3 seconds between each other.

For example, if cars A and B arrive at the west endpoint at second 10, Per lets them go at second 10 and second 13 at the earliest, in the order they arrived. If passing the segment takes 8 seconds and car C arrives at the east endpoint at second 17, then car C waits 4 seconds and gets its signal at second 21.

Drivers get irritated with Per because they think they stand still for too long. Per has logged how long each driver can bear to wait before getting irritated. One day, to evaluate his own work, Per wrote down when the cars arrived at the two endpoints of the segment. Per's question is this: what is the least number of drivers that can be irritated? A driver gets irritated if the time between the moment the driver arrives at the maintained segment and the moment the car is actually given the go signal exceeds that driver's irritation time limit.

The first line contains two integers $t$ and $n$ ($4 \le t \le 180$, $1 \le n \le 250$), where $t$ is the time in seconds a car needs to pass the segment under maintenance and $n$ is the total number of cars arriving at the segment. Each of the following $n$ lines describes one car:

• one character $d$, which is W for a car arriving at the west endpoint of the segment and E for a car arriving at the east endpoint;
• two integers $a$ and $r$ ($0 \le a < 86400$, $0 \le r \le 3600$), where $a$ is the arrival time in seconds after midnight and $r$ is the time in seconds it takes the driver to get irritated.

The cars arrive in the order given in the input and they cannot overtake each other. In particular, a car whose driver is already irritated stays in the queue until it finally receives the go signal and passes the maintained segment.

Print one line with the least possible number of irritated drivers.