e-olymp

Поликлиника

На прием к доктору каждый день приходит много людей. Каждый пациент находится на приеме целое число минут, однако разных пациентов доктор может принимать разное количество времени. Доктор начинает прием в момент времени t1 минут и заканчивает прием в момент времени t2 минут. Это означает, что любой пациент независимо от того, сколько времени его будет принимать доктор, может зайти на прием в моменты t1, t1 + 1, ..., t21. Заходить на прием к доктору в другое время или тогда, когда доктор принимает другого пациента, запрещено. Если пациент приходит в поликлинику в момент t, он ожидает первый момент времени st такой, что на этот момент доктор ведет прием, причем уже успел осмотреть всех пациентов, которые пришли в поликлинику раньше, то есть до момента t. Если доктор не успевает осмотреть всех до конца приема, то остаток пациентов должен прийти на следующий день.

Зная, в какой момент доктор начинает и заканчивает прием, те, кто и когда придут на прием в конкретный день, а также сколько времени будет осматривать доктор каждого пациента, определите момент времени, в который необходимо прийти на прием Пете Пяточкину, чтобы гарантированно попасть в этот день к доктору, и при этом ожидать приема как можно меньше. В случае, если имеется несколько альтернативных вариантов такого момента времени, Вам необходимо определить наименьший (наиболее ранний) из них.

Входные данные

В первой строке приведено три числа: количество желающих попасть на прием n, время начала приема t1 и время завершения приема t2, больший чем t1.

Во второй строке перечислены n чисел a1, a2, …, an - время, когда в поликлинику зашли соответственно первый, второй, ..., n-ый желающий попасть к доктору. Числа a1, a2, …, an попарно различны и расположены в порядке возрастания.

В третьей строке перечислены n чисел b1, b2, ..., bn - время, необходимое доктору на осмотр соответственно первого, второго, ..., n-го пациента.

Все входные числа натуральные. Количество пациентов n не больше 105, остальные числа не превосходят 109.

Сутки на планете, где проживает Петя Пяточкин, длятся значительно дольше, чем на Земле, поэтому время начала приема t1, время завершения приема t2, а также числа a1, a2, ..., an и b1, b2, ..., bn могут быть большими чем 1440 - количество минут в земных сутках.

Выходные данные

Вывести наименьший момент времени, когда Петя Пяточкин должен прийти в поликлинику, чтобы гарантированно попасть к доктору, подождав приема как можно меньше времени. Если Петя придет одновременно с другим человеком, его как младшего пропустят вперед.

Лимит времени 1 секунда
Лимит использования памяти 122.49 MiB
Входные данные #1
3 10 20
7 14 18
5 2 1
Выходные данные #1
17
Входные данные #2
5 10 20
4 9 12 16 22
4 10 10 9 2
Выходные данные #2
9
Входные данные #3
1 10 20
5
15
Выходные данные #3
5
Входные данные #4
1 10 20
15
15
Выходные данные #4
10
Автор Данило Мисак
Источник ІІІ (городской) этап Всеукраинской олимпиады школьников по информатике, 2013, г. Киев