Một quốc gia cần xây dựng các cây cầu để phát triển cơ sở hạ tầng. Có địa điểm tiềm năng để xây cầu. Tại mỗi địa điểm , có thể xây một cây cầu với chi phí và độ vững chắc .
Chính phủ đã quyết định sẽ cấp ngân sách để xây dựng chính xác cây cầu. Để đảm bảo chất lượng công trình đồng đều, họ muốn tìm một phương án xây dựng sao cho độ vững chắc của cây cầu yếu nhất trong số cây cầu được chọn là lớn nhất có thể.
Hãy giúp họ tìm ra độ vững chắc tối thiểu lớn nhất có thể này.
Dữ liệu:
Dòng đầu tiên chứa ba số nguyên (, ).
dòng tiếp theo, mỗi dòng chứa hai số nguyên () là chi phí và độ vững chắc của cây cầu tại địa điểm .
Kết quả: Một số nguyên duy nhất là độ vững chắc tối thiểu lớn nhất có thể của cây cầu được chọn. Nếu không có cách nào để xây cây cầu trong ngân sách cho phép, in ra .
Ví dụ:
Dữ liệu:
5 3 20
8 10
5 12
10 8
4 15
12 13
Kết quả:
10
Giải thích:
Bài toán yêu cầu tìm giá trị lớn nhất (độ vững chắc tối thiểu) sao cho ta có thể chọn ra cây cầu có độ vững chắc với tổng chi phí không vượt quá .
Nếu ta thử với : Các cây cầu có độ vững chắc là (chi phí 5, độ vững chắc 12), (chi phí 4, độ vững chắc 15), và (chi phí 12, độ vững chắc 13). Có đúng 3 cây cầu. Tổng chi phí của chúng là , lớn hơn ngân sách . Do đó, ta không thể đặt mức vững chắc tối thiểu là .
Nếu ta thử với : Các cây cầu có độ vững chắc là (8, 10), (5, 12), (4, 15), (12, 13). Có 4 cây cầu thỏa mãn. Để chi phí là nhỏ nhất, ta chọn 3 cây cầu rẻ nhất trong số này là (8, 10), (5, 12), (4, 15). Tổng chi phí là , nhỏ hơn ngân sách . Do đó, mức là khả thi.
Vì không khả thi và khả thi, đáp án lớn nhất có thể là .
