Last year, several hot dog vendors were lined up along a street, and they had a tricky algorithm to spread themselves out. Unfortunately, the algorithm was very slow and they are still going. All is not lost though! The hot dog vendors have a plan: time to try a new algorithm!
The problem is that multiple vendors might be selling too close to each other, and then they will take each other's business. The vendors can move along the street at 1 meter/second. To avoid interfering with each other, they want to stand so that every pair of them is separated by a distance of at least meters.
Remember that the street is really long, so there is no danger of running out of space to move in either direction. Given the starting positions of all hot dog vendors, you should find the minimum time they need before all the vendors are separated (each two vendors are at least meters apart from each other).
输入格式
Each point of the street is labeled with a number, positive, negative or zero. A point labeled is meters east of the point labeled if is positive, and meters west of the point labeled if is negative. We will use this labeling system to describe the positions of the vendors in the input file.
The first line of the input file contains the number of cases, . test cases follow. Each case begins with a line containing the number of points that have at least one hot dog vendor in the starting configuration and an integer -- the minimum distance they want to spread out to. The next lines each contain a pair of space-separated integers , , indicating that there are vendors at the point labeled .
输出格式
For each test case, output one line containing "Case #: ", where is the case number (starting from 1) and is the minimum amount of time it will take for the vendors to spread out apart on the street. Answers with relative or absolute error of at most will be accepted.
样例
样例输入 1
2
3 2
0 1
3 2
6 1
2 2
0 3
1 1
样例输出 1
数据范围与提示
Limits
.
All the values are integers in the range .
Within each test case all values are distinct and given in an increasing order. The limit on the sum of values is listed below. All the values are positive integers.
Small dataset (15 Pts, Test set 1 - Visible)
.
The sum of all the values in one test case does not exceed .
