Bathysphere

The Bathysphere is a spherical deep-sea submersible which was unpowered and lowered into the ocean on a cable, and was used to conduct a series of dives under the sea. The Bathysphere was designed for studying undersea wildlife.

The Bathysphere was conducted from the deck of a ship. After counted, the ship should not move, so choosing the position where the Bathysphere was conducted is important.

A group of scientists want to study the secrets of undersea world along the equator, and they would like to use the Bathysphere. They want to choose the position where the Bathysphere can dive as deep as possible. Before conducting the Bathysphere, they have a map of the seabed, which tell them the shape of the seabed. They draw a line on the equator of the map to mark where they will release the Bathysphere, as a number axis. Suppose the axis is draw from 0 to L. But when they release the Bathysphere, they can't know where they are accurately, i.e., if they choose position x to release the Bathysphere, the real position will distribute between x-d and x+d with an equal probability, where d is given. The objective of the scientists is very simple, i.e., to maximize the expected depth.

For the ease of presentation, the shape of the seabed is described as a poly line. Given N points ) , ( X_i,Y_i ) as the vertices, where X_i and Y_i indicate the position and the depth of the i-th vertex, respectively, the ploy line is composed of the line segments that connect consecutive vertices.

The first line contains an integer T (1 ≤ T ≤ 25), the number of test cases.

Then T test cases follow. In each test case, the first line contains two integers N (2 ≤ N ≤ 2*10^5) and L (2 ≤ L ≤ 10^9), as described above. Then N lines follow, each line contains two integer X_i and Y_i (1≤i≤N, 0≤ Y_i ≤10^9), where point ( X_i,Y_i ) is a vertex of the ploy line. It is assumed that X₁ == 0 and X_n == L and X_i < X_i+1 for 1 ≤ i < N. Then the following line contains one integer d (0 ≤ d ≤ L/2), as described above.

For each test case, choose a position between d and L-d, both inclusive, to conducted the Bathysphere, and calculate the expected depth. Output the expected depth in a line, rounded to 3 digits after the decimal point.

2
3 10
0 3
4 10
10 1
5
3 10
0 3
4 10
10 1
1

5.900
9.192

2013 Asia Regional Changchun