Subway Signalling Error

The Stockholm subway system (in one of its lines) consists of two parallel tracks connected together at their endpoints. Under normal operation the trains run continuously at speed 1 (one distance unit per time unit) and are uniformly distributed – that is, a train passes any given point on a track at regular time intervals. However, due to a signalling error the trains on one line have become randomly distributed.

You, as the traffic controller, can control each train arbitrarily: at any moment you may order a train to pause and/or change its direction (if it changes direction it instantly switches to the other track). In other words, within a time T a train initially at position x can be repositioned to any location whose distance (along the track) is at most T (note that the tracks are cyclic – see below).

In a restored uniform distribution the trains are arranged in cyclic order along the line. In fact, if the length of each track is L then by identifying the two tracks (the endpoints being connected) the motion becomes equivalent to motion on a circle of circumference L. In normal operation the passage times at any fixed point would be exactly L/n apart, where n is the total number of trains. Thus one may describe the ideal configuration as an arithmetic progression modulo L. More precisely, for some offset r the target positions are:

r, r + L/n, r + 2·L/n, …, r + (n – 1)·L/n (all mod L)

Your task is to compute the minimum time T required such that by repositioning each train no more than T (using pauses and/or instantaneous reversals) the trains can be arranged so that, after suitable re‐labelling, the i-th train is at a location whose circular distance from (r + i·L/n mod L) is at most T. (It can be shown that an optimal assignment is obtained by matching the trains in sorted order with the target positions in cyclic order.)

Note: Although each train has an initial direction (R meaning it was originally on the lower track and moving to the right, and L meaning it was originally on the upper track and moving to the left), you are allowed to change direction at any time (and a change of direction automatically switches a train to the other track). Hence the initial direction has no effect on the reachability – each train may be moved to any position within distance T along the circle.

---

Input format:

• The first line contains two integers L and n, where L (1 ≤ L ≤ 10⁹) is the length of each track and n (1 ≤ n ≤ 1000) is the number of trains.
• Then follow n lines. Each of these lines contains an integer p (0 ≤ p ≤ L) and a character d. The integer p denotes the position of a train, and d is either R (meaning the train is initially on the lower track moving to the right) or L (meaning it is on the upper track moving to the left).

Output format:

• Output a single number – the minimum time T (in time units) required to be able to restore uniform distribution. Your answer will be accepted if its absolute or relative error does not exceed 10⁻⁶.

Explanation:

One may show that it is always optimal to match the trains in increasing order of their positions with an arithmetic progression of target positions (modulo L). Since each train can be moved at most T (in either direction), the condition for a feasible arrangement is that there exists a real number r such that for all i = 0, 1, …, n − 1 (after a proper cyclic ordering) we have

d_c( a[i], (r + i·L/n) mod L ) ≤ T,

where d_c(x, y) = min(|x − y|, L − |x − y|) denotes the circular distance. A standard transformation shows that the feasibility condition is equivalent to finding a cyclic shift of the sequence { a[i] − i·L/n } whose range is at most 2·T. Thus the answer is T = ½·(minimum range over all cyclic shifts).

For example, consider the sample below with L = 100 and n = 5. The trains are at positions 5 (R), 35 (L), 46 (L), 75 (L) and 85 (R). One feasible plan (not optimal) is to move the train originally at position 46 one unit to the left and then reverse its direction – this uses one unit of time. However, by optimally reassigning the trains the minimum time required is 5.000000 time units.

inputFormat

The first line contains two integers L and n.

Then follow n lines; each contains an integer p and a character d (R or L), separated by a space.

See the sample input for details.

outputFormat

Output a single number – the minimum time (in time units) required to restore uniform distribution. Print the answer with at least 6 digits after the decimal point.

sample

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

5.000000

</p>