Maksim walks on a Cartesian plane. Initially, he stands at the point $(0, 0)$ and in one move he can go to any of four adjacent points (left, right, up, down). For example, if Maksim is currently at the point $(0, 0)$, he can go to any of the following points in one move:   $(1, 0)$;  $(0, 1)$;  $(-1, 0)$;  $(0, -1)$. 

There are also $n$ distinct key points at this plane. The $i$-th point is $p_i = (x_i, y_i)$. It is guaranteed that $0 \le x_i$ and $0 \le y_i$ and there is no key point $(0, 0)$.

Let the first level points be such points that $max(x_i, y_i) = 1$, the second level points be such points that $max(x_i, y_i) = 2$ and so on. Maksim wants to visit all the key points. But he shouldn't visit points of level $i + 1$ if he does not visit all the points of level $i$. He starts visiting the points from the minimum level of point from the given set.

The distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$ where $|v|$ is the absolute value of $v$.

Maksim wants to visit all the key points in such a way that the total distance he walks will be minimum possible. Your task is to find this distance.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of key points.

Each of the next $n$ lines contains two integers $x_i$, $y_i$ ($0 \le x_i, y_i \le 10^9$) — $x$-coordinate of the key point $p_i$ and $y$-coordinate of the key point $p_i$. It is guaranteed that all the points are distinct and the point $(0, 0)$ is not in this set.


-----Output-----

Print one integer — the minimum possible total distance Maksim has to travel if he needs to visit all key points in a way described above.


-----Examples-----
Input
8
2 2
1 4
2 3
3 1
3 4
1 1
4 3
1 2

Output
15

Input
5
2 1
1 0
2 0
3 2
0 3

Output
9



-----Note-----

The picture corresponding to the first example: [Image]

There is one of the possible answers of length $15$.

The picture corresponding to the second example: [Image]

There is one of the possible answers of length $9$.

Difficulty: introductory

Starter code:

Solutions:


def solve():
    Point=[]
    n=int(input())
    for i in range(n):
        x,y=list(map(int,input().split()))
        Point.append((x,y))
    data={}
    for each in Point:
        if each[0]<each[1]:
            try:
                tm=data[each[1]]
            except KeyError:
                data[each[1]]={}
            try:
                data[each[1]]['xi']=min(data[each[1]]['xi'],each[0])
            except KeyError:
                data[each[1]]['xi']=each[0]
            try:
                data[each[1]]['xa'] = max(data[each[1]]['xa'], each[0])
            except KeyError:
                data[each[1]]['xa'] = each[0]
        else:
            try:
                tm=data[each[0]]
            except KeyError:
                data[each[0]]={}
            try:
                data[each[0]]['yi']=min(data[each[0]]['yi'],each[1])
            except KeyError:
                data[each[0]]['yi']=each[1]
            try:
                data[each[0]]['ya']=max(data[each[0]]['ya'],each[1])
            except KeyError:
                data[each[0]]['ya'] = each[1]
    pre1=(0,0,0)
    pre2=(0,0,0)
    for each in sorted(data.keys()):
        x1,y1,w1=pre1
        x2,y2,w2=pre2
        if len(data[each])==2:
            if 'xa' in data[each]:
                x3, y3 = data[each]['xa'], each
                x4, y4 = data[each]['xi'], each
            if 'ya' in data[each]:
                x3, y3 = each, data[each]['ya']
                x4, y4 = each, data[each]['yi']
        else:
            x3,y3=data[each]['xi'],each
            x4,y4=each,data[each]['yi']
        d=abs(x3-x4)+abs(y3-y4)
        pre1 = (x3, y3, min(abs(x1 - x4) + abs(y1 - y4) + w1 + d, abs(x2 - x4) + abs(y2 - y4) + w2 + d))
        pre2=(x4,y4,min(abs(x1-x3)+abs(y1-y3)+w1+d,abs(x2-x3)+abs(y2-y3)+w2+d))
    print(min(pre1[2],pre2[2]))

def __starting_point():
    solve()

__starting_point()

import collections, heapq

