Revenge of the Hot Dogs (Small)

Last year several hot dog vendors lined up along a street and ran an algorithm to spread themselves out. The algorithm was so slow that it is still running, so the vendors decided to try a new one.

The trouble is that vendors standing too close to each other take each other's business. A vendor moves along the street at 1 meter per second. To stay out of each other's way, they want to stand so that every pair of vendors is at least $D$ meters apart.

The street is very long, so no vendor ever runs out of room in either direction. Given the starting positions of all vendors, find the minimum time needed until every pair of vendors is at least $D$ meters apart. Several vendors can start at the same point, and each vendor can move east or west.

Every point of the street carries an integer label. The point labeled $p$ is $|p|$ meters east of the point labeled $0$ when $p$ is positive, and $|p|$ meters west of it when $p$ is negative.

The first line contains the number of test cases $T$. Each test case begins with a line holding the number of points $C$ that have at least one vendor in the starting configuration and the minimum distance $D$ the vendors want between them, separated by a space. The next $C$ lines each hold two space separated integers $P$ and $V$, meaning that $V$ vendors stand at the point labeled $P$.

Limits

• $1 \le T \le 50$
• $1 \le C \le 20$
• $1 \le D \le 5$
• $-10^5 \le P \le 10^5$
• Within one test case all $P$ values are distinct and are given in increasing order.
• $V$ is a positive integer, and the sum of the $V$ values in one test case is at most $100$.

For each test case print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum time until every pair of vendors is at least $D$ meters apart.

The answer is always a multiple of $0.5$, so print it with exactly one digit after the decimal point. An answer of $1$ prints as 1.0, and an answer of $2.5$ prints as 2.5.