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

Есеп B. Платформер ойыны

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

2 seconds

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

256 megabytes

Жақында Нархан өзінің жеке платформер ойынын құрастырды. Ұқсас жанрдағы көптеген ойындар секілді ойынның барлық әрекеттері екі өлшемді кеңістікте өтеді. Ойын әлемін $(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$) бүтін сандары — кедергілер саны және соңғы нүктесінің координатасы берілген. Келесі $n$ жолдардың $i$-ші қатарында төрт бүтін сан $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$, бүкіл $i$ үшін $R_i <= L_{i+1}$).

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

Ойынды барынша тез аяқтау үшін Аманболға жалпы неше секунд қажет екенін шығарыңыз.

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

Бұл есеп $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 )