F. Опоздать на работу (отправка решений запрещена)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эта задача была скопирована автором с другой платформы. 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
Примечание

В первом примере мы можем сделать следующее:

  • Изначально, $$$5$$$ светофоров находятся на следующих секундах в цикле: $$$\{2,3,6,2,0\}$$$.
  • Оптимальное время для Harsh, чтобы начать, если Debajyoti приедет через $$$1$$$ секунду. Заметьте, что эта $$$1$$$ секунда не будет учитываться в финальном ответе.
  • Светофоры сейчас находятся в состоянии $$$\{3,4,7,3,1\}$$$, поэтому Harsh может проехать от $$$1$$$-го светофора до $$$2$$$-го светофора, что требует $$$1$$$ секунду для перемещения.
  • Светофоры сейчас находятся в состоянии $$$\{4,5,8,4,2\}$$$, поэтому Harsh может продолжить движение без остановки до $$$3$$$-го светофора, что требует $$$2$$$ секунды для перемещения.
  • Светофоры сейчас находятся в состоянии $$$\{6,7,0,6,4\}$$$, поэтому Harsh продолжит движение до $$$4$$$-го светофора, что требует $$$3$$$ секунды для перемещения.
  • Светофоры сейчас находятся в состоянии $$$\{9,0,3,9,7\}$$$. Harsh должен подождать $$$1$$$ секунду, чтобы $$$4$$$-й светофор загорелся зелёным прежде чем доехать до $$$5$$$-го светофора, что требует $$$4$$$ секунды для передвижения.
  • Светофоры сейчас находятся в состоянии $$$\{4,5,8,4,2\}$$$, поэтому Harsh может продолжить передвижение без остановки до места встречи. Общее время, которое Harsh провел за рулем, равно $$$1+2+3+1+4=11$$$ секунд.

В втором примере мы можем сделать следующее:

  • Изначально $$$6$$$ светофоров находятся на следующих секундах в цикле: $$$\{3,5,0,8,7,6\}$$$.
  • Оптимальным для Harsh будет начать, если Debajyoti приедет после $$$1$$$ секунды. Заметьте, что эта $$$1$$$ секунда не будет учитываться в финальном ответе.
  • Светофоры сейчас находятся в состоянии $$$\{4,6,1,0,8,7\}$$$, поэтому Harsh может проехать $$$1$$$-го светофора до $$$2$$$-го, что требует $$$0$$$ секунд для передвижения.
  • Светофоры всё ещё находятся в состоянии $$$\{4,6,1,0,8,7\}$$$. Harsh должен подождать $$$3$$$ секунды, чтобы $$$2$$$-й светофор загорелся зелёным, прежде чем поехать до $$$3$$$-го светофора, что потребует $$$0$$$ секунд для передвижения.
  • Светофоры сейчас находятся в состоянии $$$\{7,0,4,3,2,1\}$$$, поэтому Harsh продолжит двигаться до $$$4$$$-го светофора, что потребует $$$0$$$ секунд для передвижения.
  • Светофоры всё ещё находятся в состоянии $$$\{7,0,4,3,2,1\}$$$, поэтому Harsh продолжит двигаться до $$$5$$$-го светофора, что потребует $$$0$$$ секунд для передвижения.
  • Светофоры всё ещё находятся в состоянии $$$\{7,0,4,3,2,1\}$$$, поэтому Harsh продолжит двигаться до $$$6$$$-го светофора, что потребует $$$0$$$ секунд для передвижения.
  • Светофоры всё ещё находятся в состоянии $$$\{7,0,4,3,2,1\}$$$, поэтому Harsh продолжит двигаться до места назначения без остановки. Общее время, которое Harsh проведёт в дороге равно $$$0+3+0+0+0=3$$$ секунды.