Задачи
Лонг лонг Сом
Лонг лонг Сом
Сом Иван действительно является самой длинной рыбой на факультете. Возможно, поэтому, ему неинтересно сидеть за партой в той же позе, что и остальные. Он больше любит на них лежать. Иван наметил себе \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