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: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
from collections import defaultdict
n = int(input())
points = defaultdict(list)
points[0].append((0, 0))
for i in range(n):
	(x, y) = 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(min(dp[-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) = 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
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):
	assert len(dp_reach) == len(points)
	if len(points) == 1:
		return dp_reach
	round_cost = get_dist(points[0], points[-1])
	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):
	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):
	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]))
	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)
	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()


import collections, heapq

def dijkstra(g, st):
	n = len(g)
	d = [float('inf')] * n
	d[st] = 0
	que = [(0, st)]
	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
res = dijkstra(g, 0)
print(ans + min(res[-2:]))


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) = 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]))


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()


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))


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))


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))


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()
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))


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]))


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from heapq import *
from math import gcd, factorial, floor, ceil
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 998244353

def bucketsort(order, seq):
	buckets = [0] * (max(seq) + 1)
	for x in seq:
		buckets[x] += 1
	for i in range(len(buckets) - 1):
		buckets[i + 1] += buckets[i]
	new_order = [-1] * len(seq)
	for i in reversed(order):
		x = seq[i]
		idx = buckets[x] = buckets[x] - 1
		new_order[idx] = i
	return new_order

def ordersort(order, seq, reverse=False):
	bit = max(seq).bit_length() >> 1
	mask = (1 << bit) - 1
	order = bucketsort(order, [x & mask for x in seq])
	order = bucketsort(order, [x >> bit for x in seq])
	if reverse:
		order.reverse()
	return order

def long_ordersort(order, seq):
	order = ordersort(order, [int(i & 2147483647) for i in seq])
	return ordersort(order, [int(i >> 31) for i in seq])

def multikey_ordersort(order, *seqs, sort=ordersort):
	for i in reversed(range(len(seqs))):
		order = sort(order, seqs[i])
	return order
dp = [[inf, inf] for i in range(200010)]

def dist(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]

def solve(case):
	n = int(inp())
	hash = {}
	for i in range(n):
		(a, b) = sep()
		if max(a, b) in hash:
			hash[max(a, b)].append((a, b))
		else:
			hash[max(a, b)] = [(a, b)]
	for i in hash:
		hash[i] = sorted(hash[i])
	level = {}
	for i in hash:
		(ss, ff) = (hash[i][0], hash[i][0])
		for x in hash[i]:
			if cmp(ff, x):
				ff = x
			if cmp(x, ss):
				ss = x
		level[i] = [ff, ss]
	level[0] = [(0, 0), (0, 0)]
	(a, b) = ([], [])
	for i in level:
		a.append(i)
	order = multikey_ordersort(range(len(a)), a)
	for i in order:
		b.append(level[a[i]])
	(dp[0][0], dp[0][1]) = (0, 0)
	for i in range(1, len(a)):
		dp[i][0] = min(dp[i][0], dp[i - 1][0] + dist(b[i - 1][0], b[i][1]) + dist(b[i][0], b[i][1]))
		dp[i][0] = min(dp[i][0], dp[i - 1][1] + dist(b[i - 1][1], b[i][1]) + dist(b[i][0], b[i][1]))
		dp[i][1] = min(dp[i][1], dp[i - 1][0] + dist(b[i - 1][0], b[i][0]) + dist(b[i][0], b[i][1]))
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + dist(b[i - 1][1], b[i][0]) + dist(b[i][0], b[i][1]))
	print(min(dp[len(a) - 1]))
testcase(1)


def f(x, m):
	if x < m:
		return (m, x)
	else:
		return (m * 2 - x, m)
n = int(input())
d = {0: [0]}
for i in range(n):
	(x, y) = map(int, input().split())
	m = max(x, y)
	if m in d:
		if x == m:
			d[m].append(y)
		else:
			d[m].append(m * 2 - x)
	elif x == m:
		d[m] = [y]
	else:
		d[m] = [m * 2 - x]
t = sorted(d.keys())
ans = 0
for k in t:
	d[k].sort()
	ans += d[k][-1] - d[k][0]
dp1 = [0] * len(t)
dp2 = [0] * len(t)
for i in range(len(t) - 1):
	k = t[i]
	k2 = t[i + 1]
	(x11, y11) = f(d[k][0], k)
	(x12, y12) = f(d[k][-1], k)
	(x21, y21) = f(d[k2][0], k2)
	(x22, y22) = f(d[k2][-1], k2)
	dp1[i + 1] = min(dp1[i] + abs(x11 - x22) + abs(y11 - y22), dp2[i] + abs(x12 - x22) + abs(y12 - y22))
	dp2[i + 1] = min(dp1[i] + abs(x11 - x21) + abs(y11 - y21), dp2[i] + abs(x12 - x21) + abs(y12 - y21))
print(min(dp1[-1], dp2[-1]) + ans)


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()
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]))


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
s2 = 0
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))