Signal Failure

A subway line consists of two parallel rails of length m. On the upper rail, trains move from right to left; on the lower rail, trains move from left to right. When a train reaches an endpoint, it immediately moves to the other rail, reverses direction, and continues. This transfer takes no time.

During normal operation, every train moves at a constant speed of 1 cell per minute, and the trains are evenly distributed around the line. Therefore, trains pass any fixed point on the rail periodically. Ignore the time spent stopping at stations or boarding passengers.

After a failure, the trains are scattered arbitrarily on the rails. The control center wants to redistribute all trains evenly as quickly as possible, given their current positions. It may temporarily stop a train, and it may reverse a train's direction at any time. When a train reverses, it moves to the opposite rail at the same position.

The figure shows rails of length 100. The trains are at 5 (right), 35 (left), 46 (left), 75 (left), and 85 (right). One way to make the distribution even is to move the train at 46 by one cell and then reverse it, but that is not the fastest possible method.

The first line contains the rail length m and the number of trains n. Each of the next n lines contains a train's current position xi and direction. Direction L means the train is facing left, and R means it is facing right.

Print the minimum time needed to redistribute all trains evenly. An absolute or relative error of at most 10^{-6} is accepted.

• 100 ≤ m ≤ 100,000,000
• 1 ≤ n ≤ 100,000
• 0 ≤ xi ≤ m