def dijkstra(g, st):
    """Dijkstra method"""

    n = len(g)
    d = [float('inf')] * n
    d[st] = 0

    que = [(0, st)]     # (min_dist, vertex)
    heapq.heapify(que)

    while len(que) > 0:
        dist, v0 = heapq.heappop(que)
        if d[v0] < dist: continue
        for v1, dist in g[v0]:
            if d[v1] > d[v0] + dist:
                d[v1] = d[v0] + dist
                heapq.heappush(que, (d[v1], v1))

    return d

n = int(input())
p = [tuple(map(int, input().split())) for _ in range(n)]

d = collections.defaultdict(list)

for pi in p:
  d[max(pi[0],pi[1])].append(pi)

levels = list(d.keys())
levels.sort()

g = [[] for _ in range(2*(len(levels)+1))]

ans = 0
last = [(0,0)]
for k, l in enumerate(levels):
  d[l].sort(key=lambda x: (x[0], -x[1]))
  if d[l][0][0] == d[l][-1][0]:
    ans += d[l][0][1] - d[l][-1][1] 
  elif d[l][0][1] == d[l][-1][1]:
    ans += d[l][-1][0] - d[l][0][0]
  else:
    ans += (l-d[l][0][0]) + (l-d[l][-1][1])
  
  cand = [d[l][0]]
  if len(d[l]) > 1:
    cand.append(d[l][-1])
    
  for i, vi in enumerate(last):
    for j, vj in enumerate(cand):
      dist = abs(last[i-1][0]-vj[0]) + abs(last[i-1][1]-vj[1])
      g[2*k+i].append((2*k+2+j, dist))
      g[2*k+2+j].append((2*k+i, dist))

  last = cand

# print(g)
res = dijkstra(g, 0)
print(ans+min(res[-2:]))


n = int(input())
f = [0] * (n + 1)
p = [(0, 0, 0)] * (n + 1)
for i in range(1, n + 1):
	x, y = map(int, input().split())
	p[i] = (x, y, max(x, y))

p.sort(key=lambda x : (x[2], x[0] - x[1]))

def dis(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1])

lasi = lasj = 0
i = 1
while i <= n:
	j = i
	while j < n and p[j + 1][2] == p[i][2]:
		j += 1
	for k in {i, j}:
		f[i ^ j ^ k] = dis(p[i], p[j]) + min(f[l] + dis(p[l], p[k]) for l in {lasi, lasj})
	lasi, lasj = i, j
	i = j + 1

print(min(f[lasi], f[lasj]))

import sys

def minp():
	return sys.stdin.readline().strip()

def dist(x1,y1,x2,y2):
	return abs(x1-x2)+abs(y1-y2)

n = int(minp())
a = [None]*n
for i in range(n):
	x,y = list(map(int,minp().split()))
	a[i] = (max(x,y),x,-y)
a.sort()
#print(a)
p = [None]*2
d = [None]*2
p[0] = [None]*(n+1)
p[1] = [None]*(n+1)
d[0] = [None]*(n+1)
d[1] = [None]*(n+1)
d[0][0] = 0
d[1][0] = 0
p[0][0] = (0,0,0)
p[1][0] = (0,0,0)
i = 0
k = 1
while i < n:
	x = a[i]
	xx = x[0]
	j = i + 1
	while j < n and a[j][0] == xx:
		j += 1
	y = a[j-1]
	p0 = p[0][k-1]
	p1 = p[1][k-1]
	d0 = d[0][k-1]
	d1 = d[1][k-1]
	dd = dist(x[1],x[2],y[1],y[2])
	d2 = dist(p0[1],p0[2],x[1],x[2])
	d3 = dist(p1[1],p1[2],x[1],x[2])
	d[0][k] = min(d0+d2,d1+d3)+dd
	p[0][k] = y
	d2 = dist(p0[1],p0[2],y[1],y[2])
	d3 = dist(p1[1],p1[2],y[1],y[2])
	d[1][k] = min(d0+d2,d1+d3)+dd
	p[1][k] = x
	k += 1
	i = j
print(min(d[0][k-1],d[1][k-1]))


import sys

def minp():
	return sys.stdin.readline().strip()

def dist(a,b):
	return abs(a[1]-b[1])+abs(a[2]-b[2])

n = int(minp())
a = [None]*n
for i in range(n):
	x,y = list(map(int,minp().split()))
	a[i] = (max(x,y),x,-y)
