Ремонт забора
(Время: 2 сек. Память: 32 Мб Сложность: 48%)
Илья работает плотником и перед ним стоит задача отремонтировать забор. Забор состоит из N сегментов, i-й из которых имеет высоту Ai. Илья располагает тележкой, на которой лежит стопка из M досок, j-я из которых имеет длину Bj.
Илья идет вдоль забора от первого сегмента к последнему и катит перед собой тележку с досками. Если он хочет увеличить высоту текущего сегмента, он может взять доску с тележки и прибить ее сверху. Тогда новая высота сегмента будет равна сумме изначальной высоты сегмента и длины прибитой доски.
Собираясь увеличить высоту сегмента забора, Илья поступает следующим образом. Он либо использует для увеличения сегмента верхнюю доску с тележки, либо выкидывает одну или несколько верхних досок с тележки и использует следующую доску. Илья никогда не прибивает больше одной доски к сегменту, не возвращается назад вдоль забора и никогда не подбирает ранее выкинутые доски.
Помогите Илье определить максимально возможную высоту забора после ремонта, если под высотой забора понимается высота самого низкого сегмента.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N – количество сегментов в заборе (1 ≤ N ≤ 105). Во второй строке содержатся N целых чисел A1, A2, … AN – высоты сегментов забора, перечисленные в том порядке, в котором мимо них пройдет Илья (1 ≤ Ai ≤ 108).
В третьей строке находится целое число M – количество досок на тележке (1 ≤ M ≤ 105). В четвертой строке содержатся M целых чисел B1, B2, … BM – длины досок на тележке, начиная с верхней (1 ≤ Bj ≤ 108).
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число H – максимальную возможную высоту забора после ремонта.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
10 5 10
1
5 | 10 |
| 2 | 6
2 5 4 1 7 5
7
2 3 1 3 2 4 6 | 5 |
Система оценивания
Решения, работающие для H ≤ 100, будут оцениваться в 25 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
