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, м. Київ