a.sort()
#print(a)
d0 = 0
d1 = 0
p0 = (0,0,0)
p1 = (0,0,0)
i = 0
k = 1
while i < n:
	x = a[i]
	xx = x[0]
	j = i + 1
	while j < n and a[j][0] == xx:
		j += 1
	y = a[j-1]
	dd = dist(x,y)
	d2 = dist(p0,x)
	d3 = dist(p1,x)
	D0 = min(d0+d2,d1+d3)+dd
	P0 = y
	d2 = dist(p0,y)
	d3 = dist(p1,y)
	D1 = min(d0+d2,d1+d3)+dd
	P1 = x
	p0 = P0
	p1 = P1
	d0 = D0
	d1 = D1
	k += 1
	i = j
print(min(d0,d1))


def distance(a,b):
    return(abs(a[0]-b[0])+abs(a[1]-b[1]))
n=int(input())
keys=[]
for i in range(n):
    keys.append(tuple(map(int,input().split())))
dict={}
levels=[]
for key in keys:
    level=max(key)
    if level not in dict:
        levels.append(level)
        dict[level]=[key,key]
    else:
        if distance(key,(0,level))<distance(dict[level][0],(0,level)):
            dict[level]=[key,dict[level][1]]
        if distance(key,(level,0))<distance(dict[level][1],(level,0)):
            dict[level]=[dict[level][0],key]
levels.sort()
left=0
right=0
leftpoint=(0,0)
rightpoint=(0,0)
for level in levels:
    r=distance(dict[level][1],dict[level][0])
    newright=min(right+distance(rightpoint,dict[level][0])+r,left+distance(leftpoint,dict[level][0])+r)
    newleft=min(left+distance(leftpoint,dict[level][1])+r,right+distance(rightpoint,dict[level][1])+r)
    leftpoint=dict[level][0]
    rightpoint=dict[level][1]
    left,right=(newleft,newright)
print(min(left,right))

def get_input_list():
	return list(map(int, input().split()))
def sort_(p):
	np = []
	for i in p:
		np.append([i[0],-i[1]])
	np.sort()
	return np

def distance(A,B):
	return abs(B[0] - A[0]) + abs(B[1] - A[1])

n = int(input())
p_ = []
for _ in range(n):
	p_.append(get_input_list())
d = {}
for i in p_:
	if (str(max(i))) in d:
		d[str(max(i))].append(i)
	else:
		d[str(max(i))] = [i]
l = [int(i) for i in d]
l.sort()
left = [0,0]
right = [0,0]
sleft = 0
sright = 0
for i_ in l:
	i = str(i_)
	p = sort_(d[i])
	left_ = p[0]
	right_ = p[-1]
	a1 = distance(left, left_)
	b1 = distance(left, right_)
	a2 = distance(right, left_)
	b2 = distance(right, right_)
	c = distance(p[0],p[-1])

	sl = sleft
	sr = sright

	sleft = min(sr + a1, sl + a2) + c
	sright = min(sr + b1, sl + b2) + c

	left = left_
	right = right_
print(min(sleft, sright))

def get_input_list():
	return list(map(int, input().split()))
def sort_(p):
	np = []
	for i in p:
		np.append([i[0],-i[1]])
	np.sort()
	return np
def distance(A,B):
	return abs(B[0] - A[0]) + abs(B[1] - A[1])

n = int(input())
p_ = []
for _ in range(n):
	p_.append(get_input_list())
d = {}
for i in p_:
	if (str(max(i))) in d:
		d[str(max(i))].append(i)
	else:
		d[str(max(i))] = [i]
l = [int(i) for i in d]
l.sort()
p1 = [0,0]
p2 = [0,0]
s1 = 0 # Path to p2
s2 = 0 # Path to p1
for i_ in l:
	i = str(i_)
	p = sort_(d[i])
	a1 = distance(p1,p[0])
	b1 = distance(p1,p[-1])
	a2 = distance(p2,p[0])
	b2 = distance(p2,p[-1])
	c = distance(p[0],p[-1])
	s1_ = s1
	s2_ = s2
	s1 = min(s2_+a1,s1_+a2) + c
	s2 = min(s2_+b1,s1_+b2) + c
	p1 = p[0]
	p2 = p[-1]
print(min(s1,s2))

