import sys sys.setrecursionlimit(1000000) def distance(t1, t2): return abs(t1[0] - t2[0]) + abs(t1[1] - t2[1]) def solve(arr, single, index, dist,first=False): #print(index, dist, first) #print(arr[index]) if single[index]: if index == len(arr) - 1: return dist, index if single[index + 1]: return dist + distance(arr[index], arr[index + 1]), index + 1 d1, x1 = solve(arr, single, index + 1, dist + distance(arr[index], arr[index + 1]), first=True) d2, x2 = solve(arr, single, index + 2, dist + distance(arr[index], arr[index + 2])) if d1 < d2: return d1, x1 return d2, x2 else: if first: d = distance(arr[index], arr[index+1]) if index + 1 == len(arr) - 1: return dist + d, index + 1 if single[index + 2]: return dist + d + distance(arr[index+1], arr[index+2]), index + 2 d1, x1 = solve(arr, single, index + 2, dist + d + distance(arr[index+1], arr[index+2]), first=True) d2, x2 = solve(arr, single, index + 3, dist + d + distance(arr[index+1], arr[index+3])) if d1 < d2: return d1, x1 return d2, x2 else: d = distance(arr[index], arr[index-1]) if index == len(arr) - 1: return dist + d, index if single[index + 1]: return dist + d + distance(arr[index-1], arr[index+1]), index + 1 d1, x1 = solve(arr, single, index + 1, dist + d + distance(arr[index-1], arr[index+1]), first=True) d2, x2 = solve(arr, single, index + 2, dist + d + distance(arr[index-1], arr[index+2])) if d1 < d2: return d1, x1 return d2, x2 def main(): n = int(input()) arr = [None for _ in range(n)] for index in range(n): x, y = [int(i) for i in input().split()] arr[index] = (x,y) arr.sort() arr2 = [] last = False prev = (None, None) for i in arr: if prev[0] == None: arr2.append(i) prev = i last = True else: if prev[0] != i[0]: if not last: arr2.append(prev) arr2.append(i) last = True prev = i else: last = False prev = i if n == 1: print(0) return if not last: arr2.append(prev) single = [None for _ in arr2] if arr2[0][0] != arr2[1][0]: single[0] = True else: single[0] = False for i in range(1, len(arr2) - 1): if arr2[i][0] != arr2[i - 1][0] and arr2[i][0] != arr2[i + 1][0]: single[i] = True else: single[i] = False if arr2[-1][0] != arr2[-2][0]: single[-1] = True else: single[-1] = False index = 0 dist = 0 if not single[0]: #print('f') dist1, index1 = solve(arr2, single, 0, 0, first=True) #print('s') dist2, index2 = solve(arr2, single, 1, 0) dist = min(dist1, dist2) index = index1 while index < (len(arr2) - 1): dist, index = solve(arr2, single, index, dist) print(dist) if __name__ == '__main__': main()