핫도그의 복수

작년에 여러 핫도그 판매상이 길을 따라 줄지어 있었고, 서로 간격을 벌리기 위한 까다로운 알고리즘을 사용했다. 안타깝게도 그 알고리즘은 매우 느렸고, 그들은 아직도 이동하고 있다. 하지만 아직 희망은 있다! 핫도그 판매상들에게 계획이 있다. 새로운 알고리즘을 시도할 때다!

문제는 여러 판매상이 서로 너무 가까이에서 장사할 수도 있으며, 그러면 서로의 손님을 빼앗게 된다는 것이다. 판매상들은 길을 따라 초당 1미터의 속도로 이동할 수 있다. 서로 방해하지 않기 위해, 그들은 모든 판매상 쌍 사이의 거리가 적어도 D미터가 되도록 서고 싶어 한다.

길은 매우 길어서 어느 방향으로 이동하든 공간이 부족해질 위험은 없다는 점을 기억하라. 모든 핫도그 판매상의 시작 위치가 주어질 때, 모든 판매상이 서로 떨어지는 데 필요한 최소 시간을 구해야 한다(임의의 두 판매상 사이의 거리가 적어도 D미터여야 한다).

제한

1 ≤ T ≤ 50. 모든 P 값은 [-$10^{5}$, $10^{5}$] 범위의 정수이다. 각 테스트 케이스 안에서 모든 P 값은 서로 다르며 증가하는 순서로 주어진다. V 값의 합에 대한 제한은 아래에 제시되어 있다. 모든 V 값은 양의 정수이다. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ D ≤ 5 1 ≤ C ≤ 20. 하나의 테스트 케이스에서 모든 V 값의 합은 100을 초과하지 않는다. 시간 제한: 30초.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ D ≤ $10^{6}$ 1 ≤ C ≤ 200. 모든 V 값의 합은 $10^{6}$을 초과하지 않는다. 시간 제한: 60초.

길의 각 지점에는 양수, 음수 또는 영인 수가 붙어 있다. p가 양수이면 p가 붙은 지점은 0이 붙은 지점에서 동쪽으로 |p|미터 떨어져 있고, p가 음수이면 0이 붙은 지점에서 서쪽으로 |p|미터 떨어져 있다. 입력 파일에서 판매상의 위치를 설명할 때 이 표기 체계를 사용한다.

입력 파일의 첫 번째 줄에는 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 케이스는 초기 배치에서 핫도그 판매상이 적어도 하나 있는 지점의 수 C와, 그들이 서로 벌리고자 하는 최소 거리인 정수 D가 포함된 줄로 시작한다. 다음 C개의 줄에는 각각 공백으로 구분된 정수 쌍 P, V가 주어지며, 이는 P가 붙은 지점에 V명의 판매상이 있음을 나타낸다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 (1부터 시작하는) 케이스 번호이고, y는 판매상들이 길에서 서로 떨어지는 데 걸리는 최소 시간이다. 상대 오차 또는 절대 오차가 최대 10^{-6}인 답은 정답으로 인정된다.