from sys import stdin
n=int(stdin.readline().strip())
s=[]
s1=[]
for i in range(n):
    a,b=list(map(int,stdin.readline().strip().split()))
    s.append((a,b))
    s1.append((b,a))
s.sort()
s1.sort(reverse=True)
mt=dict()
for i in s:
    if i[0]<=i[1]:
        if i[1] in mt:
            mt[i[1]].append(i)
        else:
            mt.update({i[1]:[i]})
for i in s1:
    if i[1]>i[0]:
        if i[1] in mt:
            mt[i[1]].append((i[1],i[0]))
        else:
            mt.update({i[1]:[(i[1],i[0])]})
v=[[(0,0)]]
k=list(mt.keys())
k.sort()
for i in k:
    v.append(mt[i])
n=len(v)
dp=[[-1,-1] for i in range(n)]
dp[0][0]=0
dp[0][1]=0
dist=[0 for i in range(n)]
for i in range(1,n):
    x=0
    for j in range(1,len(v[i])):
        x+=abs(v[i][j][0]-v[i][j-1][0])+abs(v[i][j][1]-v[i][j-1][1])
    dist[i]=x
for i in range(1,n):
    dp[i][1]=dist[i]+(min(dp[i-1][1]+abs(v[i][0][0]-v[i-1][-1][0])+abs(v[i][0][1]-v[i-1][-1][1]),dp[i-1][0]+abs(v[i][0][0]-v[i-1][0][0])+abs(v[i][0][1]-v[i-1][0][1])))
    dp[i][0]=dist[i]+(min(dp[i-1][1]+abs(v[i][-1][0]-v[i-1][-1][0])+abs(v[i][-1][1]-v[i-1][-1][1]),dp[i-1][0]+abs(v[i][-1][0]-v[i-1][0][0])+abs(v[i][-1][1]-v[i-1][0][1])))    
print(min(dp[-1]))
                 
    

    


from sys import stdin
n=int(stdin.readline().strip())
s=[]
s1=[]
for i in range(n):
    a,b=list(map(int,stdin.readline().strip().split()))
    s.append((a,b))
    s1.append((b,a))
s.sort()
s1.sort(reverse=True)
mt=dict()
for i in s:
    if i[0]<=i[1]:
        if i[1] in mt:
            mt[i[1]].append(i)
        else:
            mt.update({i[1]:[i]})
for i in s1:
    if i[1]>i[0]:
        if i[1] in mt:
            mt[i[1]].append((i[1],i[0]))
        else:
            mt.update({i[1]:[(i[1],i[0])]})
v=[[(0,0)]]
k=list(mt.keys())
k.sort()
for i in k:
    v.append(mt[i])
n=len(v)
dp=[[-1,-1] for i in range(n)]
dp[0][0]=0
dp[0][1]=0
dist=[0 for i in range(n)]
for i in range(1,n):
    x=0
    for j in range(1,len(v[i])):
        x+=abs(v[i][j][0]-v[i][j-1][0])+abs(v[i][j][1]-v[i][j-1][1])
    dist[i]=x
for i in range(1,n):
    dp[i][1]=dist[i]+(min(dp[i-1][1]+abs(v[i][0][0]-v[i-1][-1][0])+abs(v[i][0][1]-v[i-1][-1][1]),dp[i-1][0]+abs(v[i][0][0]-v[i-1][0][0])+abs(v[i][0][1]-v[i-1][0][1])))
    dp[i][0]=dist[i]+(min(dp[i-1][1]+abs(v[i][-1][0]-v[i-1][-1][0])+abs(v[i][-1][1]-v[i-1][-1][1]),dp[i-1][0]+abs(v[i][-1][0]-v[i-1][0][0])+abs(v[i][-1][1]-v[i-1][0][1])))    
print(min(dp[-1]))
                 
    

    


n = int(input())
f = [0] * (n + 1)
p = [(0, 0, 0)] * (n + 1)
for i in range(1, n + 1):
	x, y = map(int, input().split())
	p[i] = (x, y, max(x, y))

p.sort(key=lambda x : (x[2], x[0] - x[1]))

def dis(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1])

lasi = lasj = 0
i = 1
while i <= n:
	j = i
	while j < n and p[j + 1][2] == p[i][2]:
		j += 1
	for k in {i, j}:
		f[i ^ j ^ k] = dis(p[i], p[j]) + min(f[l] + dis(p[l], p[k]) for l in {lasi, lasj})
	lasi, lasj = i, j
	i = j + 1

