Задачі
Лонг лонг Сом
Лонг лонг Сом
Сом Іван дійсно є найдовшою рибою на факультеті. Можливо, тому, йому нецікаво сидіти за партою в тій самій позі, що й інші. Він більше полюбляє на них лежати. Іван намітив собі \textbf{N} парт, на яких він хоче полежати сьогодні. Пересуватися по аудиторії можна тільки між рядами парт, з чого випливає, що відстань між партою, що знаходиться в точці (\textbf{x_1}, \textbf{y_1}) і партою в точці (\textbf{x_2}, \textbf{y_2}), дорівнює \textbf{|x_1-x_2| + |y_1-y_2|}. Аудиторія досить велика, тому, Іван хоче мінімізувати сумарну відстань, необхідну для відвідування усіх \textbf{N} парт. Почати свій шлях він може з будь-якої точки аудиторії.
\InputFile
У першому рядку подається кількість парт \textbf{N }(\textbf{1 }≤ \textbf{N} ≤ \textbf{20}), на яких Іван хоче сьогодні залягти. У наступних \textbf{N} рядках йдуть по два цілих числа \textbf{x_i}, \textbf{y_i} (\textbf{1 }≤ \textbf{x_i}, \textbf{y_i} ≤ \textbf{10^10}) - координати цих парт.
\OutputFile
Мінімальна відстань, яку треба подолати Івану.
Вхідні дані #1
3 2 1 3 2 4 1
Вихідні дані #1
4