Для операторов мобильной связи крайне важно размещать радиовышки как можно ближе к пользователям, поскольку расстояние между вышкой и пользователем напрямую влияет на мощность сигнала. Чем дальше пользователь находится от вышки, тем слабее будет сигнал, что может привести к обрыву вызовов, низкой скорости передачи данных и общей низкой производительности мобильной сети. Располагая радиовышки ближе к пользователям, операторы мобильной связи могут гарантировать, что пользователи получат сильный и стабильный сигнал, что необходимо для предоставления высококачественных мобильных услуг и поддержания удовлетворенности клиентов.

У очень известного мобильного оператора SDUcell есть $$$n$$$ радиовышек в городе. В данной задаче город можно представить как двумерную Евклидову плоскость и $$$i$$$-я радиовышка находится на целочисленной координате $$$(x_i, y_i)$$$. Расстояние между двумя точками измеряется Евклидовым расстоянием, то есть длиной кратчайшего отрезка, соединяющего заданные точки.

Активный пользователь данного оператора Марко решил прогуляться по улицам города и поболтать с друзьями во время прогулки. Он уже определился со своим маршрутом и выделил $$$m$$$ точек на карте.

Он начинает свой маршрут в точке $$$(a_1, b_1)$$$. Дальше он будет ходить по прямой линии до точки $$$(a_2, b_2)$$$, оттуда до точки $$$(a_3, b_3)$$$ и так далее. В итоге он закончит свой маршрут в точке $$$(a_m, b_m)$$$.

Особенность его маршрута в том, что улицы в городе расположены в прямоугольном виде. Поскольку Марко всегда гуляет по улицам, каждая часть его маршрута будет либо строго горизонтальной, либо вертикальной. Более формально, для всех $$$1 \le i \le m-1$$$ всегда будет выполняться либо $$$a_i = a_{i+1}$$$, либо $$$b_i = b_{i+1}$$$.

Марко двигается с постоянной скоростью одной единицы в секунду. То есть, пройденное расстояние прямо пропорционально потраченному времени и Марко пройдет $$$d$$$ единиц расстояния за $$$d$$$ секунд.

В каждый момент времени мобильный оператор SDUcell будет соединять телефон Марко к ближайшей радиовышке. По окончанию маршрута SDUcell считает стоимость звонка очень интересным образом:

• Обозначим общее количество времени в пути Марко как $$$d$$$. Будем считать, что Марко начал звонок в момент времени $$$0$$$ и завершил его в момент времени $$$d$$$. Для каждого момента времени $$$t$$$ ($$$0 \le t \le d$$$) определим значение $$$f(t)$$$ как расстояние от Марко до ближайшей радиовышки в этот момент.
• Тогда стоимость звонка в тенге будет определяться как площадь под функцией $$$C(t) = f(t)^2$$$ в промежутке $$$[0, d]$$$.

Какую сумму придется заплатить Марко?