#1000. WALL - Sửa hàng rào

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

NGUỒN: CONTEST LÀO CAI Lần 2 2017

Sau khi dựng xong nhà kho, Hải Dương quyết định dùng m 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ừ n 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ứ i có độ cao a_i (1≤i≤n) . 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ứ j có độ cao b_j (1≤j≤m) . 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 n (1≤n≤10^5) ;
  • Dòng tiếp theo chứa n số nguyên dương a_1,a_2,…,a_n (1≤a_i≤10^8,1≤i≤n) ;
  • Dòng tiếp theo chứa số nguyên dương m (1≤m≤10^5) ;
  • Dòng tiếp theo chứa m số nguyên dương b_1,b_2,…,b_m\ (1≤b_j≤10^8,1≤j≤m)

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 5 . Đây là một cách gia cố: a_1+b_2,a_2,a_3+b_3,a_4+b_6,a_5,a_6 , độ cao tương ứng của các thanh sau khi gia cố là: {5,5,5,5,7,5} . Do đó, độ cao của hàng rao là 5 .

Giới hạn:

  • 1≤n≤10^5; 1≤m≤10^5 ;
  • 1≤a_i≤10^8,1≤i≤n; 1≤b_j≤10^8,1≤j≤m