Гермес#2123

Гермес

1 секунда
64 мегабайти
Дуже складна

У сучасному місті, населеному грецькими богами, вулиці розташовано у вигляді цілочисельної ґратки, паралельно осям та . Для кожного цілого існує горизонтальна вулиця y=Z та вертикальна вулиця x=Z. Кожне перехрестя цих вулиць знаходиться у точці з цілими координатами, тож кожна пара цілих чисел визначає унікальне перехрестя. У спекотні дні боги відпочивають у кав’ярнях, розташованих на цих перехрестях. Гермес, вісник, має доставити легкі повідомлення богам у кав’ярнях, пересуваючись лише вулицями міста. Кожне повідомлення адресоване певному богу, але якщо його побачать і інші боги — це не проблема.

Повідомлення необхідно доставляти у вказаному порядку, тому Гермес отримує координати кав’ярень саме у цій послідовності. Гермес починає шлях у точці . Щоб доставити повідомлення до кав’ярні з координатами (X_i, Y_i), Гермесу достатньо дістатися будь-якої точки на цій горизонтальній вулиці (тобто з -координатою Y_i) або на цій вертикальній вулиці (тобто з -координатою X_i). Після доставки усіх повідомлень Гермес зупиняється.

Ваше завдання — написати програму, яка, отримавши послідовність координат кав’ярень, визначає мінімальну загальну довжину шляху, який має пройти Гермес, щоб доставити всі повідомлення.

Вхідні дані

Перший рядок вхідних даних містить одне ціле число — кількість повідомлень, які потрібно доставити. Далі йдуть рядків із координатами перехресть, куди потрібно передати повідомлення, у вказаному порядку. Кожен із цих рядків містить два цілих числа: перше — -координата, друге — -координата перехрестя.

Для всіх тестів 1 \leq N \leq 20000, -1000 \leq X_i, Y_i \leq 1000. У тестів: 1 \leq N \leq 80.

Вихідні дані

У вихідний файл виведіть одне ціле число — мінімальну необхідну довжину шляху для доставки всіх повідомлень Гермесом.

Приклади

Приклад 1

Loading
Loading