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

Начинающий японский художник рисует абстрактную картину на $$$n$$$ гвоздиках, занумерованных от $$$1$$$ до $$$n$$$ в порядке их расположения на доске слева направо. Для каждого гвоздика известны его координаты на доске: $$$i$$$-й гвоздик расположен в позиции $$$(x_i, y_i)$$$, причем $$$x_1 \le x_2 \le \ldots \le x_n$$$.

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

• Если какая-то нить последний раз была привязана к гвоздику номер $$$i$$$, то затем ее можно привязать только к гвоздику с номером $$$ \gt i$$$. Иными словами, последовательность узлов на любой нити должна иметь строго возрастающие номера гвоздиков.
• Каждый гвоздик должен быть использован хотя бы один раз, то есть для любого $$$i$$$ существует либо узел первой нити на $$$i$$$-м гвоздике, либо узел второй нити, либо обеих.
• Суммарная потраченная длина нитей должна быть как можно меньше.

Расстояние между гвоздиками $$$i$$$ и $$$j$$$ равно $$$\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$$$. Суммарная длина используемых нитей равна сумме расстояний между их соседними узлами. При этом каждая нить может быть привязана на произвольное число гвоздиков, и последние гвоздики двух нитей не обязаны совпадать.

Определите оптимальную основу для стринг-арт рисунка, для которой выполняются все поставленные условия.

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