Поліклініка
Поліклініка
На прийом до лікаря щодня приходить чимало людей. Кожен пацієнт перебуває на прийомі цілу кількість хвилин, але різних пацієнтів лікар може приймати різну кількість часу. Лікар починає прийом у момент часу t1
хвилин і закінчує прийом у момент часу t2
хвилин. Це означає, що будь-який пацієнт незалежно від того, скільки часу його прийматиме лікар, може зайти на прийом у моменти t1
, t1
+ 1, ..., t2
- 1. Заходити на прийом до лікаря в інший час або тоді, коли лікар приймає іншого пацієнта, заборонено. Якщо пацієнт приходить у поліклініку в момент t, він чекає на перший момент часу s ≥ t такий, що на цей момент лікар веде прийом, причому вже встиг оглянути всіх пацієнтів, які прийшли у поліклініку раніше, тобто до моменту 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 - кількість хвилин у земній добі.
Вихідні дані
Вивести єдине натуральне число - найменший момент часу, коли Петрик П'яточкін має прийти в поліклініку, щоб гарантовано потрапити до лікаря, але прочекати на прийом якомога менше часу. Якщо Петрик прийде водночас з іншою людиною, його як молодшого пропустять уперед.
3 10 20 7 14 18 5 2 1
17
5 10 20 4 9 12 16 22 4 10 10 9 2
9
1 10 20 5 15
5
1 10 20 15 15
10