Chirox đi sửa hàng rào
View as PDFSau khi trở nên túng quẫn vì mua skin game, ~Chirox~ phải về quê chăn rau và nuôi gà. Nhưng cuộc đời ~Chirox~ có mấy khi được suôn sẻ, những tên trộm luôn nhòm ngó khu vườn nhà ~Chirox~. Sau nhiều lần bị trộm, ~Chirox~ quyết định phải sửa lại hàng rào cho cao lên để những tên trộm chân ngắn không thể trèo vào được.
Kế hoạch của ~Chirox~ như sau: ~Chirox~ sẽ chở một chồng gỗ và lần lượt đi qua từng thanh hàng rào từ trái qua phải, sau đó nếu cảm thấy thanh hàng rào này cần phải được sửa cho cao lên, ~Chirox~ sẽ lấy một miếng gỗ mới phù hợp trong chồng gỗ để bổ sung cho thanh hàng rào đó. Chiều cao của thanh rào sau khi được sửa sẽ bằng chiều cao thanh rào ban đầu cộng cho chiều dài của miếng gỗ mới. Tuy nhiên, vì là một người lười biếng, sau khi đã chọn 1 miếng gỗ phù hợp cho thanh hàng rào đó thì những miếng gỗ ở bên trên sẽ bị ~Chirox~ quăng đi (vì lười xếp lại). Lười biếng là vậy, ~Chirox~ vẫn muốn hàng rào của mình được sửa một cách tốt nhất.
Gọi độ cao của hàng rào là chiều cao của thanh rào thấp nhất trong hàng rào. Bạn hãy giúp ~Chirox~ lười biếng sửa hàng rào một cách lười biếng nhưng vẫn sửa được cho độ cao hàng rào là lớn nhất có thể.
*Input: *
- Dòng đầu tiên chứa số nguyên dương ~n~ là số thanh rào trong hàng rào của ~Chirox~
- Dòng thứ hai chứa ~n~ số nguyên dương ~a_i (i ≤ n)~, tương ứng là chiều cao ban đầu của thanh rào thứ ~i~
- Dòng thứ ba chứa số nguyên dương ~m~ là số ván gỗ trong chồng gỗ của ~Chirox~
- Dòng thứ tư chứa ~m~ số nguyên dương ~b_1, b_1,..., b_m~ lần lượt là chiều dài của các ván gỗ trong chồng gỗ từ trên xuống dưới
*Output: * Một dòng duy nhất chứa một số nguyên là độ cao hàng rào lớn nhất mà ~Chirox~ có thể sửa được bằng cách sửa lười biếng ấy
Giới hạn:
- ~1 ≤ n, m ≤ 5.10^5~
- ~1 ≤ a[i] ≤ 10^8, b[i] ≤ 10^8~
Ví dụ:
Input
6
2 5 4 1 7 5
7
2 3 1 3 2 4 6
Output
5
*Giải thích: * Một cách sửa thỏa mãn:
- Sửa thanh rào thứ ~1~ bằng ván gỗ thứ ~2~, chiều cao mới của thanh rào là ~2 + 3 = 5~
- Sửa thanh rào thứ ~3~ bằng ván gỗ thứ ~4~, chiều cao mới của thanh rào là ~4 + 3 = 7~
- Sửa thanh rào thứ ~4~ bằng ván gỗ thứ ~7~, chiều cao mới của thanh rào là ~1 + 6 = 7~
- Vậy chiều cao của các thanh rào sau cùng là: ~5, 5, 7, 7, 7, 5 => 5~ là chiều cao của thanh rào thấp nhất ~=>~ 5 là độ cao của hàng rào và là lớn nhất có thể đạt được
Comments
my time has come
Đã update test!