Bạn đang ở trên đỉnh Everest và muốn tận hưởng tất cả những đường mòn tuyệt đẹp nơi đây. Tuy nhiên, kinh nghiệm cho bạn biết rằng leo núi một mình rất nguy hiểm — bạn có thể lạc trong bóng tối. Vì vậy, bạn muốn đi vào những giờ đã định trước cùng hướng dẫn viên.

Trên núi có \(C\) trại, đánh số từ \(1\) đến \(C\), và có \(2C\) tour đi bộ đường dài một chiều, đánh số từ \(1\) đến \(2C\). Mỗi tour bắt đầu ở một trại, kết thúc ở một trại khác và không đi qua trại nào ở giữa. Everest thưa dân, công việc kinh doanh ế ẩm: có đúng hai tour khởi hành từ mỗi trại và đúng hai tour đến mỗi trại.

Mỗi tour chạy hằng ngày. Tour \(1\) và \(2\) xuất phát từ trại \(1\), tour \(3\) và \(4\) xuất phát từ trại \(2\), v.v.; tổng quát, tour \(2i-1\) và \(2i\) xuất phát từ trại \(i\). Tour thứ \(i\) kết thúc ở trại \(E_i\), khởi hành lúc giờ \(L_i\) và kéo dài đúng \(D_i\) giờ.

Hiện tại là giờ \(0\); các giờ trong ngày được đánh số từ \(0\) đến \(23\). Bạn đang ở trại \(1\) và muốn đi mỗi tour đúng một lần, cuối cùng trở lại trại \(1\). Không thể di chuyển giữa các trại bằng cách nào khác. Khi ở một trại, bạn có thể chờ bao nhiêu giờ tùy ý, kể cả \(0\), nhưng chỉ có thể bắt đầu tour đúng thời điểm nó khởi hành.

Sau khi xem lịch, bạn đã xác định chắc chắn có thể đạt mục tiêu, nhưng muốn hoàn thành nhanh nhất. Nếu chọn lộ trình tối ưu, bạn cần bao nhiêu giờ để đi hết mọi tour?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng số nguyên \(C\), số trại. Tiếp theo là \(2C\) dòng. Dòng thứ \(i\), đánh số từ \(1\), mô tả tour xuất phát từ trại \(\lfloor(i+1)/2\rfloor\) và chứa ba số nguyên \(E_i,L_i,D_i\) như trên. Định dạng này bảo đảm đúng hai tour xuất phát từ mỗi trại.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test, bắt đầu từ \(1\), và y là số giờ nhỏ nhất để đạt mục tiêu.

Ràng buộc

• \(1\le T\le100\).
• \(1\le E_i\le C\).
• \(E_i\ne\lceil i/2\rceil\) với mọi \(i\); không tour nào bắt đầu và kết thúc cùng một trại.
• Với mỗi trại \(i\), có đúng hai chỉ số \(j\) sao cho \(E_j=i\); đúng hai tour kết thúc tại mỗi trại.
• \(0\le L_i\le23\).
• \(1\le D_i\le1000\).
• Tồn tại ít nhất một lộ trình bắt đầu và kết thúc tại trại \(1\), dùng mỗi tour đúng một lần.

Phân nhóm

Test Set 1 (Visible): \(2\le C\le15\).

Test Set 2 (Hidden): \(2\le C\le1000\).

Đ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
2
2 1 5
2 0 3
1 4 4
1 6 3
4
3 0 24
2 0 24
4 0 24
4 0 24
2 0 24
1 0 24
3 0 24
1 0 24

Case #1: 32
Case #2: 192

Nguồn

Google Code Jam 2017, Vòng 3, bài Mountain Tour.

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