핫도그 장수의 역습 (라지)

긴 거리 하나를 따라 핫도그 장수 여러 명이 서 있다. 서로 너무 가까운 곳에서 팔면 같은 손님을 나눠 갖게 되므로, 장수들은 충분히 떨어져 자리를 잡으려고 한다.

장수는 거리를 따라 초속 1미터로 움직인다. 모두 동시에 움직이며, 어느 두 사람 사이의 거리도 $D$미터 이상이 되는 순간 멈춘다.

거리는 아주 길어서 어느 방향으로 가든 움직일 공간이 모자랄 일은 없다. 장수들의 처음 위치가 주어질 때, 모든 장수가 서로 $D$미터 이상 떨어지는 데 필요한 최소 시간을 구하시오.

거리의 각 지점에는 정수 번호가 붙어 있다. 번호가 $p$인 지점은 $p$가 양수이면 번호 $0$인 지점에서 동쪽으로 $|p|$미터, $p$가 음수이면 서쪽으로 $|p|$미터 떨어진 곳이다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 장수가 한 명 이상 서 있는 지점의 개수 $C$와 장수들이 확보하려는 최소 거리 $D$가 공백으로 구분되어 주어진다. 이어지는 $C$개 줄에는 각각 두 정수 $P$와 $V$가 공백으로 구분되어 주어지며, 번호가 $P$인 지점에 장수가 $V$명 서 있다는 뜻이다.

제한

• $1 \le T \le 50$
• $1 \le C \le 200$
• $1 \le D \le 10^6$
• $P$는 $-10^5$ 이상 $10^5$ 이하의 정수이다.
• 한 테스트 케이스 안에서 $P$ 값은 모두 다르고, 증가하는 순서로 주어진다.
• $V$는 양의 정수이고, 한 테스트 케이스의 $V$ 값을 모두 더한 값은 $10^6$을 넘지 않는다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 모든 장수가 서로 $D$미터 이상 떨어지는 데 걸리는 최소 시간이다.

$y$는 항상 $0.5$의 배수이므로 소수점 아래 한 자리까지 출력한다. 답이 3이면 3.0, 답이 2.5이면 2.5를 출력한다.