Ferry Safe Crossing

Ferries crossing the Strait of Gibraltar must choose a safe time to begin their north‐bound journey such that during the entire crossing of each shipping lane, no ship touches the crossing line. The strait is modeled as several parallel lanes (numbered 1 through N) running in the east–west direction. Ships in each lane move at a constant speed in one direction – either eastbound or westbound – and they may have different lengths. In each lane, all ships move in the same direction. A ferry crosses the strait by moving north along a fixed vertical line. The ferry is so small that its dimensions are negligible; however, once it starts to cross a lane it must complete that lane during a fixed time interval T. In other words, if the ferry starts crossing at time X then it will cross lane i during the time interval [X + (i-1)T, X + iT].

For each ship in a lane, its position on the east–west axis is given at time zero along with its length. The crossing line is assumed to be the vertical line at x = 0. For a ship in a lane the conditions are described as follows:

• If the lane is eastbound, a ship with front position p and length l will have its unsafe time interval defined in latex by $$[A,B] = \Big[\frac{-p}{s},\;\frac{l-p}{s}\Big],$$ where s is the ship's speed.
• If the lane is westbound, a ship with front position p and length l has its unsafe interval given by $$[A,B] = \Big[\frac{p}{s},\;\frac{p+l}{s}\Big].$$

For a ship in lane i with unsafe interval \([A, B]\), the ferry starting at time X will conflict with the ship if its crossing interval for lane i, i.e. \([X+(i-1)T, X+iT]\), overlaps \([A,B]\). This happens when:

Equivalently, the ferry’s start time X is forbidden (for that ship) if:

Your task is to, given an observation window \([0, W]\) and data for all lanes, compute the largest continuous time interval within \([0,W]\) during which the ferry may start its crossing safely (i.e. for every lane, its crossing interval does not conflict with any ship’s unsafe interval). If there is no safe interval, output 0. The answer should be printed as a floating–point number rounded to 6 decimal places.

inputFormat

The input begins with a line containing three numbers: the number of lanes N (an integer), the crossing time per lane T (a positive real number), and the observation window upper bound W (a positive real number).

This is followed by N lane descriptions. Each lane description starts with a line containing a character d (either 'E' for eastbound or 'W' for westbound), the ship speed s (a positive real number), and an integer m indicating the number of ships in that lane. Then, m lines follow, each containing two real numbers: the ship's front position p and its length l.

Note: For eastbound lanes, the unsafe interval for a ship is \([ -p/s,\;(l-p)/s ]\), and for westbound lanes it is \([ p/s,\;(p+l)/s ]\). For each ship in lane i, the ferry cannot start at times in the interval \([A - iT,\; B - (i-1)T]\) (with \([A,B]\) being the unsafe interval for that ship) if it is to avoid any collision.

outputFormat

Output a single line containing the length of the largest continuous safe start interval within \([0,W]\), rounded to 6 decimal places. If no safe interval exists, output 0.000000.

sample

2 2 10
E 1 1
-3 2
W 1 1
4 2

5.000000