Cho một hệ thống gồm hang động. Hang động thứ () có thực thể với các chỉ số sức mạnh tương ứng là .
Để vượt qua hang động , bạn phải đánh bại các thực thể theo đúng thứ tự từ đến . Giả sử sức mạnh hiện tại của bạn là :
Để đánh bại thực thể thứ trong hang , điều kiện cần là .
Sau khi đánh bại một thực thể, sức mạnh của bạn sẽ tăng thêm đơn vị ().
Bạn có quyền quyết định thứ tự khám phá các hang động, nhưng một khi đã vào một hang, bạn phải đánh bại toàn bộ các thực thể trong hang đó trước khi sang hang khác.
Yêu cầu: Tìm sức mạnh khởi đầu () nhỏ nhất để có thể hoàn thành việc khám phá toàn bộ hang động.
Dữ liệu:
Dòng đầu tiên chứa số nguyên () — số lượng hang động.
dòng tiếp theo, mỗi dòng mô tả một hang động: số nguyên () theo sau là số nguyên ().
Tổng giá trị của tất cả các không vượt quá ().
Kết quả:
Một số nguyên duy nhất là sức mạnh khởi đầu tối thiểu cần thiết.
Ví dụ:
Dữ liệu:
2
2 10 15
1 12
Kết quả:
14
Giải thích:
Thứ tự tối ưu là đi Hang 2 trước, sau đó đến Hang 1.
Với :
Vào Hang 2: (thỏa mãn), sức mạnh tăng lên .
Vào Hang 1: (thỏa mãn), (thỏa mãn), sức mạnh cuối cùng là .
Nếu chọn , sau khi xong Hang 2, sức mạnh , không đủ để vượt qua thực thể thứ hai của Hang 1 (yêu cầu ).
Dữ liệu:
1
3 10 20 30
Kết quả:
29
Giới hạn:
Subtask #1 (20% số điểm): .
Subtask #2 (15% số điểm): .
Subtask #3 (20% số điểm): với mọi .
Subtask #4 (20% số điểm): và .
Subtask #5 (25% số điểm): Không có ràng buộc bổ sung.
