Bạn đang cố gắng tổ chức một nhóm người trượt tuyết. Họ sẽ đến một ngọn núi lớn đã được thuê trọn ngày.

Trên núi có \(N\) điểm nghỉ được đánh số từ \(1\) đến \(N\), nối với nhau bởi \(N-1\) dốc trượt tuyết. Mỗi dốc bắt đầu tại một điểm nghỉ và đi thẳng đến một điểm nghỉ khác, không có dốc hay điểm nghỉ trung gian. Mỗi dốc chỉ có thể được đi theo một chiều.

Mỗi người trượt tuyết bắt đầu tại điểm nghỉ trên đỉnh núi, rồi đi qua một dốc để tới một điểm nghỉ khác. Từ đó, họ có thể tiếp tục đi qua một dốc khác để tới điểm nghỉ tiếp theo, và cứ như vậy. Khi tới điểm nghỉ đích, họ ngừng trượt tuyết trong ngày và đến nhà nghỉ uống ca cao nóng. Điểm nghỉ đích không được là điểm nghỉ trên đỉnh núi. Tuy nhiên, điểm nghỉ đích có thể là đầu của không, một hoặc nhiều dốc; nói cách khác, người trượt tuyết không nhất thiết phải tiếp tục dùng các dốc còn đi được cho tới khi không còn dốc nào. Họ luôn có thể cẩn thận đi bộ xuống phần còn lại của ngọn núi! Với mỗi điểm nghỉ, có đúng một dãy các dốc mà một người có thể dùng để đi từ điểm nghỉ trên đỉnh núi tới đó.

Mỗi dốc chỉ phục vụ được một tổng số người trượt tuyết nhất định trong một ngày; sau đó, tuyết trở nên quá gồ ghề để trượt. Ngoài ra, khu nghỉ dưỡng có thể thu phí hoặc trả thưởng cho mỗi người trên từng dốc họ đi qua. Mỗi dốc có thể có một mức giá khác nhau, và mỗi người phải trả giá của từng dốc mà mình đi. Giá của một dốc có thể dương, bằng không hoặc thậm chí âm; giá âm biểu thị khoản thưởng dành cho việc thử nghiệm dốc đó. Với vai trò người tổ chức, bạn trả mọi khoản phí và nhận mọi khoản thưởng thay cho cả nhóm. Nếu nhiều người dùng cùng một dốc, bạn phải trả phí hoặc nhận thưởng của dốc đó nhiều lần.

Tổng các khoản phí bạn trả trừ đi tổng các khoản thưởng bạn nhận là tổng chi phí của chuyến đi. Chi phí này có thể dương, bằng không hoặc âm. Chi phí âm nghĩa là bạn thực sự kiếm được tiền từ chuyến đi!

Với vai trò người tổ chức, bạn muốn xác định số người trượt tuyết lớn nhất có thể đưa lên núi. Đồng thời, trong số các chuyến đi có số người lớn nhất đó, bạn muốn tìm tổng chi phí nhỏ nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Sau đó là \(T\) bộ test. Dòng đầu tiên của mỗi bộ test chứa một số nguyên \(N\): số điểm nghỉ trên núi.

Mỗi dòng trong \(N-1\) dòng cuối của một bộ test mô tả một dốc bằng bốn số nguyên \(U_i\), \(V_i\), \(S_i\) và \(C_i\). Chúng lần lượt là điểm nghỉ bắt đầu của dốc, điểm nghỉ kết thúc của dốc, số người trượt tuyết tối đa mà dốc có thể phục vụ và giá của dốc cho mỗi người.

Điểm nghỉ trên đỉnh núi, nơi mọi người bắt đầu, luôn mang số \(1\).

Dữ liệu ra

Với mỗi bộ test, in một dòng theo định dạng Case #x: y z, trong đó x là số thứ tự bộ test (bắt đầu từ \(1\)), y là số người trượt tuyết lớn nhất và z là chi phí nhỏ nhất để y người, mỗi người trượt qua ít nhất một dốc.

Ràng buộc

• \(1 \le U_i \le N\) với mọi \(i\).
• \(2 \le V_i \le N\) với mọi \(i\). Không dốc nào có thể kết thúc tại điểm nghỉ trên đỉnh núi.
• \(U_i \ne V_i\) với mọi \(i\).
• \(1 \le S_i \le 10^5\) với mọi \(i\).
• \(-10^5 \le C_i \le 10^5\) với mọi \(i\).
• Với mọi điểm nghỉ \(r\), có đúng một dãy các dốc mà một người có thể dùng để đi từ điểm nghỉ trên đỉnh núi tới \(r\).

Phân nhóm

Test Set 1 (phản hồi kết quả đầy đủ)

• \(1 \le T \le 100\).
• \(2 \le N \le 1000\).

Test Set 2 (phản hồi kết quả ẩn)

• \(T = 17\).
• \(2 \le N \le 10^5\).

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

Case #1: 4 18
Case #2: 7 15

Nguồn

Google Code Jam 2020, Chung kết thế giới trực tuyến, bài Pack the Slopes.

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