Do sự xâm nhập ồ ạt của các gián điệp nước ngoài, an ninh quốc gia đang trong tình trạng khủng hoảng cao độ. Nếu gián điệp nắm giữ bằng chứng phạm tội của gián điệp , ta nói có thể tố giác . Một số gián điệp chấp nhận hối lộ, chỉ cần đưa cho họ một lượng đô la nhất định, họ sẵn sàng giao nộp toàn bộ tình báo mà họ nắm giữ. Vì vậy, nếu chúng ta có thể mua chuộc một số gián điệp, chúng ta có thể kiểm soát từng phần tử trong mạng lưới gián điệp. Bởi vì một khi bắt giữ được một gián điệp, toàn bộ tình báo hắn nắm giữ (bao gồm bằng chứng về các gián điệp khác) sẽ thuộc về chúng ta, từ đó có thể bắt giữ các gián điệp mới và nắm thêm tình báo mới.
Cơ quan phản gián cung cấp một tài liệu, bao gồm tất cả các gián điệp đã biết chấp nhận hối lộ và số tiền cụ thể họ yêu cầu. Đồng thời chúng ta cũng biết gián điệp nào nắm giữ tài liệu về gián điệp nào. Giả sử có tổng cộng gián điệp, được đánh số từ đến .
Dựa trên tài liệu này, hãy xác định xem chúng ta có thể kiểm soát toàn bộ các gián điệp hay không. Nếu có, hãy tìm số tiền tối thiểu cần chi trả. Nếu không, hãy xuất ra một gián điệp không thể bị kiểm soát.
Dữ liệu:
Dòng đầu tiên chứa một số nguyên .
Dòng thứ hai là số nguyên , biểu thị số người sẵn sàng nhận hối lộ.
dòng tiếp theo, mỗi dòng gồm hai số nguyên: số đầu là mã số của gián điệp chịu nhận hối lộ, số thứ hai là số tiền cần để mua chuộc anh ta.
Tiếp theo là một dòng chứa số nguyên . Sau đó là dòng, mỗi dòng chứa hai số nguyên dương biểu thị cặp , nghĩa là gián điệp nắm giữ bằng chứng về gián điệp .
Kết quả:
Nếu có thể kiểm soát tất cả gián điệp, dòng đầu tiên xuất YES, và dòng thứ hai xuất chi phí hối lộ tối thiểu.
Nếu không, dòng đầu tiên xuất NO, và dòng thứ hai xuất mã số của gián điệp không thể bị kiểm soát (chọn gián điệp có mã số nhỏ nhất trong số những người không thể kiểm soát).
Ví dụ:
Dữ liệu:
2
1
2 512
2
1 2
2 1
Kết quả:
YES
512
Giới hạn: . Chi phí mua chuộc mỗi người là số không âm và không vượt quá .
