Trước khi tốt nghiệp Đại học Lập trình viên Tuyệt vời, sinh viên theo truyền thống phải thực hiện một số "yêu cầu tốt nghiệp". Một trong số đó là lái xe ngược chiều quanh một vòng xuyến giao thông. Với hầu hết mọi người, điều này đã đủ điên rồ rồi, nhưng như một thử thách thêm, bạn muốn xem liệu mình có thể đi ngược chiều quanh vòng xuyến nhiều vòng mà không dừng lại hay không.

Vòng xuyến giao thông bao gồm \(N\) giao lộ, cách đều nhau quanh vòng tròn. Một chiếc xe bình thường sẽ đi vào vòng xuyến tại một giao lộ, và sau mỗi giây, nó sẽ di chuyển đến giao lộ tiếp theo theo chiều ngược chiều kim đồng hồ, cho đến khi cuối cùng nó đến đích và rời đi.

Bạn đã quan sát các xe đi vào và rời khỏi vòng xuyến trong \(X\) giây. Với mỗi xe, bạn ghi lại thời điểm nó vào vòng xuyến, cũng như các giao lộ nó vào và ra. Tất cả các xe đều di chuyển ngược chiều kim đồng hồ với tốc độ 1 giao lộ mỗi giây. Mỗi chiếc xe bạn quan sát đều rời khỏi vòng xuyến trước khi quay trở lại giao lộ mà nó đã đi vào. Có nhiều làn đường trên vòng xuyến, vì vậy nhiều xe có thể chiếm cùng một vị trí tại cùng một thời điểm.

Nếu bạn đã lập kế hoạch vừa đúng, bạn có thể lái xe theo chiều kim đồng hồ trong vòng xuyến trong bao lâu? Bạn phải vào vòng xuyến tại một thời điểm nguyên \(>= 0\), rời đi tại thời điểm \(<= X\), và một khi bạn đã rời đi, bạn không được phép quay lại. Khi ở trong vòng xuyến, bạn phải di chuyển theo chiều kim đồng hồ với tốc độ 1 giao lộ mỗi giây. Bạn muốn chơi an toàn (theo cách an toàn nhất mà việc lái xe ngược chiều trên vòng xuyến có thể có), vì vậy bạn không bao giờ được chạm hoặc đi ngang qua một chiếc xe khác. Cụ thể, bạn không thể rời vòng xuyến tại một giao lộ mà một chiếc xe khác đang đi vào tại cùng thời điểm đó, và bạn không thể vào vòng xuyến tại một giao lộ mà một chiếc xe khác đang rời đi tại cùng thời điểm đó. Bạn có thể chọn thời điểm và địa điểm để vào và rời khỏi vòng xuyến.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo.
Dòng đầu tiên của mỗi bộ test mô tả số lượng xe \(C\) mà bạn đã quan sát. Dòng thứ hai chứa hai số nguyên, \(X\) và \(N\) — thời gian (tính bằng giây) mà bạn quan sát vòng xuyến, và số lượng giao lộ trên vòng xuyến. \(C\) dòng tiếp theo mô tả các xe bạn đã thấy. Mỗi dòng chứa ba số nguyên \(s_i\), \(e_i\) và \(t_i\) — giao lộ mà xe đi vào vòng xuyến, giao lộ mà nó rời đi và thời điểm nó đi vào. Các giao lộ được đánh số từ 1 đến \(N\), theo chiều ngược chiều kim đồng hồ (nghĩa là giao lộ số 2 là giao lộ tiếp theo theo chiều ngược chiều kim đồng hồ từ số 1).

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à số giây tối đa bạn có thể di chuyển trên vòng xuyến. Lưu ý rằng y có thể bằng 0 cả trong trường hợp bạn không thể vào vòng xuyến và trong trường hợp bạn có thể vào, nhưng không thể di chuyển dù chỉ một giao lộ.

Hãy nhớ rằng bạn được yêu cầu vào vòng xuyến tại một thời điểm được biểu thị bằng một số nguyên giây — bạn phải vào tại một thời điểm nguyên, và do đó đến mỗi giao lộ tại một thời điểm nguyên.

Ràng buộc

• \(1 \le T \le 100\)
• \(1 \le s_i, e_i \le N\)
• \(s_i \neq e_i\)
• \(0 \le t_i\)
• Mỗi chiếc xe được quan sát đều rời khỏi vòng xuyến tại thời điểm \(X\) hoặc sớm hơn.

Phân nhóm

• Small dataset (Test set 1 - Visible): \(3 \le N \le 10, 1 \le X \le 10, 0 \le C \le 10\).
• Large dataset (Test set 2 - Hidden): \(3 \le N \le 10^{10}, 1 \le X \le 10^{10}, 0 \le C \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ụ

5
1
3 4
1 4 0
6
3 5
5 2 0
5 1 2
1 3 0
1 2 2
2 3 0
3 4 0
3
2 3
1 3 0
2 1 0
3 2 0
0
6 4
1
2 3
1 3 0

Case #1: 1
Case #2: 2
Case #3: 0
Case #4: 6
Case #5: 0

Nguồn

Google Code Jam 2013, Chung kết thế giới, bài Graduation Requirements.

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