Sau khi dựng xong nhà kho, Hải Dương quyết định dùng tấm gỗ còn thừa gia cố hàng rào của vườn rau ngăn không cho gà vào phá và giao công việc này cho Hải Phong. Nhiệm vụ của Hải Phong là đóng thêm vào các tấm ván hàng rào để có hàng rào mới càng cao càng tốt. Hàng rào được ghép từ tấm gỗ cùng độ rộng như nhau và bằng độ rộng của các tấm gỗ còn thừa, tấm thứ có độ cao . Hải Phong xếp các tấm gỗ còn thừa lên xe ba gác để kéo đi, các tấm gỗ được xếp thành một chồng, tính từ trên xuống tấm thứ có độ cao . Hải Phong kéo xe ba gác đi dọc theo hàng rào. Đến một tấm nào đó muốn gia cố, Hải Phong sẽ lấy một tấm gỗ từ xe đóng tiếp lên tấm gỗ trên hàng rào và độ cao mới của tấm này trên hàng rào là tổng độ cao của tấm cũ và tấm mới đóng thêm. Hải Phong chỉ đóng thêm một tấm mới vào tấm cũ để đảm bảo độ chắc chắn của hàng rào. Hải Phong có thể lấy tấm trên cùng của xe hoặc vất ra khỏi xe một số tấm cho đến khi gặp tấm gỗ vừa ý. Để đảm bảo sức khỏe và thời gian, Hải Phong không xếp lại các tấm gỗ bị bỏ ra vào xe và cũng không quay lại lấy những tấm bị loại.
Yêu cầu: Hãy xác định độ cao lớn nhất có thể đạt được của hàng rào sau khi gia cố. Độ cao của hàng rào được tính bằng độ cao của tấm gỗ thấp nhất trên hàng rào.
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên dương ;
Dòng tiếp theo chứa số nguyên dương ;
Dòng tiếp theo chứa số nguyên dương ;
Dòng tiếp theo chứa số nguyên dương
Các số trên một dòng của input file được ghi cách nhau bởi dấu cách.
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là độ cao lớn nhất có thể đạt được của hàng rào sau khi gia cố.
Ví dụ:
Dữ liệu vào:
6
2 5 4 1 7 5
7
2 3 1 3 2 4 6
Dữ liệu ra:
5
Giải thích
Có nhiều cách gia cố hàng rào để đạt độ cao bằng . Đây là một cách gia cố: , độ cao tương ứng của các thanh sau khi gia cố là: . Do đó, độ cao của hàng rao là .