print(min(f[lasi], f[lasj]))

#!/usr/bin/env python3

import sys
import traceback

class Input(object):
    def __init__(self):
        self.fh = sys.stdin

    def next_line(self):
        while True:
            line = sys.stdin.readline()
            if line == '\n':
                continue
            return line


    def next_line_ints(self):
        line = self.next_line()
        return [int(x) for x in line.split()]

    def next_line_strs(self):
        line = self.next_line()
        return line.split()

def get_dist(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

def calculate_finish_cost(dp_reach, points):
    """ Return dp_finish of this level. """
    assert len(dp_reach) == len(points)
    if len(points) == 1:
        return dp_reach
    round_cost = get_dist(points[0], points[-1])
    # dp_finish = min(2 * round_cost + (dp[p1] - dist)). omit 2 * round_cost for now.
    dp_finish = dp_reach[:]
    min_diff = dp_reach[0]
    for i in range(1, len(points)):
        min_diff = min(min_diff - get_dist(points[i], points[i-1]), dp_reach[i])
        dp_finish[i] = min(min_diff, dp_finish[i])
    min_diff = dp_reach[-1]
    for i in range(len(points) - 2, -1, -1):
        min_diff = min(min_diff - get_dist(points[i], points[i+1]), dp_reach[i])
        dp_finish[i] = min(min_diff, dp_finish[i])
    assert len(dp_finish) == len(points)
    return [x + 2 * round_cost for x in dp_finish]

def calculate_reach_cost(dp_finish, from_points, to_points):
    """calculate from dp_finish of current level to the dp_reach of the next level."""
    assert len(dp_finish) == len(from_points)
    from_k = [y/max(x, 0.5) for x, y in from_points]
    to_k = [y/max(x, 0.5) for x, y in to_points]
    dp_reach = []
    from_index = 0
    for i in range(len(to_points)):
        while from_index + 1 < len(from_points) and from_k[from_index + 1] > to_k[i]:
            from_index += 1
        dp = dp_finish[from_index] + get_dist(from_points[from_index], to_points[i])
        if from_index + 1 < len(from_points):
            dp = min(dp, dp_finish[from_index + 1] + get_dist(from_points[from_index + 1], to_points[i]))
        dp_reach.append(dp)
    assert len(dp_reach) == len(to_points)
    return dp_reach


def get_min_dist(points):
    # 1. split points into levels, sort points in each level in x increase, y decrease order.
    level_dict = {}
    for point in points:
        level = max(point[0], point[1])
        if level in level_dict:
            level_dict[level].append(point)
        else:
            level_dict[level] = [point]
    level_points = []
    for level in sorted(level_dict.keys()):
        p = level_dict[level]
        level_points.append(sorted(p, key=lambda x: x[0] - x[1]))

    # 2. calculate the min cost to reach a level at a point.
    #    calculate the min cost to finish a level at a point.
    dp_reach = []
    for p in level_points[0]:
        dp_reach.append(p[0] + p[1])
    dp_finish = calculate_finish_cost(dp_reach, level_points[0])
    for i in range(len(level_points) - 1):
        from_points = level_points[i]
        to_points = level_points[i + 1]
        dp_reach = calculate_reach_cost(dp_finish, from_points, to_points)
        dp_finish = calculate_finish_cost(dp_reach, to_points)

    # 3. the result is to finish at any points at the last level.
    return min(dp_finish)

def main():
    input = Input()
    while True:
        try:
            nums = input.next_line_ints()
            if not nums:
                break
            n = nums[0]
            points = []
            for _ in range(n):
                x, y = input.next_line_ints()
                points.append((x, y))
        except:
            print('read input failed')
        try:
            min_dist = get_min_dist(points)
        except:
            traceback.print_exc(file=sys.stdout)
            print('get_min_dist failed')
        print("{}".format(min_dist))

main()

from collections import defaultdict
n = int(input())
points = defaultdict(list)
points[0].append((0,0))
for i in range(n):
	x,y = list(map(int,input().split()))
	points[max(x,y)].append((x,y))
for level in points:
	points[level].sort(key=lambda x:(x[0],-x[1]))
levels = sorted(points.keys())
dp = [[0,0] for i in levels]
dist = lambda a,b:abs(a[0]-b[0])+abs(a[1]-b[1])
for i in range(1,len(levels)):
	start = points[levels[i]][0]
	end = points[levels[i]][-1]
	prevstart = points[levels[i-1]][0]
	prevend = points[levels[i-1]][-1]
	dp[i][0] = min(dp[i-1][0]+dist(prevstart,end), dp[i-1][1]+dist(prevend,end)) + dist(start,end)
	dp[i][1] = min(dp[i-1][0]+dist(prevstart,start), dp[i-1][1]+dist(prevend,start)) + dist(start,end)
# print(points)
print(min(dp[-1]))


def dista(a, b):
	return abs(lista[a][0]-lista[b][0]) + abs(lista[a][1]-lista[b][1])


lista = []
ne = 0
n = int(input())
dist = [0] * (n+1)
lista.append((0, 0))
for _ in range(n):
	x, y = list(map(int, input().split()))
	lista.append((x, y))
lista = sorted(lista, key= lambda x: min(x))
lista = sorted(lista, key= lambda x: max(x))
n += 1
ini = 0
ne = 1
oy = 0
ox = 0
while ne < n:
	ini = ne
	maxi = max(lista[ne])
	while ne < n and max(lista[ne]) == maxi:
		ne += 1
	minx = ini
	miny = ini
	for i in range(ini, ne):
		if lista[i][0] < lista[minx][0]:
			minx = i
		elif lista[i][0] == lista[minx][0] and lista[i][1] > lista[minx][1]:
			minx = i
		if lista[i][1] < lista[miny][1]:
			miny = i
		elif lista[i][1] == lista[miny][1] and lista[i][0] > lista[miny][0]:
			miny = i

	mxy = dista(minx, miny)
	if dista(miny, ox) + dist[ox] < dist[oy] + dista(miny, oy):
		dist[minx] = dista(ox, miny) + dist[ox] + mxy
	else:
		dist[minx] = dista(oy, miny) + dist[oy] + mxy

	if dista(ox, minx) + dist[ox] < dist[oy] + dista(oy, minx):
		dist[miny] = dista(ox, minx) + dist[ox] + mxy
	else:
		dist[miny] = dista(oy, minx) + dist[oy] + mxy
	ox = minx
	oy = miny
print(min(dist[miny], dist[minx]))


import itertools as it

def dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def spir_dist(x):
    a, b = x
    if a >= b:
        return b
    else:
        return 2 * b - a

n = int(input())

A = [[0, 0]]

for _ in range(n):
    x, y = list(map(int, input().split()))
    A += [[x, y]]

A_s = sorted(A, key=max)

A_g = it.groupby(A_s, key=max)

A_t = [p + p if len(p) == 1 else [p[0], p[-1]]
       for p in [sorted(list(q[1]), key=spir_dist) for q in A_g]]

B = [[0,0]]

for i in range(1, len(A_t)):
    pa, pb = A_t[i]
    d = dist(pa, pb)
    y = min([B[i - 1][k] + dist(A_t[i - 1][k], pa) for k in [0, 1]]) + d
    x = min([B[i - 1][k] + dist(A_t[i - 1][k], pb) for k in [0, 1]]) + d
    B += [[x, y]]

print(min(B[len(A_t) - 1]))


import itertools as it

def dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def spir_dist(x):
    a, b = x
    if a >= b:
        return b
    else:
        return 2 * b - a

n = int(input())

A = [[0, 0]]

for _ in range(n):
    x, y = list(map(int, input().split()))
    A += [[x, y]]

A_s = sorted(A, key=max)

A_g = it.groupby(A_s, key=max)

A_t = [p + p if len(p) == 1 else [p[0], p[-1]]
       for p in [sorted(list(q[1]), key=spir_dist) for q in A_g]]

B = [[0,0]]

for i in range(1, len(A_t)):
    pa, pb = A_t[i]
    d = dist(pa, pb)
    y = min([B[i - 1][k] + dist(A_t[i - 1][k], pa) for k in [0, 1]]) + d
    x = min([B[i - 1][k] + dist(A_t[i - 1][k], pb) for k in [0, 1]]) + d
    B += [[x, y]]

print(min(B[len(A_t) - 1]))


import sys

def cal(a,b):
    return abs(a[0]-b[0])+abs(a[1]-b[1])

def cmp(a,b):
    if a[0]!=b[0]:return a[0]<b[0]
    return a[1]>b[1]

rd=sys.stdin.readlines()
n=int(rd[0])
data={}
for _ in range(0,n):
    x,y=map(int,rd[_+1].split())
    if max(x,y) not in data:
        data[max(x,y)]=[]
    data[max(x,y)].append((x,y))
dp1,dp2=0,0
pre1,pre2=(0,0),(0,0)
for i in sorted(list(data.keys())):
    now1,now2=data[i][0],data[i][0]
    for x in data[i]:
        if cmp(now1,x):now1=x
        if cmp(x,now2):now2=x
    dp1,dp2=min(dp1+cal(pre1,now2)+cal(now2,now1),dp2+cal(pre2,now2)+cal(now2,now1)),min(dp1+cal(pre1,now1)+cal(now1,now2),dp2+cal(pre2,now1)+cal(now1,now2))
    pre1,pre2=now1,now2
print(min(dp1,dp2))

import sys
 
def minp():
	return sys.stdin.readline().strip()
 
def dist(a,b):
	return abs(a[1]-b[1])+abs(a[2]-b[2])
 
n = int(minp())
a = [None]*n
for i in range(n):
	x,y = list(map(int,minp().split()))
	a[i] = (max(x,y),x,-y)
a.sort()
#print(a)
d0 = 0
d1 = 0
p0 = (0,0,0)
p1 = (0,0,0)
i = 0
k = 1
while i < n:
	x = a[i]
	xx = x[0]
	j = i + 1
	while j < n and a[j][0] == xx:
		j += 1
	y = a[j-1]
	dd = dist(x,y)
	d2 = dist(p0,x)
	d3 = dist(p1,x)
	D0 = min(d0+d2,d1+d3)+dd
	P0 = y
	d2 = dist(p0,y)
	d3 = dist(p1,y)
	D1 = min(d0+d2,d1+d3)+dd
	P1 = x
	p0 = P0
	p1 = P1
	d0 = D0
	d1 = D1
	k += 1
	i = j
print(min(d0,d1))
	


import itertools as it
     
def dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])
     
