Proud Penguin

Time limit3sMemory limit256 MB

Summary

Distribute at most W units of water into level pools along a polygonal track to minimize the tallest uphill stretch penguins must climb.

Level: Hard8 of 10
Topics: Binary search, Greedy, Geometry
Solved: No attempts yet

Problem

Proud Penguin (PP) is one of the busiest attractions in the city. It specializes in the arctic, so visitors see fish, seals, whales and penguins. The penguins drew such crowds that PP decided to build a new area for them to play in.

The new area is a long, narrow track of climbs and slides. The ends are the highest points, so a trip always starts with a slide. Penguins enter at one end and reach the other by waddling, swimming and sliding.

One question is left in the planning stage. How should PP spread the water along the track? Penguins are lazy, so PP wants the highest climb to be as low as possible. The board also capped the amount of water, to keep maintenance cheap.

You are given the height of the track at evenly spaced points and the amount of water available. Find the lowest possible height of the highest climb the penguins are left with.

Figure 1: measuring the height of climbs

The track and the water

The cross section of the track is the polyline through the points $(0, a_0), (1, a_1), \dots, (N, a_N)$ . The track is one unit wide and runs in a straight line between two neighbouring points.

Water runs downhill, so the surface of one pool is level and every piece of ground below that level is under water. The two ends have height 100 and no other point is higher, so no water leaves the track. Water is measured by cross-section area, and the areas of all pools add up to at most $W$ .

Climbs

After the water is poured, the surface is the ground where it is dry and the water level where it is flooded. A climb is a maximal stretch of that surface along which the height keeps rising, and the height of the climb is the height at its top minus the height at its bottom. A flat stretch ends a climb. A climb can therefore start at a water line, and level ground between two points of equal height ends a climb as well. Penguins travel in both directions, so climbs that rise to the left and climbs that rise to the right both count.

Make the highest climb as low as you can and print its height.

Input

The first line contains the number of test cases $T$ . The first line of each test case contains the length of the track $N$ and the amount of water available $W$ . The next line contains $N+1$ integers $a_0, a_1, \dots, a_N$ , where $a_0$ is the height at the left end, $a_1$ is the height one unit from the left end, and $a_N$ is the height at the right end.

$0 < T \le 100$
$0 < N \le 10\,000$
$0 \le W \le 1\,000\,000$
$0 \le a_i \le 100$
$a_0 = a_N = 100$

Output

For each test case, print on one line the lowest possible height of the highest climb, rounded to four digits after the decimal point. In every test case the answer is farther than $10^{-5}$ from a rounding boundary, so computing it to an accuracy of $10^{-6}$ is enough.

Examples3

Example 1

Input

2
2 0
100 34 100
5 25
100 70 90 60 75 100

Expected output

66.0000
19.5732

Example 2

Input

4
1 0
100 100
2 0
100 0 100
2 25
100 0 100
3 0
100 100 100 100

Expected output

Example 3

Input

4
4 0
100 60 60 20 100
6 0
100 0 50 50 90 40 100
5 0
100 80 80 80 80 100
7 0
100 50 60 50 60 50 60 100

Expected output