Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

Ремонт забора

(Время: 2 сек. Память: 16 Мб Сложность: 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.TXTOUTPUT.TXT
13
10 5 10
1
5
10
26
2 5 4 1 7 5
7
2 3 1 3 2 4 6
5

Система оценивания

Решения, работающие для H ≤ 100, будут оцениваться в 25 баллов.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2005 / 2006
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014 7-8 классы
 2013 / 2014 9-11 классы
 2014 / 2015 7-8 классы
 2014 / 2015 9-11 классы
 2015 / 2016 7-8 классы
 2015 / 2016 9-11 классы
 2016 / 2017 7-8 классы
 2016 / 2017 9-11 классы
 2017 / 2018 7-8 классы
 2017 / 2018 9-11 классы
 2018 / 2019 7-8 классы
 2018 / 2019 9-11 классы
 2019 / 2020 7-8 классы
 2019 / 2020 9-11 классы
 2020 / 2021 7-8 классы
 2020 / 2021 9-11 классы
 2021 / 2022 7-8 классы
 2021 / 2022 9-11 классы
 A. Остаток от деления
 B. Газонокосильщик
 C. Предложение
 D. Бесконечный поезд
 E. Ремонт забора

Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru