Эта задача была скопирована автором с другой платформы. Codeforces категорически осуждает такое действие, поэтому дальнейшие посылки по этой задаче не будут приняты.
Debajyoti предстоит очень важная встреча, и он уже очень опаздывает. Harsh, его водитель, должен как можно быстрее доставить Debajyoti к месту встречи.
Harsh должен забрать Debajyoti из его дома и отвезите его к месту назначения, чтобы Debajyoti успел вовремя посетить встречу. Прямая дорога с $$$n$$$ светофорами соединяет дом и место проведения интервью. Светофоры пронумерованы по порядку от $$$1$$$ до $$$n$$$.
Каждый светофор зацикливается через $$$t$$$ секунд. $$$i$$$-й светофор горит $$$\color{green}{\text{зелёным}}$$$ (в этом случае Harsh может проехать светофор) первые $$$g_i$$$ секунд, и $$$\color{red}{\text{красным}}$$$ (в этом случае Harsh должен дождаться включения $$$\color{green}{\text{зелёного}}$$$) оставшиеся $$$(t−g_i)$$$ секунд, после чего схема повторяется. Цикл каждого светофора повторяется бесконечно, и изначально, $$$i$$$-й светофор находится на секунде $$$c_i$$$ в своём цикле (светофор с $$$c_i=0$$$ только что включил $$$\color{green}{\text{зелёный}}$$$). В случае, если Harsh приближается к светофору в то же время, когда он меняет цвет, он будет подчиняться новому цвету. Формально, $$$i$$$-й светофор горит $$$\color{green}{\text{зелёным}}$$$ в отрезок времени $$$[0,g_i)$$$ и $$$\color{red}{\text{красным}}$$$ в отрезок времени $$$[g_i,t)$$$ (после чего цикл повторяется). $$$i$$$-й светофор изначально находится на $$$c_i$$$-й секунде своего цикла.
От $$$i$$$-го светофора ровно $$$d_i$$$ секунд требуются, чтобы доехать до следующего светофора (то есть до $$$(i+1)$$$-го светофора). Дом Debajyoti расположен прямо перед первым светофором, и Debajyoti попадает на интервью как только он проезжает $$$n$$$-й светофор. Другими словами, не требуется времени, чтобы доехать до первого светофора из дома Debajyoti или добраться до центра интервью от $$$n$$$-го светофора.
Harsh не знает, сколько времени потребуется Debajyoti, чтобы собраться. В ожидании он задается вопросом, какое минимально возможное количество времени ему может понадобиться провести за рулем, если он начнет движение в момент прибытия Debajyoti, которое может быть любым от $$$0$$$ до $$$\infty$$$ секунд от данного момента. Можете ли вы сказать Harsh минимально возможное количество времени, которое ему нужно провести в дороге?
Обратите внимание, что Harsh может начинать или останавливать движение только в целочисленные моменты времени.
Первая строка ввода содержит два целых числа $$$n$$$ и $$$t$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$2 \le t \le 10^9$$$) — количество светофоров и длину цикла светфоров соответственно.
Далее следуют $$$n$$$ строк. $$$i$$$-я строка содержит два целых числа $$$g_i$$$ и $$$c_i$$$ ($$$1 \le g_i < t$$$, $$$0 \le c_i < t$$$), описывающие $$$i$$$-й светофор.
Следующая строка содержит $$$n−1$$$ целых чисел $$$d_1, d_2, \ldots, d_{n-1}$$$ ($$$0 \le d_i \le 10^9$$$) — время, нужное чтобы доехать от $$$i$$$-го до $$$(i+1)$$$-го светофора.
Выведите единственное целое число — минимально возможное количество времени, которое Harsh может провести в дороге.
5 10 4 2 7 3 3 6 5 2 8 0 1 2 3 4
11
6 9 5 3 5 5 7 0 5 8 7 7 6 6 0 0 0 0 0
3
В первом примере мы можем сделать следующее:
В втором примере мы можем сделать следующее:
Название |
---|