4-й этап Республиканской олимпиады по информатике 2022-2023, 1-й тур

Задача B. Игра-платформер

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Нархан недавно создал свою оригинальную игру-платформер. Как в большинстве игр похожего жанра, всё действие игры происходит в двумерном пространстве. Весь мир игры можно описать как один большой прямоугольник, соединяющий точки $(0, 0)$ и $(m, 10^9)$. Все объекты в игре находятся внутри этого прямоугольника. Прямая $y=0$ считается землей. В игре действует обычная гравитация. Игрок начинает игру в точке $(0, 0)$ и для победы нужно добраться до точки $(m, 0)$. В игре также присутствуют $n$ препятствий. Каждое препятствие также можно описать как прямоугольник. Все препятствия лежат на земле, т.е. напрямую касаются земли. Расположение каждого из них описывается тремя целыми числами $L_i$, $R_i$ и $H_i$ — $x$-координатой левого конца прямоугольника, $x$-координатой правого конца прямоугольника и высотой прямоугольника. Препятствия не пересекаются между собой, но могут касаться друг-друга. Также гарантируется, что никакое препятствие не содержит начальную точку $(0, 0)$ и конечную точку $(m, 0)$. Игрок может свободно перемещаться налево или направо. Однако игрок не может проходить сквозь препятствия или обходить их. Но игрок может подниматься и опускаться по сторонам препятствий. На каждое перемещение игрока тратится ровно одна секунда. Нархан попросил Аманбола пройти эту игру. Аманбол очень ленивый, поэтому он не хочет тратить большое количество времени на прохождение игры. Поэтому перед началом игры он может попросить Нархана передвинуть некоторые препятствия. Он может выбрать произвольное препятствие $i$ ($1 <= i <= n$) и попросить Нархана подвинуть это препятствие на одну единицу налево или на одну единицу направо при условии что все правила игры всё еще выполняются (препятствия не должны пересекаться и не должны содержать начальную или конечную точку). Нархану потребуется ровно $C_i$ секунд чтобы выполнить просьбу Аманбола. Аманбол может просить Нархана подвинуть прямоугольники неограниченное (возможно $0$) количество раз. За какое минимальное суммарное время он сможет пройти игру?

Формат входного файла

В первой строке входного файла содержатся два целых числа $n$ и $m$ — количество препятствий и координата конечной точки ($1 <= n <= 5 \cdot 10^5$, $1 <= m <= 3 \cdot 10^6$). В $i$-й из последующих $n$ строк содержатся четыре целых числа $L_i$, $R_i$, $H_i$ и $C_i$ — координата левого конца, координата правого конца, высота и стоимость передвижения $i$-го препятствия ($1 <= L_i < R_i <= m-1$, $1 <= H_i <= 10^9$, $0 <= C_i <= 3 \cdot 10^6$, $R_i <= L_{i+1}$ для всех $i$).

Формат выходного файла

Выведите одно единственное целое число — минимальное суммарное количество секунд, необходимое Аманболу для прохождения игры.

Система оценки

Данная задача содержит $6$ подзадач.

Примеры:

Вход

3 10
1 3 5 100
4 6 4 2
7 9 3 100

Ответ

28

Вход

4 15
1 4 3 0
5 6 3 0
6 8 3 0
12 13 3 0

Ответ

21

Замечание

Разберем первый пример.

Но Аманбол может попросить подвинуть второй прямоугольник на единицу налево за $2$ секунды. Теперь для прохождения игры потребуются $26$ секунд. В итоге получилось $28$ секунд.

( Temirlan Baibolov )