Groundwater Reserves

Groundwater is the word for the lakes, ponds, and rivers that form underground. When it rains, part of the water percolates through the layers of soil and rock and ends up in one of those bodies of water somewhere below the surface. Plants with long enough roots draw on groundwater when no rain has fallen for a while, and people reach it by drilling wells deep enough. A drought leaves the reserves partly or completely empty, and refilling them takes a lot of rain.

In this problem the reserves start completely empty, and you compute how far rainfall refills them. The rock at the bottom of the reservoir is given as a polyline through the points $(x_i, y_i)$. The $x$ coordinates increase strictly from $x_1 = 0$ to $x_n = 1$, and no segment is exactly horizontal, so the direction in which the water landing at a point flows is always determined. A point with a larger $y$ sits higher up, and the sky is at $y = +\infty$. Infinitely high walls stand at $x = 0$ and $x = 1$, so no water leaves the map.

Rain falls vertically and evenly over the whole width. A rate of $r$ means that $r$ units of water hit each unit of horizontal length per unit of time, so during a duration $t$ the horizontal interval $[a, b]$ receives $r \times t \times (b - a)$ units of water. Water that lands on a slope runs downhill into a basin. Once a basin is full, the surplus flows over the lower of the two ridges that bound it and into the next basin. The reservoir starts completely empty.

Find the highest level the water surface reaches anywhere in the reservoir during the $t$ units of time it rains.

The first line is the number $K$ of data sets. The $K$ data sets follow, each in this form.

The first line of a data set holds three numbers $n$, $r$, $t$. The integer $n$ is the number of points in the reservoir bottom contour, $2 \le n \le 50$. The double $r$ is the rate at which rain falls, $0.0 \le r \le 1000.0$. The double $t$ is the duration for which rain falls, $0.0 \le t \le 1000.0$.

The next line holds $2n$ doubles describing the points of the bottom contour in the order $x_1\ y_1\ x_2\ y_2\ \dots\ x_n\ y_n$. It is guaranteed that $0 = x_1 < x_2 < x_3 < \dots < x_n = 1$ and $-1000.0 \le y_i \le 1000.0$. Two neighboring points never share the same $y$ value.

For each data set, print Data Set x: on a line by itself, where $x$ is its number counting from 1.

On the next line, print the highest level the water surface reached anywhere in the reservoir, rounded to exactly two digits after the decimal point. A basin that holds no water counts as having its surface at the height of its floor.

Print a blank line after each data set.