import heapq class Heapq: def __init__(self, lst=[], reverse=False): if reverse: self.pm = -1 self.hq = [-l for l in lst] else: self.pm = 1 self.hq = lst.copy() heapq.heapify(self.hq) self.tot = sum(lst) self.rm = [] self.length = len(lst) def push(self, x): self.length += 1 heapq.heappush(self.hq, x * self.pm) self.tot += x def pop(self): self.length -= 1 ret = heapq.heappop(self.hq) self.tot -= self.pm * ret self.delete() return self.pm * ret def front(self): return self.pm * self.hq[0] def remove(self, x): # 存在しないものを消そうとするとバグる self.length -= 1 self.tot -= x heapq.heappush(self.rm, self.pm * x) self.delete() def delete(self): while self.rm and self.rm[0] == self.hq[0]: heapq.heappop(self.rm) heapq.heappop(self.hq) class Med_lst: def __init__(self, lst=[]): inf = 1 << 60 l = len(lst) self.low = Heapq(lst=[-inf] + lst[: (l + 1) // 2], reverse=True) self.upp = Heapq(lst=[inf] + lst[(l + 1) // 2 :]) self.low.tot += inf self.upp.tot -= inf self.low.length -= 1 self.upp.length -= 1 # def get(self): # return self.low.front() def get(self): if self.low.length == self.upp.length: return (self.low.front() + self.upp.front()) // 2 else: return self.low.front() def abs_sum(self): med = self.low.front() ret = med * self.low.length - self.low.tot ret += self.upp.tot - med * self.upp.length return ret def push(self, x): lst = [self.low.pop(), x, self.upp.pop()] lst.sort() if self.low.length == self.upp.length: self.low.push(lst[0]) self.low.push(lst[1]) self.upp.push(lst[2]) else: self.low.push(lst[0]) self.upp.push(lst[1]) self.upp.push(lst[2]) def remove(self, x): med = self.get() if x <= med: self.low.remove(x) if self.low.length < self.upp.length: self.low.push(self.upp.pop()) else: self.upp.remove(x) if self.low.length > self.upp.length + 1: self.upp.push(self.low.pop()) n = int(input()) X = Med_lst() Y = Med_lst() for _ in range(n): x, y = map(int, input().split()) X.push(x) Y.push(y) print(X.abs_sum() + Y.abs_sum())