Năm ngoái, một vài người bán xúc xích đã xếp hàng dọc theo một con phố, và họ có một thuật toán phức tạp để tự giãn cách nhau ra. Thật không may, thuật toán đó rất chậm và họ vẫn đang thực hiện nó. Tuy nhiên, mọi thứ vẫn chưa mất hết! Những người bán xúc xích đã có một kế hoạch: đã đến lúc thử một thuật toán mới!

Vấn đề là nhiều người bán có thể đang đứng quá gần nhau, và khi đó họ sẽ tranh giành khách hàng của nhau. Những người bán có thể di chuyển dọc theo con phố với tốc độ \(1\) mét/giây. Để tránh cản trở nhau, họ muốn đứng sao cho mọi cặp người bán cách nhau một khoảng ít nhất là \(D\) mét.

Hãy nhớ rằng con phố rất dài, vì vậy không có nguy cơ hết chỗ để di chuyển theo cả hai hướng. Cho biết vị trí bắt đầu của tất cả các người bán xúc xích, bạn nên tìm thời gian tối thiểu cần thiết trước khi tất cả các người bán được giãn cách (mỗi hai người bán cách nhau ít nhất \(D\) mét).

Dữ liệu vào

Mỗi điểm trên con phố được gắn nhãn bằng một con số, có thể là số dương, số âm hoặc số không. Một điểm có nhãn \(p\) nằm cách điểm có nhãn \(0\) là \(|p|\) mét về phía đông nếu \(p\) dương, và \(|p|\) mét về phía tây nếu \(p\) âm. Chúng tôi sẽ sử dụng hệ thống nhãn này để mô tả vị trí của các người bán trong tệp dữ liệu vào.

Dòng đầu tiên của dữ liệu vào chứa số lượng bộ test, \(T\). \(T\) bộ test tiếp theo. Mỗi bộ test bắt đầu bằng một dòng chứa số lượng điểm \(C\) có ít nhất một người bán xúc xích trong cấu hình bắt đầu và một số nguyên \(D\) -- khoảng cách tối thiểu họ muốn giãn cách. \(C\) dòng tiếp theo mỗi dòng chứa một cặp số nguyên \(P, V\) cách nhau bởi dấu cách, cho biết có \(V\) người bán tại điểm có nhãn \(P\).

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là lượng thời gian tối thiểu để những người bán giãn cách nhau trên con phố. Các câu trả lời có sai số tương đối hoặc tuyệt đối tối đa \(10^{-6}\) sẽ được chấp nhận.

Ràng buộc

• \(1 \le T \le 50\).
• Tất cả các giá trị \(P\) là số nguyên trong phạm vi \([-10^5, 10^5]\).
• Trong mỗi bộ test, tất cả các giá trị \(P\) là duy nhất và được đưa ra theo thứ tự tăng dần. Giới hạn về tổng các giá trị \(V\) được liệt kê bên dưới. Tất cả các giá trị \(V\) là số nguyên dương.

Phân nhóm

• Small dataset (Test set 1 - Visible):

  • \(1 \le D \le 5\).
  • \(1 \le C \le 20\).
  • Tổng tất cả các giá trị \(V\) trong một bộ test không vượt quá \(100\).

• Large dataset (Test set 2 - Hidden):

  • \(1 \le D \le 10^6\).
  • \(1 \le C \le 200\).
  • Tổng tất cả các giá trị \(V\) không vượt quá \(10^6\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
3 2
0 1
3 2
6 1
2 2
0 3
1 1

Case #1: 1.0
Case #2: 2.5

Nguồn

Google Code Jam 2011, Vòng 1B, bài Revenge of the Hot Dogs.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.