Baltic Olympiad in Informatics: 2009 Day 1, Problem 3

The subway in Stockholm consists of several subway lines. In this problem, we will consider one line in particular and the problems that quite often happen on it when there's been a "signaling error".

A subway line can be seen as two parallel rails connected at the endpoints. In the upper rail, the trains are going from right to left and in the lower rail, the trains are going from left to right. When a train reaches an endpoint of a rail, it switches to the opposite rail and changes direction. This switch is instantaneous and takes no time.

During normal traffic, the traffic flow is continuous and the trains are moving at a constant speed (~1~ length unit per time unit). The trains are evenly distributed; that is, at any given position on a rail, the trains will appear periodically. We will assume that the time it takes for a train to stop and pick up passengers is negligible.

Now, because of signaling errors, the trains have been randomly distributed along the line. Your job as the traffic manager is to, as fast as possible, ensure that the trains will be evenly distributed along the line again. Write a program that, given the current train positions, calculates how fast this can be achieved. You are allowed to order the trains to temporarily stop, and/or change direction anywhere along the line. If a train changes direction, it will move from one rail to the other.

Both rails have a length of ~100~. In the upper example the trains are positioned at ~5~ (direction right), ~35~ (left), ~46~ (left), ~75~ (left) and ~85~ (right). One way to make the trains evenly distributed is for the train at position ~46~ to travel one unit to the left and then change direction. This takes one time unit. However, this is not the optimal solution; see sample input 1 below.

Input Specification

The first line in the input contains two integers separated by a single space, the length ~m~ of the subway rails, and the number ~n~ of trains on the line. Then follows ~n~ lines each describing the current position of a train. This will be given as an integer ~x_i~ and a direction (L for left, R for right), separated by a single space.

Output Specification

Output a single line containing the shortest time it takes to make the trains evenly distributed. Your program should have an absolute precision error of at most ~10^{-6}~.

Sample Input 1

100 5
5 R
35 L
46 L
75 L
85 R

Sample Output 1

0.5

Sample Input 2

100 8
9 L
15 R
41 L
33 L
81 R
33 R
100 L
97 R

Sample Output 2

15.500000

Constraints

~100 \le m \le 100\,000\,000~

~1 \le n \le 100\,000~

~0 \le x_i \le m~

Grading

For test cases worth 50% of the total score, ~n \le 200~.