e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more

Поликлиника

Many people come to the doctor every day. Each patient goes to doctor on reception for a whole number of minutes, but the doctor can take different amounts of time for different patients. Doctor starts reception at t1 minutes and finishes at t2 minutes. It means that any patient independently of his reception time, can come to doctor at the moments of time t1, t1 + 1, ..., t2 - 1. To go to see a doctor at another time or when the doctor takes another patient is prohibited. If the patient comes to the polyclinic at the time t, he expects the first moment of time st such that at this moment the doctor is taking a reception, and already had time to examine all patients who came to the clinic before, that is until the moment t. If the doctor does not have time to examine everyone before the end of the working day, the rest of the patients should come the next day.

Knowing the time when doctor starts and ends the reception, who and when will come to the reception on a particular day, and also how much time will be examined by the doctor each patient, determine the time when it is necessary to come to the reception for Petya Pyatochkin, to be guaranteed to get this day to the doctor, and his expectation time must be as small as possible. In the case of several alternative options for such time, determine the smallest (the earliest) of them.

Input

В первой строке приведено три числа: количество желающих попасть на прием 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 - количество минут в земных сутках.

Output

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

Time limit 1 seconds
Memory limit 122.49 MiB
Input example #1
3 10 20
7 14 18
5 2 1
Output example #1
17
Input example #2
5 10 20
4 9 12 16 22
4 10 10 9 2
Output example #2
9
Input example #3
1 10 20
5
15
Output example #3
5
Input example #4
1 10 20
15
15
Output example #4
10
Author Данило Мисак
Source ІІІ (городской) этап Всеукраинской олимпиады школьников по информатике, 2013, г. Киев