D. Dangerous Driving
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Womais is taking a road trip through the fictional country of Muigleb. Unfortunately, he is late to his destination and would like to shave some time off his trip – but he is also scared of speeding and getting caught by the vigilant Muiglebian police. Highways in Muigleb have two lanes: the left lane and the right lane. Everybody in the right lane drives at the speed of 100 km/h, which is the Muiglebian speed limit. Cars in the left lane may drive at arbitrary speeds (even above the speed limit), subject to the following constraint: no car can drive faster than the car in front of it. Every car $$$c$$$ driving in the left lane will have an internal speed preference $$$s_c$$$. Then, if a car is driving in the left lane, its speed at any given moment will be equal to $$$\min(s_c, v)$$$, where $$$v$$$ is the speed of the car in front of it or $$$+\infty$$$ if there is no such car. To drive quickly and avoid getting pulled over, Womais will drive according to the following algorithm:

  • If there is at least one car in the left lane, and the last car in the left lane is driving faster than 100 km/h, Womais will drive in the left lane behind the last car, with the speed equal to its speed.
  • Otherwise, Womais will drive in the right lane at the speed of 100 km/h.
When Womais switches from the right lane to the left, he always ends up behind all the cars currently in the left lane. You may assume that all lane and speed changes are instantaneous When Womais starts his journey, the left lane is empty. Outside of Womais's movements, the following two types of events happen on the road:
  • A car currently in the left lane switches over to the right lane.
  • A car currently in the right lane switches over to the left lane with some internal speed preference, ending up in front of all the cars currently in the left lane (note that this is different from what happens when Womais switches from the right lane to the left; he ends up behind all the cars in the left lane).
Given the information about other cars behavior and internal speed preferences, find out how long it will take for Womais to complete his journey.
Input

The first line of the input will contain two positive integers $$$d, n$$$ ($$$1 \leq d \leq {10}^9$$$, $$$0 \leq n \leq 2\cdot {10}^5$$$) – the length of the road trip in kilometers and the number of events to follow.

The $$$i$$$-th of the following $$$n$$$ lines will contain two positive integers $$$t_i, m_i$$$ ($$$1 \leq t_i, m_i \leq {10}^9$$$) and a character $$$c_i \in \{\texttt{L}, \texttt{R}\}$$$. If $$$c_i$$$ is $$$\texttt{L}$$$, the line will also contain a positive integer $$$s_i$$$ ($$$1 \leq s_i \leq {10}^9$$$). Here $$$t_i$$$ is the time in seconds of the $$$i$$$-th event (Womais's journey starts at time 0), $$$m_i$$$ is the unique identifier of the car involved in event $$$i$$$. The two cases for $$$c_i$$$ are as follows:

  • If $$$c_i$$$ is $$$\texttt{R}$$$, car $$$m_i$$$ is switching from the left lane to the right lane. It is guaranteed that car $$$m_i$$$ was in the left lane just before this event.
  • If $$$c_i$$$ is $$$\texttt{L}$$$, car $$$m_i$$$ is switching from the right lane to the left lane. This car's new internal speed preference is given as $$$s_i$$$, measured in km/h. It is guaranteed that car $$$m_i$$$ was in the right lane just before this event.

It is guaranteed that $$$t_i$$$ are strictly increasing.

Output

The only line of output should contain a single integer, which is the number of seconds it will take Womais to drive $$$d$$$ km from the start of his journey, rounded up.

Example
Input
1000 3
10000 1 L 150
15000 2 L 125
20000 2 R
Output
28167
Note

In sample case 1, Womais is driving in the right lane with the speed of 100 km/h for the first 10000 seconds. At 10000s car 1 switches from right to left and Womais switches behind it, both of them driving at 150 km/h. At 15000s car 2 switches to the left in front of car 1, and both car 1 and Womais slow down to 125 km/h. At 20000s car 2 goes back to the right lane, and car 1 and Womais both speed back up to 150 km/h.