Bạn đang ở trong một sân bay, đứng tại điểm 0. Một hành lang có chiều dài \(X\) dẫn đến cổng khởi hành, nơi máy bay của bạn sắp cất cánh. Có những băng chuyền chuyển động trong hành lang, mỗi băng chuyền di chuyển với tốc độ \(w_i\). Khi bạn đi bộ hoặc chạy trên một trong những băng chuyền đó, bạn sẽ di chuyển với tốc độ (tốc độ của bạn + \(w_i\)). Các băng chuyền không thay đổi vị trí; chúng chỉ giúp bạn di chuyển nhanh hơn. Các băng chuyền không chồng lấn lên nhau: tại bất kỳ điểm nào trên hành lang, có tối đa một băng chuyền, nhưng một băng chuyền có thể bắt đầu tại điểm mà một băng chuyền khác kết thúc.

Tốc độ đi bộ bình thường của bạn là \(S\). Tuy nhiên, bạn lo lắng rằng mình có thể không kịp chuyến bay, vì vậy bạn có thể chạy một chút - bạn có thể chạy với tốc độ \(R\) trong tổng cộng tối đa \(t\) giây. Bạn không nhất thiết phải chạy trong \(t\) giây liên tục: bạn có thể chia \(t\) giây này thành bất kỳ số lượng khoảng thời gian nào, hoặc thậm chí không sử dụng hết chúng.

Bạn mất bao lâu để đến được cổng, giả sử bạn chọn khi nào đi bộ và khi nào chạy để đến nơi sớm nhất có thể?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Mỗi bộ thử nghiệm bắt đầu bằng một dòng chứa năm số nguyên: \(X\) (chiều dài hành lang, tính bằng mét), \(S\) (tốc độ đi bộ của bạn, tính bằng mét trên giây), \(R\) (tốc độ chạy của bạn, tính bằng mét trên giây), \(t\) (thời gian chạy tối đa, tính bằng giây) và \(N\) (số lượng băng chuyền).

Mỗi dòng trong số \(N\) dòng tiếp theo chứa ba số nguyên: \(B_i\), \(E_i\) và \(w_i\) - điểm bắt đầu và điểm kết thúc của băng chuyền (tính bằng mét từ điểm xuất phát của bạn) và tốc độ của băng chuyền (tính bằng mét trên giây).

Dữ liệu ra

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

Ràng buộc

• \(1 \le T \le 40\).
• \(1 \le S < R \le 100\).
• \(1 \le w_i \le 100\).
• \(0 \le B_i < E_i \le X\).
• \(E_i \le B_{i+1}\).

Phân nhóm

• Small dataset (Test set 1):

  • \(1 \le t \le 100\).
  • \(1 \le X \le 100\).
  • \(1 \le N \le 20\).

• Large dataset (Test set 2):

  • \(1 \le t \le 10^6\).
  • \(1 \le X \le 10^6\).
  • \(1 \le N \le 1000\).

Đ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ụ

3
10 1 4 1 2
4 6 1
6 9 2
12 1 2 4 1
6 12 1
20 1 3 20 5
0 4 5
4 8 4
8 12 3
12 16 2
16 20 1

Case #1: 4.000000
Case #2: 5.500000
Case #3: 3.538095238

Nguồn

Google Code Jam 2011, Vòng 2, bài Airport Walkways.

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