핫도그 장수의 반격 (작은 입력)

작년에 핫도그 장수 여러 명이 한 거리에 늘어서서 서로 간격을 벌리는 알고리즘을 돌렸다. 그 알고리즘이 너무 느린 탓에 아직도 끝나지 않았다. 그래서 장수들은 새 알고리즘을 쓰기로 했다.

문제는 여러 장수가 너무 가까이 붙어서 장사하면 서로 손님을 빼앗는다는 점이다. 장수는 거리를 따라 초속 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 20$
• $1 \le D \le 5$
• $-10^5 \le P \le 10^5$
• 한 테스트 케이스 안에서 $P$ 값은 모두 다르고 증가하는 순서로 주어진다.
• $V$는 양의 정수이고, 한 테스트 케이스의 $V$ 값의 합은 $100$ 이하이다.

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

정답은 항상 $0.5$의 배수이므로 소수점 아래 한 자리까지 출력한다. 정답이 $1$이면 1.0, $2.5$이면 2.5로 출력한다.