Bessie должна сдать задания $C$ курсов Moo U ($1 \le C \le 1{,}000$), чтобы пережёвывать жвачку с одноклассниками, ожидая автобус домой.
Учителя принимают после урока, очистки доски, уборки лабораторного и прочего. Ввод даёт самое раннее время приёма.
Начинает с конца коридора длины $H$ метров ($1 \le H \le 1{,}000$), расстояние $0$, идёт метр в секунду в классы в любом порядке. Все классы и дверь к автобусной площадке на коридоре.
По положениям выхода/классов и расписаниям найдите самое раннее время выхода к автобусам. Сдать всё до выхода, сама сдача мгновенна.
Входные данные
- Строка 1: целые $C$, $H$, $B$. $B$ ($0 \le B \le H$) — расстояние от входа к площадке.
- Строки $2..C+1$: по два целых для класса сдачи. Первое ($0..H$) — метры от входа, второе ($0..10,000$) — первая секунда приёма учителем.
Выходные данные
- Строка 1: целое, самая ранняя секунда выхода к автобусам.
Примеры
Входные данные 1
4 10 3
8 9
4 21
3 16
8 12Выходные данные 1
22Примечание
| Время | Действие |
|---|---|
| $0$ | Bessie идёт к классам в$8$ метрах (на$8$м) |
| $8$ | Ждёт$1$ секунду |
| $9$ | Сдаёт первые задания |
| $9$ | Ждёт$3$ секунды, думая о прохладном летнем сене |
| $12$ | Сдаёт другие задания здесь |
| $12$ | Возвращается к классу в$4$ метрах (на$4$м) |
| $16$ | Ждёт$5$ секунд, вспоминая красивого быка |
| $21$ | Сдаёт задания |
| $21$ | Возвращается к классу в$1$ метре (на$3$м) |
| $22$ | Сдаёт задания |
| $22$ | Выходит, тут и выход к автобусам |
Можно выйти в $22$, лучше расписания нет.
Благодарности: Hal Burch, 2004