Опять Сайтама ненарочно уничтожил гостиницу. Чтобы расплатиться с гостиничной компанией, Генос вызвался управлять лифтом в одной из уцелевших гостиниц этой компании. Лифт обладает рядом особенностей: он всегда начинает движение с верхнего этажа, может двигаться только вниз и имеет бесконечную вместимость. Этажи пронумерованы от 0 до s, при этом лифт всегда находится на этаже номер s в момент времени 0.
Лифту требуется ровно 1 секунда, чтобы переместиться ровно на 1 этаж вниз. Временем, которое тратится на посадку и высадку пассажиров, можно пренебречь. У Геноса есть список, детально описывающий, когда и на какой этаж прибывает очередной пассажир. Пожалуйста, определите минимальное количество секунд, за которое можно доставить всех пассажиров на этаже номер 0.
В первой строке входных данных записано два целых числа n и s (1 ≤ n ≤ 100, 1 ≤ s ≤ 1000) — количество пассажиров и номер верхнего этажа соответственно.
В каждой из следующих n строк записано по два целых числа fi и ti (1 ≤ fi ≤ s и 1 ≤ ti ≤ 1000) — номер этажа и время прибытия в секундах для i-го пассажира.
Выведите единственное целое число — минимальное количество времени в секундах, необходимое для того, чтобы высадить всех пассажиров на этаже с номером 0.
3 7
2 1
3 8
5 2
11
5 10
2 77
3 33
8 21
9 12
10 64
79
В первом примере необходимо потратить не меньше 11 секунд, чтобы доставить всех пассажиров на этаж номер 0. Одним из способов это сделать является:
1. Доехать до этажа номер 5: занимает 2 секунды.
2. Взять пассажира номер 3.
3. Доехать до этажа номер 3: занимает 2 секунды.
4. Подождать, пока подойдет пассажир номер 2: занимает 4 секунды.
5. Взять пассажира номер 2.
6. Доехать до этажа номер 2: занимает 1 секунду.
7. Взять пассажира номер 1.
8. Доехать до этажа номер 0: занимает 2 секунды.
9. Высадить всех пассажиров.
Итого получается 2 + 2 + 4 + 1 + 2 = 11 секунд.
| Codeforces Round 336 (Div. 2) |
|---|
| Закончено |
