e-olymp

Поліклініка

На прийом до лікаря щодня приходить чимало людей. Кожен пацієнт перебуває на прийомі цілу кількість хвилин, але різних пацієнтів лікар може приймати різну кількість часу. Лікар починає прийом у момент часу t1 хвилин і закінчує прийом у момент часу t2 хвилин. Це означає, що будь-який пацієнт незалежно від того, скільки часу його прийматиме лікар, може зайти на прийом у моменти t1, t1 + 1, ..., t2 - 1. Заходити на прийом до лікаря в інший час або тоді, коли лікар приймає іншого пацієнта, заборонено. Якщо пацієнт приходить у поліклініку в момент 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, м. Київ