def spir_dist(x):
    a, b = x
    if a >= b:
        return b
    else:
        return 2 * b - a
     
n = int(input())
     
A = [[0, 0]]
     
for _ in range(n):
    x, y = list(map(int, input().split()))
    A += [[x, y]]
     
A_s = sorted(A, key=max)
     
A_g = it.groupby(A_s, key=max)
     
A_t = [p + p if len(p) == 1 else [p[0], p[-1]]
           for p in [sorted(list(q[1]), key=spir_dist) for q in A_g]]
     
B = [[0,0]]
     
for i in range(1, len(A_t)):
    pa, pb = A_t[i]
    d = dist(pa, pb)
    y = min([B[i - 1][k] + dist(A_t[i - 1][k], pa) for k in [0, 1]]) + d
    x = min([B[i - 1][k] + dist(A_t[i - 1][k], pb) for k in [0, 1]]) + d
    B += [[x, y]]
     
print(min(B[len(A_t) - 1]))
#JSR



import itertools as it
     
def dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])
     
def spir_dist(x):
    a, b = x
    if a >= b:
        return b
    else:
        return 2 * b - a
     
n = int(input())
     
A = [[0, 0]]
     
for _ in range(n):
    x, y = list(map(int, input().split()))
    A += [[x, y]]
     
A_s = sorted(A, key=max)
     
A_g = it.groupby(A_s, key=max)
     
A_t = [p + p if len(p) == 1 else [p[0], p[-1]]
           for p in [sorted(list(q[1]), key=spir_dist) for q in A_g]]
     
B = [[0,0]]
     
for i in range(1, len(A_t)):
    pa, pb = A_t[i]
    d = dist(pa, pb)
    y = min([B[i - 1][k] + dist(A_t[i - 1][k], pa) for k in [0, 1]]) + d
    x = min([B[i - 1][k] + dist(A_t[i - 1][k], pb) for k in [0, 1]]) + d
    B += [[x, y]]
     
print(min(B[len(A_t) - 1]))