Задача №115447. Поездка в Москву
Андрей живет в Санкт-Петербурге, однако ему часто приходится ездить в Москву по рабочим делам. Для перемещения между городами Андрей предпочитает использовать личный автомобиль и скоростную современную трассу, соединяющую два города. Так как у Андрея много работы, он не хочет тратить много времени на дорогу до Москвы. Поэтому он задумался о том, как минимизировать время поездки.
Расстояние от Москвы до Санкт-Петербурга составляет \(m\) единиц. Для удобства представим трассу, соединяющую города, как числовую прямую. Санкт-Петербург находится в точке \(0\), а Москва — в точке \(m\). Также на трассе построены \(n\) заправочных станций, \(i\)-я из которых расположена на расстоянии \(x_i\) единиц от Санкт-Петербурга. Таким образом, \(i\)-я заправка будет расположена на числовой прямой в точке \(x_i\).
Обозначим за \(t_i\) количество единиц времени, необходимых для того, чтобы заправиться на \(i\)-й станции. Для простоты будем считать, что время заправки не зависит от количества топлива, заправляемого в автомобиль.
Бак личного автомобиля Андрея вмещает в себя \(c\) литров топлива. Разумеется, расход топлива при езде по трассе зависит от скорости, с которой движется автомобиль. Андрей знает, что при езде со скоростью \(v\) единиц расстояния в единицу времени его автомобиль будет расходовать \(v\) литров топлива на одну единицу расстояния. Ограничения скорости на трассе нет, можно ехать с любой скоростью.
Изначально Андрей находится в Санкт-Петербурге, и его автомобиль заправлен до полного бака (то есть в баке автомобиля содержатся \(c\) литров топлива). Зная информацию о всех заправках на трассе, помогите Андрею вычислить минимальное количество единиц времени, которых хватит, чтобы добраться до Москвы. Обратите внимание, что Андрею не важно, сколько литров топлива останется в его автомобиле в момент, когда он окажется в Москве.
Первая строка содержит три целых числа \(n\), \(m\) и \(c\) (\(1 \le n \le 250\,000\), \(n + 1 \le m \le 10^9\), \(1 \le c \le 10^9\)) — количество заправочных станций, расстояние от Санкт-Петербурга до Москвы, а также объем бака автомобиля Андрея.
Каждая из следующих \(n\) строк содержит два целых числа \(x_i\) и \(t_i\) (\(0 < x_i < m\), \(1 \le t_i \le 1\,000\)) — расстояние от Санкт-Петербурга до \(i\)-й заправочной станции, а также время, необходимое для заправки автомобиля на ней.
Гарантируется, что \(0 < x_1 < x_2 < \ldots < x_n < m\).
Выведите одно вещественное число — минимальное количество единиц времени, необходимых для того, чтобы добраться до Москвы.
Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не превосходит \(10^{-6}\).
Формально, пусть ваш ответ равен \(a\), а ответ жюри равен \(b\). Ваш ответ будет зачтен, если и только если \(\frac{\lvert a - b \rvert}{\max(1, \lvert b \rvert)} \le 10^{-6}\).
В первом примере оптимальный маршрут Андрея устроен следующим образом:
- Доехать от Санкт-Петербурга до второй заправочной станции, проехав \(15\) единиц расстояния. Данный участок можно проехать со скоростью \(\frac{25}{15}\), чтобы израсходовать все топливо. Таким образом, путь займет \(9\) единиц времени;
- Заправить бак на второй станции, потратив \(30\) единиц времени;
- Доехать от второй заправочной станции до четвертой заправочной станции, проехав \(65\) единиц расстояния. Данный участок можно проехать со скоростью \(\frac{25}{65}\), чтобы израсходовать все топливо. Таким образом, путь займет \(169\) единиц времени;
- Заправить бак на четвертой станции, потратив \(60\) единиц времени;
- Доехать от четвертой заправочной станции до Москвы, проехав \(20\) единиц расстояния. Данный участок можно проехать со скоростью \(\frac{25}{20}\), чтобы израсходовать все топливо. Таким образом, путь займет \(16\) единиц времени.
4 100 25 10 50 15 30 50 100 80 60
284.0000000000