Tàu điện ngầm Stockholm có nhiều tuyến. Ta xét một tuyến gồm hai đường ray song song nối với nhau ở hai đầu. Trên đường ray phía trên, tàu chạy từ phải sang trái; trên đường ray phía dưới, tàu chạy từ trái sang phải. Khi đến đầu đường ray, tàu lập tức chuyển sang đường ray kia và đổi hướng; thao tác này không tốn thời gian.

Trong điều kiện bình thường, các tàu chạy liên tục với vận tốc một đơn vị độ dài trong một đơn vị thời gian và được phân bố đều: tại một vị trí bất kỳ trên đường ray, tàu xuất hiện theo chu kỳ. Thời gian dừng để đón khách được xem là không đáng kể.

Sau một lỗi tín hiệu, các tàu bị phân bố ngẫu nhiên dọc tuyến. Bạn được phép ra lệnh cho tàu tạm dừng và/hoặc đổi hướng tại bất kỳ vị trí nào. Khi đổi hướng, tàu chuyển sang đường ray kia.

Hãy tính thời gian ngắn nhất để các tàu lại được phân bố đều.

Trong hình, mỗi đường ray dài \(100\). Ở cấu hình trên, các tàu lần lượt ở vị trí \(5\) (sang phải), \(35\) (sang trái), \(46\) (sang trái), \(75\) (sang trái) và \(85\) (sang phải). Có thể cho tàu tại \(46\) đi một đơn vị sang trái rồi đổi hướng để đạt cấu hình đều trong một đơn vị thời gian, nhưng đây chưa phải phương án tối ưu; xem Ví dụ 1.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(m,n\): chiều dài mỗi đường ray và số tàu. Mỗi dòng trong \(n\) dòng tiếp theo chứa một số nguyên \(x_i\) và một ký tự chỉ hướng, L nếu tàu đang đi sang trái hoặc R nếu tàu đang đi sang phải.

Dữ liệu ra

In ra thời gian ngắn nhất để các tàu được phân bố đều. Sai số tuyệt đối không được vượt quá \(10^{-6}\).

Ràng buộc

Phân nhóm

• 50% số điểm: \(n\le 200\).

Ví dụ

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

0.5

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

15.500000