DEBUG = False N = int(input()) volcs = [] for n in range(N): a, b = input().split(' ') a, b = int(a), int(b) # print(a, b) volcs.append((a,b)) # sort left to right # sort up to down volcs.sort(key=lambda tup : tup[1]) # top down volcs.sort(key=lambda tup : tup[0]) volcs_top_down = volcs.copy() volcs.sort(key=lambda tup : tup[1], reverse=True) volcs.sort(key=lambda tup : tup[0]) volcs_down_top = volcs.copy() if DEBUG: print("volcs (top down): ", volcs_top_down) print("volcs (down top): ", volcs_down_top) # top down first top_down = True curr_list = volcs_top_down first_cost = 0 prev_volc = curr_list[0] if DEBUG: print("TOP_DOWN: ") print(prev_volc) for i in range(1, len(volcs)): curr_volc = curr_list[i] # if curr has new x, swap the dicts if curr_volc[0] != prev_volc[0] and top_down: curr_list = volcs_down_top top_down = False elif curr_volc[0] != prev_volc[0] and not top_down: curr_list = volcs_top_down top_down = True curr_volc = curr_list[i] if DEBUG: print(curr_volc) first_cost += abs(prev_volc[0] - curr_volc[0]) + abs(prev_volc[1] - curr_volc[1]) prev_volc = curr_volc # down top first down_top = True curr_list = volcs_down_top second_cost = 0 prev_volc = curr_list[0] if DEBUG: print("DOWN_TOP: ") print(prev_volc) for i in range(1, len(volcs)): curr_volc = curr_list[i] # if curr has new x, swap the dicts if curr_volc[0] != prev_volc[0] and down_top: curr_list = volcs_top_down down_top = False elif curr_volc[0] != prev_volc[0] and not down_top: curr_list = volcs_down_top down_top = True curr_volc = curr_list[i] if DEBUG: print(curr_volc) second_cost += abs(prev_volc[0] - curr_volc[0]) + abs(prev_volc[1] - curr_volc[1]) prev_volc = curr_volc # print("cost: ", min(first_cost, second_cost)) print(min(first_cost, second_cost))