Bạn cần thuê một số người để sơn một hàng rào. Hàng rào gồm \(10000\) đoạn liên tiếp, được đánh số từ \(1\) đến \(10000\).

Bạn nhận được một số lời đề nghị từ các thợ sơn. Mỗi thợ sơn đề nghị sơn một đoạn liên tiếp của hàng rào bằng một màu cụ thể. Bạn cần chấp nhận một tập hợp các lời đề nghị sao cho:

• Mọi đoạn của hàng rào đều được sơn.
• Có tối đa \(3\) màu được sử dụng để sơn hàng rào.

Nếu có thể thỏa mãn hai yêu cầu này, hãy tìm số lượng lời đề nghị tối thiểu mà bạn phải chấp nhận.

Dữ liệu vào

• Một dòng chứa số nguyên \(T\), số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu:

• Một dòng chứa số nguyên \(N\), số lượng lời đề nghị.
• \(N\) dòng, mỗi dòng cho một lời đề nghị, chứa "\(C\) \(A\) \(B\)" trong đó \(C\) là tên màu (một chuỗi in hoa tối đa \(10\) ký tự), \(A\) là đoạn đầu tiên và \(B\) là đoạn cuối cùng được sơn. \(1 \le A \le B \le 10000\).

Dữ liệu ra

• \(T\) dòng, mỗi dòng cho một bộ dữ liệu theo thứ tự xuất hiện, chứa chuỗi "Case #\(X\): \(Y\)", trong đó \(X\) là số thứ tự bộ dữ liệu, và \(Y\) là số lượng lời đề nghị tối thiểu cần chấp nhận, hoặc "Case #\(X\): IMPOSSIBLE" nếu không có tập hợp lời đề nghị nào thỏa mãn.

Ràng buộc

• \(1 \le T \le 50\).

Phân nhóm

• Tập dữ liệu nhỏ (Test set 1 - Visible): \(1 \le N \le 10\).
• Tập dữ liệu lớn (Test set 2 - Hidden): \(1 \le N \le 300\).

Đ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
2
BLUE 1 5000
RED 5001 10000
3
BLUE 1 6000
RED 2000 8000
WHITE 7000 10000
4
BLUE 1 3000
RED 2000 5000
ORANGE 4000 8000
GREEN 7000 10000
2
BLUE 1 4000
RED 4002 10000
3
BLUE 1 6000
RED 4000 10000
ORANGE 3000 8000

Case #1: 2
Case #2: 3
Case #3: IMPOSSIBLE
Case #4: IMPOSSIBLE
Case #5: 2

Nguồn

Google Code Jam 2008, Vòng bán kết EMEA, bài Painting a Fence.

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