Задача №112845. Tutu
Санкт-Петербург и Москва соединены одноколейной железной дорогой. Поезду требуется s минут чтобы проехать от одного города до другого в любом из направлений. Однако, поезда должны отправляться от станции с интервалом хотя бы в одну минуту. Более того, в любой момент времени все поезда на железной дороге должны двигаться в одном и том же направлении.
Имеется n поездов, которые сначала прибывают из Саратова в Москву, затем эти поезда должны быть отправлены из Москвы в Санкт-Петербург, там они должны быть загружены культурными ценностями и вернуться обратно в Москву. Для простоты мы будем считать, что погрузка происходит мгновенно.
Требуется определить минимальное время, в которое последний поезд может вернуться в Москву.
В первой строке входных данных содержатся два числа n и s — количество поездов и время проезда от Москвы до Петербурга, соответственно ( 1 ≤ n ≤ 10 6 , 1 ≤ s ≤ 10 9 ). В следующей строке содержатся n чисел t 1 , t 2 , ..., t n , которые обозначают времена прибытия поездов из Саратова в Москву ( 0 ≤ t i ≤ 10 9 ).
Выведите единственное число — искомое минимальное время возвращения последнего поезда в Москву.
Решение, работающее в случае n ≤ 100 будет набирать не менее 25 баллов. Решение, работающее в случае n ≤ 5000 будет набирать не менее 50 баллов.
Одним из оптимальных решений в примере из условия является следующее: поезда отправляются из Москвы в моменты времени 1, 9 и 11, а из Петербурга — 5, 15 и 16.
3 4 1 8 11
20