Обратите внимание, что различия между простой и сложной версиями заключаются в ограничении на $$$n$$$ и в ограничении по времени. Вы можете делать взломы только если обе версии задачи решены.

AquaMoon узнала, что призраки собираются нападать на туристов на пешеходной улице. К сожалению, в этот раз призракам удается скрываться за невидимым барьером, поэтому она не может уничтожить их. Все что она может сделать это спасти от призраков любого человека оказавшегося на улице.

Пешеходная улица может быть представлена как координатная прямая. Есть один человек, который передвигается по ней. В момент времени $$$0$$$ он находится в координате $$$x$$$, двигаясь со скоростью $$$1$$$ координата в секунду. В частности, в момент времени $$$i$$$ человек будет в координате $$$x+i$$$.

Призраки собираются совершить $$$n$$$ нападений на улицу. $$$i$$$-е нападение будет длиться с момента времени $$$tl_i-1+10^{-18}$$$ до момента времени $$$tr_i+1-10^{-18}$$$ (не включительно) и будет убивать людей с координатами от $$$l_i-1+10^{-18}$$$ до $$$r_i+1-10^{-18}$$$ (не включительно). Формально это означает, что человек, чья координата находится в интервале $$$(l_i-1+10^{-18},r_i+1-10^{-18})$$$ в любой из моментов времени из интервала $$$(tl_i-1+10^{-18},tr_i+1-10^{-18})$$$ умрет.

Чтобы спасти человека на улице, AquaMoon может остановить время в любой момент времени $$$t$$$ и затем переместить человека из его текущей координаты $$$x$$$ в любую координату $$$y$$$ ($$$t$$$, $$$x$$$ и $$$y$$$ не обязательно целые числа). Это перемещение будет стоить для AquaMoon $$$|x-y|$$$ энергии. Перемещение является непрерывным, поэтому если существует координата под нападением между координатами $$$x$$$ и $$$y$$$ в момент времени $$$t$$$, человек также умрет.

AquaMoon хочет узнать какое минимальное количество энергии она должна потратить, чтобы спасти человека на улице от всех $$$n$$$ нападений. Она не очень хороша в программировании. Как ее друг, можете ли вы помочь ей?