На двухмерной декартовой плоскости расположено n городов. Расстояние между двумя городами равняется Манхэттенскому расстоянию между ними (определение см. в примечаниях). Гамильтоновым циклом указанных городов является перестановка из n городов. Длина этого Гамильтонова цикла определяется как сумма расстояний между смежными городами в перестановке плюс расстояние между первым и последним городом в перестановке. Пожалуйста, подсчитайте длиннейшую возможную длину Гамильтонова цикла данных городов.
Выходные данные
Выведите единственную строку, обозначающую наибольшую возможную длину Гамильтонова цикла данных городов. Сам цикл выводить не надо, только его длину.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
В примере одним из возможных Гамильтоновых циклов длины 6 является цикл (1, 1) (1, 2) (2, 1) (2, 2). Других Гамильтоновых циклов, чья длина превышает 6, не существует.
Манхэттенское расстояние между двумя городами (xi, yi) и (xj, yj) равняется |xi - xj| + |yi - yj|.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 1
1 2
2 1
2 2
|
6
|