eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Поликлиника

Поликлиника

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

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

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

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

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

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

В третьей строке перечислены n чисел b[1], b[2], ..., b[n] - время, необходимое доктору на осмотр соответственно первого, второго, ..., n-го пациента.

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

Сутки на планете, где проживает Петя Пяточкин, длятся значительно дольше, чем на Земле, поэтому время начала приема t[1], время завершения приема t[2], а также числа a[1], a[2], ..., a[n] и b[1], b[2], ..., b[n] могут быть большими чем 1440 - количество минут в земных сутках.

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

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

Пример

Входные данные #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, г. Киев