Problem E
Physics Experiment
Input: Standard Input

Output: Standard Output

Experiments are a very significant part of various branches of Physics such as light, sound or heat. Now in a world famous underground physics laboratory, a heat experiment is being carried on. They have gas particles filled in an otherwise empty straight-lined glass rod. All the particles are on the same horizontal plane & able to travel only left or right. To be more specific, a particle can move 1 unit distance per second on either direction or may not move at all.

Now, for the experiment, one side of the glass rod is heated by a burner, let's assume this will always be the left side. The heat is immediately transferred to the left most particle and at the same time, the particles start to move. Remember that, after this time any particle can move 1 unit distance to right or left every second or lay unmoved at a particular second. We shall also assume that, at the start of the experiment all particles were unheated & not moving. An important characteristics of this gas particles are, multiple of them can reside in the same place.

Heat transfer takes place by radiation between two particles. If an unheated particle, at some point comes at a distance of less than or equal to D units of a heated particle, it becomes heated. There is no heat loss inside the experimental environment, so a particle once heated, will be heated forever. Given the initial position of all the particles, you are to determine the minimum amount of seconds required to have all the particles heated.

Input

The first line of every test case contains an integer N (1<=N<=10000), the number of particles in the glass rod. Each of the next N lines has a floating point number, the unit distance of a particle from the left side of the glass rod, given to 3 digits after the decimal point. The distances will always be non-negative and less than or equal to 10^7. The last line of the case will be another floating point value, D (0<=D<=1000), as described in the statement. D will have 3 digits after the decimal as well. The last test case will be followed by a line with a single 0 denoting the end of input. This line should not be processed.

Output

For every test case, print a line of of the form, “Case X: Y”, where X is the serial number of output (starting from 1) and Y is the minimum time in seconds required to heat all the particles. The result, Y should be printed upto 3 digits after decimal point. Output having difference by no more than 0.001 with the official output shall be considered as correct.

Sample Input Output for Sample Input

5 0.000 3.000 4.500 7.000 10.000 2.500 2 0.000 6.000 3.000 0

Case 1: 0.250 Case 2: 1.500

Problem setter: Mohammad Mahmudur Rahman

Special Thanks: Manzurur Rahman Khan