Cho một tập hợp gồm vật phẩm. Mỗi vật phẩm () được đặc trưng bởi hai thông tin:
Một số nguyên dương : Chi phí để sở hữu vật phẩm.
Một chuỗi ký tự : Tập các thuộc tính mà vật phẩm đó sở hữu. Chuỗi chỉ chứa tối đa 3 loại ký tự thuộc tập , các ký tự trong không trùng lặp và không nhất thiết phải theo thứ tự.
Nhiệm vụ của bạn là chọn ra một tập con các vật phẩm sao cho hợp tất cả các chuỗi của các vật phẩm được chọn chứa đầy đủ cả 3 ký tự 'A', 'B' và 'C', đồng thời tổng chi phí là nhỏ nhất.
Dữ liệu:
Dòng đầu tiên chứa số nguyên ().
dòng tiếp theo, mỗi dòng chứa một số nguyên () và một chuỗi ().
Kết quả:
In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất tìm được. Nếu không có cách nào để thu thập đủ cả 3 loại thuộc tính, in ra .
Ví dụ:
Dữ liệu:
4
5 C
6 B
16 ABC
2 A
Kết quả:
13
Giải thích:
Có hai phương án khả thi:
Chọn vật phẩm thứ 3 (có đủ 'A', 'B', 'C') với chi phí: .
Chọn vật phẩm thứ 1, 2 và 4 để có đủ {'C', 'B', 'A'} với chi phí: .
Chi phí nhỏ nhất là .
Dữ liệu:
3
10 A
11 AA
13 AB
Kết quả:
-1
Giới hạn:
Subtask #1 (10% số điểm): .
Subtask #2 (15% số điểm): Độ dài với mọi ().
Subtask #3 (20% số điểm): .
Subtask #4 (25% số điểm): .
Subtask #5 (30% số điểm): Không có ràng buộc bổ sung ().
