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$.
[{"code": "\n\ndef solve():\n    Point=[]\n    n=int(input())\n    for i in range(n):\n        x,y=list(map(int,input().split()))\n        Point.append((x,y))\n    data={}\n    for each in Point:\n        if each[0]<each[1]:\n            try:\n                tm=data[each[1]]\n            except KeyError:\n                data[each[1]]={}\n            try:\n                data[each[1]]['xi']=min(data[each[1]]['xi'],each[0])\n            except KeyError:\n                data[each[1]]['xi']=each[0]\n            try:\n                data[each[1]]['xa'] = max(data[each[1]]['xa'], each[0])\n            except KeyError:\n                data[each[1]]['xa'] = each[0]\n        else:\n            try:\n                tm=data[each[0]]\n            except KeyError:\n                data[each[0]]={}\n            try:\n                data[each[0]]['yi']=min(data[each[0]]['yi'],each[1])\n            except KeyError:\n                data[each[0]]['yi']=each[1]\n            try:\n                data[each[0]]['ya']=max(data[each[0]]['ya'],each[1])\n            except KeyError:\n                data[each[0]]['ya'] = each[1]\n    pre1=(0,0,0)\n    pre2=(0,0,0)\n    for each in sorted(data.keys()):\n        x1,y1,w1=pre1\n        x2,y2,w2=pre2\n        if len(data[each])==2:\n            if 'xa' in data[each]:\n                x3, y3 = data[each]['xa'], each\n                x4, y4 = data[each]['xi'], each\n            if 'ya' in data[each]:\n                x3, y3 = each, data[each]['ya']\n                x4, y4 = each, data[each]['yi']\n        else:\n            x3,y3=data[each]['xi'],each\n            x4,y4=each,data[each]['yi']\n        d=abs(x3-x4)+abs(y3-y4)\n        pre1 = (x3, y3, min(abs(x1 - x4) + abs(y1 - y4) + w1 + d, abs(x2 - x4) + abs(y2 - y4) + w2 + d))\n        pre2=(x4,y4,min(abs(x1-x3)+abs(y1-y3)+w1+d,abs(x2-x3)+abs(y2-y3)+w2+d))\n    print(min(pre1[2],pre2[2]))\n\ndef __starting_point():\n    solve()\n\n__starting_point()", "passed": true, "time": 0.15, "memory": 14352.0, "status": "done"}, {"code": "import collections, heapq\n\ndef dijkstra(g, st):\n    \"\"\"Dijkstra method\"\"\"\n\n    n = len(g)\n    d = [float('inf')] * n\n    d[st] = 0\n\n    que = [(0, st)]     # (min_dist, vertex)\n    heapq.heapify(que)\n\n    while len(que) > 0:\n        dist, v0 = heapq.heappop(que)\n        if d[v0] < dist: continue\n        for v1, dist in g[v0]:\n            if d[v1] > d[v0] + dist:\n                d[v1] = d[v0] + dist\n                heapq.heappush(que, (d[v1], v1))\n\n    return d\n\nn = int(input())\np = [tuple(map(int, input().split())) for _ in range(n)]\n\nd = collections.defaultdict(list)\n\nfor pi in p:\n  d[max(pi[0],pi[1])].append(pi)\n\nlevels = list(d.keys())\nlevels.sort()\n\ng = [[] for _ in range(2*(len(levels)+1))]\n\nans = 0\nlast = [(0,0)]\nfor k, l in enumerate(levels):\n  d[l].sort(key=lambda x: (x[0], -x[1]))\n  if d[l][0][0] == d[l][-1][0]:\n    ans += d[l][0][1] - d[l][-1][1] \n  elif d[l][0][1] == d[l][-1][1]:\n    ans += d[l][-1][0] - d[l][0][0]\n  else:\n    ans += (l-d[l][0][0]) + (l-d[l][-1][1])\n  \n  cand = [d[l][0]]\n  if len(d[l]) > 1:\n    cand.append(d[l][-1])\n    \n  for i, vi in enumerate(last):\n    for j, vj in enumerate(cand):\n      dist = abs(last[i-1][0]-vj[0]) + abs(last[i-1][1]-vj[1])\n      g[2*k+i].append((2*k+2+j, dist))\n      g[2*k+2+j].append((2*k+i, dist))\n\n  last = cand\n\n# print(g)\nres = dijkstra(g, 0)\nprint(ans+min(res[-2:]))\n", "passed": true, "time": 0.15, "memory": 14244.0, "status": "done"}, {"code": "n = int(input())\nf = [0] * (n + 1)\np = [(0, 0, 0)] * (n + 1)\nfor i in range(1, n + 1):\n\tx, y = map(int, input().split())\n\tp[i] = (x, y, max(x, y))\n\np.sort(key=lambda x : (x[2], x[0] - x[1]))\n\ndef dis(a, b):\n\treturn abs(a[0] - b[0]) + abs(a[1] - b[1])\n\nlasi = lasj = 0\ni = 1\nwhile i <= n:\n\tj = i\n\twhile j < n and p[j + 1][2] == p[i][2]:\n\t\tj += 1\n\tfor k in {i, j}:\n\t\tf[i ^ j ^ k] = dis(p[i], p[j]) + min(f[l] + dis(p[l], p[k]) for l in {lasi, lasj})\n\tlasi, lasj = i, j\n\ti = j + 1\n\nprint(min(f[lasi], f[lasj]))", "passed": true, "time": 0.14, "memory": 14412.0, "status": "done"}, {"code": "import sys\n\ndef minp():\n\treturn sys.stdin.readline().strip()\n\ndef dist(x1,y1,x2,y2):\n\treturn abs(x1-x2)+abs(y1-y2)\n\nn = int(minp())\na = [None]*n\nfor i in range(n):\n\tx,y = list(map(int,minp().split()))\n\ta[i] = (max(x,y),x,-y)\na.sort()\n#print(a)\np = [None]*2\nd = [None]*2\np[0] = [None]*(n+1)\np[1] = [None]*(n+1)\nd[0] = [None]*(n+1)\nd[1] = [None]*(n+1)\nd[0][0] = 0\nd[1][0] = 0\np[0][0] = (0,0,0)\np[1][0] = (0,0,0)\ni = 0\nk = 1\nwhile i < n:\n\tx = a[i]\n\txx = x[0]\n\tj = i + 1\n\twhile j < n and a[j][0] == xx:\n\t\tj += 1\n\ty = a[j-1]\n\tp0 = p[0][k-1]\n\tp1 = p[1][k-1]\n\td0 = d[0][k-1]\n\td1 = d[1][k-1]\n\tdd = dist(x[1],x[2],y[1],y[2])\n\td2 = dist(p0[1],p0[2],x[1],x[2])\n\td3 = dist(p1[1],p1[2],x[1],x[2])\n\td[0][k] = min(d0+d2,d1+d3)+dd\n\tp[0][k] = y\n\td2 = dist(p0[1],p0[2],y[1],y[2])\n\td3 = dist(p1[1],p1[2],y[1],y[2])\n\td[1][k] = min(d0+d2,d1+d3)+dd\n\tp[1][k] = x\n\tk += 1\n\ti = j\nprint(min(d[0][k-1],d[1][k-1]))\n", "passed": true, "time": 0.14, "memory": 14216.0, "status": "done"}, {"code": "import sys\n\ndef minp():\n\treturn sys.stdin.readline().strip()\n\ndef dist(a,b):\n\treturn abs(a[1]-b[1])+abs(a[2]-b[2])\n\nn = int(minp())\na = [None]*n\nfor i in range(n):\n\tx,y = list(map(int,minp().split()))\n\ta[i] = (max(x,y),x,-y)\na.sort()\n#print(a)\nd0 = 0\nd1 = 0\np0 = (0,0,0)\np1 = (0,0,0)\ni = 0\nk = 1\nwhile i < n:\n\tx = a[i]\n\txx = x[0]\n\tj = i + 1\n\twhile j < n and a[j][0] == xx:\n\t\tj += 1\n\ty = a[j-1]\n\tdd = dist(x,y)\n\td2 = dist(p0,x)\n\td3 = dist(p1,x)\n\tD0 = min(d0+d2,d1+d3)+dd\n\tP0 = y\n\td2 = dist(p0,y)\n\td3 = dist(p1,y)\n\tD1 = min(d0+d2,d1+d3)+dd\n\tP1 = x\n\tp0 = P0\n\tp1 = P1\n\td0 = D0\n\td1 = D1\n\tk += 1\n\ti = j\nprint(min(d0,d1))\n", "passed": true, "time": 0.14, "memory": 14276.0, "status": "done"}, {"code": "def distance(a,b):\n    return(abs(a[0]-b[0])+abs(a[1]-b[1]))\nn=int(input())\nkeys=[]\nfor i in range(n):\n    keys.append(tuple(map(int,input().split())))\ndict={}\nlevels=[]\nfor key in keys:\n    level=max(key)\n    if level not in dict:\n        levels.append(level)\n        dict[level]=[key,key]\n    else:\n        if distance(key,(0,level))<distance(dict[level][0],(0,level)):\n            dict[level]=[key,dict[level][1]]\n        if distance(key,(level,0))<distance(dict[level][1],(level,0)):\n            dict[level]=[dict[level][0],key]\nlevels.sort()\nleft=0\nright=0\nleftpoint=(0,0)\nrightpoint=(0,0)\nfor level in levels:\n    r=distance(dict[level][1],dict[level][0])\n    newright=min(right+distance(rightpoint,dict[level][0])+r,left+distance(leftpoint,dict[level][0])+r)\n    newleft=min(left+distance(leftpoint,dict[level][1])+r,right+distance(rightpoint,dict[level][1])+r)\n    leftpoint=dict[level][0]\n    rightpoint=dict[level][1]\n    left,right=(newleft,newright)\nprint(min(left,right))", "passed": true, "time": 0.22, "memory": 14344.0, "status": "done"}, {"code": "def get_input_list():\n\treturn list(map(int, input().split()))\ndef sort_(p):\n\tnp = []\n\tfor i in p:\n\t\tnp.append([i[0],-i[1]])\n\tnp.sort()\n\treturn np\n\ndef distance(A,B):\n\treturn abs(B[0] - A[0]) + abs(B[1] - A[1])\n\nn = int(input())\np_ = []\nfor _ in range(n):\n\tp_.append(get_input_list())\nd = {}\nfor i in p_:\n\tif (str(max(i))) in d:\n\t\td[str(max(i))].append(i)\n\telse:\n\t\td[str(max(i))] = [i]\nl = [int(i) for i in d]\nl.sort()\nleft = [0,0]\nright = [0,0]\nsleft = 0\nsright = 0\nfor i_ in l:\n\ti = str(i_)\n\tp = sort_(d[i])\n\tleft_ = p[0]\n\tright_ = p[-1]\n\ta1 = distance(left, left_)\n\tb1 = distance(left, right_)\n\ta2 = distance(right, left_)\n\tb2 = distance(right, right_)\n\tc = distance(p[0],p[-1])\n\n\tsl = sleft\n\tsr = sright\n\n\tsleft = min(sr + a1, sl + a2) + c\n\tsright = min(sr + b1, sl + b2) + c\n\n\tleft = left_\n\tright = right_\nprint(min(sleft, sright))", "passed": true, "time": 0.14, "memory": 14236.0, "status": "done"}, {"code": "def get_input_list():\n\treturn list(map(int, input().split()))\ndef sort_(p):\n\tnp = []\n\tfor i in p:\n\t\tnp.append([i[0],-i[1]])\n\tnp.sort()\n\treturn np\ndef distance(A,B):\n\treturn abs(B[0] - A[0]) + abs(B[1] - A[1])\n\nn = int(input())\np_ = []\nfor _ in range(n):\n\tp_.append(get_input_list())\nd = {}\nfor i in p_:\n\tif (str(max(i))) in d:\n\t\td[str(max(i))].append(i)\n\telse:\n\t\td[str(max(i))] = [i]\nl = [int(i) for i in d]\nl.sort()\np1 = [0,0]\np2 = [0,0]\ns1 = 0 # Path to p2\ns2 = 0 # Path to p1\nfor i_ in l:\n\ti = str(i_)\n\tp = sort_(d[i])\n\ta1 = distance(p1,p[0])\n\tb1 = distance(p1,p[-1])\n\ta2 = distance(p2,p[0])\n\tb2 = distance(p2,p[-1])\n\tc = distance(p[0],p[-1])\n\ts1_ = s1\n\ts2_ = s2\n\ts1 = min(s2_+a1,s1_+a2) + c\n\ts2 = min(s2_+b1,s1_+b2) + c\n\tp1 = p[0]\n\tp2 = p[-1]\nprint(min(s1,s2))", "passed": true, "time": 0.14, "memory": 14400.0, "status": "done"}, {"code": "from sys import stdin\nn=int(stdin.readline().strip())\ns=[]\ns1=[]\nfor i in range(n):\n    a,b=list(map(int,stdin.readline().strip().split()))\n    s.append((a,b))\n    s1.append((b,a))\ns.sort()\ns1.sort(reverse=True)\nmt=dict()\nfor i in s:\n    if i[0]<=i[1]:\n        if i[1] in mt:\n            mt[i[1]].append(i)\n        else:\n            mt.update({i[1]:[i]})\nfor i in s1:\n    if i[1]>i[0]:\n        if i[1] in mt:\n            mt[i[1]].append((i[1],i[0]))\n        else:\n            mt.update({i[1]:[(i[1],i[0])]})\nv=[[(0,0)]]\nk=list(mt.keys())\nk.sort()\nfor i in k:\n    v.append(mt[i])\nn=len(v)\ndp=[[-1,-1] for i in range(n)]\ndp[0][0]=0\ndp[0][1]=0\ndist=[0 for i in range(n)]\nfor i in range(1,n):\n    x=0\n    for j in range(1,len(v[i])):\n        x+=abs(v[i][j][0]-v[i][j-1][0])+abs(v[i][j][1]-v[i][j-1][1])\n    dist[i]=x\nfor i in range(1,n):\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])))\n    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])))    \nprint(min(dp[-1]))\n                 \n    \n\n    \n", "passed": true, "time": 0.15, "memory": 14240.0, "status": "done"}, {"code": "from sys import stdin\nn=int(stdin.readline().strip())\ns=[]\ns1=[]\nfor i in range(n):\n    a,b=list(map(int,stdin.readline().strip().split()))\n    s.append((a,b))\n    s1.append((b,a))\ns.sort()\ns1.sort(reverse=True)\nmt=dict()\nfor i in s:\n    if i[0]<=i[1]:\n        if i[1] in mt:\n            mt[i[1]].append(i)\n        else:\n            mt.update({i[1]:[i]})\nfor i in s1:\n    if i[1]>i[0]:\n        if i[1] in mt:\n            mt[i[1]].append((i[1],i[0]))\n        else:\n            mt.update({i[1]:[(i[1],i[0])]})\nv=[[(0,0)]]\nk=list(mt.keys())\nk.sort()\nfor i in k:\n    v.append(mt[i])\nn=len(v)\ndp=[[-1,-1] for i in range(n)]\ndp[0][0]=0\ndp[0][1]=0\ndist=[0 for i in range(n)]\nfor i in range(1,n):\n    x=0\n    for j in range(1,len(v[i])):\n        x+=abs(v[i][j][0]-v[i][j-1][0])+abs(v[i][j][1]-v[i][j-1][1])\n    dist[i]=x\nfor i in range(1,n):\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])))\n    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])))    \nprint(min(dp[-1]))\n                 \n    \n\n    \n", "passed": true, "time": 0.14, "memory": 14448.0, "status": "done"}, {"code": "n = int(input())\nf = [0] * (n + 1)\np = [(0, 0, 0)] * (n + 1)\nfor i in range(1, n + 1):\n\tx, y = map(int, input().split())\n\tp[i] = (x, y, max(x, y))\n\np.sort(key=lambda x : (x[2], x[0] - x[1]))\n\ndef dis(a, b):\n\treturn abs(a[0] - b[0]) + abs(a[1] - b[1])\n\nlasi = lasj = 0\ni = 1\nwhile i <= n:\n\tj = i\n\twhile j < n and p[j + 1][2] == p[i][2]:\n\t\tj += 1\n\tfor k in {i, j}:\n\t\tf[i ^ j ^ k] = dis(p[i], p[j]) + min(f[l] + dis(p[l], p[k]) for l in {lasi, lasj})\n\tlasi, lasj = i, j\n\ti = j + 1\n\nprint(min(f[lasi], f[lasj]))", "passed": true, "time": 0.14, "memory": 14376.0, "status": "done"}, {"code": "#!/usr/bin/env python3\n\nimport sys\nimport traceback\n\nclass Input(object):\n    def __init__(self):\n        self.fh = sys.stdin\n\n    def next_line(self):\n        while True:\n            line = sys.stdin.readline()\n            if line == '\\n':\n                continue\n            return line\n\n\n    def next_line_ints(self):\n        line = self.next_line()\n        return [int(x) for x in line.split()]\n\n    def next_line_strs(self):\n        line = self.next_line()\n        return line.split()\n\ndef get_dist(p1, p2):\n    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])\n\ndef calculate_finish_cost(dp_reach, points):\n    \"\"\" Return dp_finish of this level. \"\"\"\n    assert len(dp_reach) == len(points)\n    if len(points) == 1:\n        return dp_reach\n    round_cost = get_dist(points[0], points[-1])\n    # dp_finish = min(2 * round_cost + (dp[p1] - dist)). omit 2 * round_cost for now.\n    dp_finish = dp_reach[:]\n    min_diff = dp_reach[0]\n    for i in range(1, len(points)):\n        min_diff = min(min_diff - get_dist(points[i], points[i-1]), dp_reach[i])\n        dp_finish[i] = min(min_diff, dp_finish[i])\n    min_diff = dp_reach[-1]\n    for i in range(len(points) - 2, -1, -1):\n        min_diff = min(min_diff - get_dist(points[i], points[i+1]), dp_reach[i])\n        dp_finish[i] = min(min_diff, dp_finish[i])\n    assert len(dp_finish) == len(points)\n    return [x + 2 * round_cost for x in dp_finish]\n\ndef calculate_reach_cost(dp_finish, from_points, to_points):\n    \"\"\"calculate from dp_finish of current level to the dp_reach of the next level.\"\"\"\n    assert len(dp_finish) == len(from_points)\n    from_k = [y/max(x, 0.5) for x, y in from_points]\n    to_k = [y/max(x, 0.5) for x, y in to_points]\n    dp_reach = []\n    from_index = 0\n    for i in range(len(to_points)):\n        while from_index + 1 < len(from_points) and from_k[from_index + 1] > to_k[i]:\n            from_index += 1\n        dp = dp_finish[from_index] + get_dist(from_points[from_index], to_points[i])\n        if from_index + 1 < len(from_points):\n            dp = min(dp, dp_finish[from_index + 1] + get_dist(from_points[from_index + 1], to_points[i]))\n        dp_reach.append(dp)\n    assert len(dp_reach) == len(to_points)\n    return dp_reach\n\n\ndef get_min_dist(points):\n    # 1. split points into levels, sort points in each level in x increase, y decrease order.\n    level_dict = {}\n    for point in points:\n        level = max(point[0], point[1])\n        if level in level_dict:\n            level_dict[level].append(point)\n        else:\n            level_dict[level] = [point]\n    level_points = []\n    for level in sorted(level_dict.keys()):\n        p = level_dict[level]\n        level_points.append(sorted(p, key=lambda x: x[0] - x[1]))\n\n    # 2. calculate the min cost to reach a level at a point.\n    #    calculate the min cost to finish a level at a point.\n    dp_reach = []\n    for p in level_points[0]:\n        dp_reach.append(p[0] + p[1])\n    dp_finish = calculate_finish_cost(dp_reach, level_points[0])\n    for i in range(len(level_points) - 1):\n        from_points = level_points[i]\n        to_points = level_points[i + 1]\n        dp_reach = calculate_reach_cost(dp_finish, from_points, to_points)\n        dp_finish = calculate_finish_cost(dp_reach, to_points)\n\n    # 3. the result is to finish at any points at the last level.\n    return min(dp_finish)\n\ndef main():\n    input = Input()\n    while True:\n        try:\n            nums = input.next_line_ints()\n            if not nums:\n                break\n            n = nums[0]\n            points = []\n            for _ in range(n):\n                x, y = input.next_line_ints()\n                points.append((x, y))\n        except:\n            print('read input failed')\n        try:\n            min_dist = get_min_dist(points)\n        except:\n            traceback.print_exc(file=sys.stdout)\n            print('get_min_dist failed')\n        print(\"{}\".format(min_dist))\n\nmain()", "passed": true, "time": 0.14, "memory": 14308.0, "status": "done"}, {"code": "from collections import defaultdict\nn = int(input())\npoints = defaultdict(list)\npoints[0].append((0,0))\nfor i in range(n):\n\tx,y = list(map(int,input().split()))\n\tpoints[max(x,y)].append((x,y))\nfor level in points:\n\tpoints[level].sort(key=lambda x:(x[0],-x[1]))\nlevels = sorted(points.keys())\ndp = [[0,0] for i in levels]\ndist = lambda a,b:abs(a[0]-b[0])+abs(a[1]-b[1])\nfor i in range(1,len(levels)):\n\tstart = points[levels[i]][0]\n\tend = points[levels[i]][-1]\n\tprevstart = points[levels[i-1]][0]\n\tprevend = points[levels[i-1]][-1]\n\tdp[i][0] = min(dp[i-1][0]+dist(prevstart,end), dp[i-1][1]+dist(prevend,end)) + dist(start,end)\n\tdp[i][1] = min(dp[i-1][0]+dist(prevstart,start), dp[i-1][1]+dist(prevend,start)) + dist(start,end)\n# print(points)\nprint(min(dp[-1]))\n", "passed": true, "time": 0.23, "memory": 14224.0, "status": "done"}, {"code": "def dista(a, b):\n\treturn abs(lista[a][0]-lista[b][0]) + abs(lista[a][1]-lista[b][1])\n\n\nlista = []\nne = 0\nn = int(input())\ndist = [0] * (n+1)\nlista.append((0, 0))\nfor _ in range(n):\n\tx, y = list(map(int, input().split()))\n\tlista.append((x, y))\nlista = sorted(lista, key= lambda x: min(x))\nlista = sorted(lista, key= lambda x: max(x))\nn += 1\nini = 0\nne = 1\noy = 0\nox = 0\nwhile ne < n:\n\tini = ne\n\tmaxi = max(lista[ne])\n\twhile ne < n and max(lista[ne]) == maxi:\n\t\tne += 1\n\tminx = ini\n\tminy = ini\n\tfor i in range(ini, ne):\n\t\tif lista[i][0] < lista[minx][0]:\n\t\t\tminx = i\n\t\telif lista[i][0] == lista[minx][0] and lista[i][1] > lista[minx][1]:\n\t\t\tminx = i\n\t\tif lista[i][1] < lista[miny][1]:\n\t\t\tminy = i\n\t\telif lista[i][1] == lista[miny][1] and lista[i][0] > lista[miny][0]:\n\t\t\tminy = i\n\n\tmxy = dista(minx, miny)\n\tif dista(miny, ox) + dist[ox] < dist[oy] + dista(miny, oy):\n\t\tdist[minx] = dista(ox, miny) + dist[ox] + mxy\n\telse:\n\t\tdist[minx] = dista(oy, miny) + dist[oy] + mxy\n\n\tif dista(ox, minx) + dist[ox] < dist[oy] + dista(oy, minx):\n\t\tdist[miny] = dista(ox, minx) + dist[ox] + mxy\n\telse:\n\t\tdist[miny] = dista(oy, minx) + dist[oy] + mxy\n\tox = minx\n\toy = miny\nprint(min(dist[miny], dist[minx]))\n", "passed": true, "time": 0.14, "memory": 14396.0, "status": "done"}, {"code": "import itertools as it\n\ndef dist(a, b):\n    return abs(a[0] - b[0]) + abs(a[1] - b[1])\n\ndef spir_dist(x):\n    a, b = x\n    if a >= b:\n        return b\n    else:\n        return 2 * b - a\n\nn = int(input())\n\nA = [[0, 0]]\n\nfor _ in range(n):\n    x, y = list(map(int, input().split()))\n    A += [[x, y]]\n\nA_s = sorted(A, key=max)\n\nA_g = it.groupby(A_s, key=max)\n\nA_t = [p + p if len(p) == 1 else [p[0], p[-1]]\n       for p in [sorted(list(q[1]), key=spir_dist) for q in A_g]]\n\nB = [[0,0]]\n\nfor i in range(1, len(A_t)):\n    pa, pb = A_t[i]\n    d = dist(pa, pb)\n    y = min([B[i - 1][k] + dist(A_t[i - 1][k], pa) for k in [0, 1]]) + d\n    x = min([B[i - 1][k] + dist(A_t[i - 1][k], pb) for k in [0, 1]]) + d\n    B += [[x, y]]\n\nprint(min(B[len(A_t) - 1]))\n", "passed": true, "time": 0.14, "memory": 14276.0, "status": "done"}, {"code": "import itertools as it\n\ndef dist(a, b):\n    return abs(a[0] - b[0]) + abs(a[1] - b[1])\n\ndef spir_dist(x):\n    a, b = x\n    if a >= b:\n        return b\n    else:\n        return 2 * b - a\n\nn = int(input())\n\nA = [[0, 0]]\n\nfor _ in range(n):\n    x, y = list(map(int, input().split()))\n    A += [[x, y]]\n\nA_s = sorted(A, key=max)\n\nA_g = it.groupby(A_s, key=max)\n\nA_t = [p + p if len(p) == 1 else [p[0], p[-1]]\n       for p in [sorted(list(q[1]), key=spir_dist) for q in A_g]]\n\nB = [[0,0]]\n\nfor i in range(1, len(A_t)):\n    pa, pb = A_t[i]\n    d = dist(pa, pb)\n    y = min([B[i - 1][k] + dist(A_t[i - 1][k], pa) for k in [0, 1]]) + d\n    x = min([B[i - 1][k] + dist(A_t[i - 1][k], pb) for k in [0, 1]]) + d\n    B += [[x, y]]\n\nprint(min(B[len(A_t) - 1]))\n", "passed": true, "time": 0.14, "memory": 14376.0, "status": "done"}, {"code": "import sys\n\ndef cal(a,b):\n    return abs(a[0]-b[0])+abs(a[1]-b[1])\n\ndef cmp(a,b):\n    if a[0]!=b[0]:return a[0]<b[0]\n    return a[1]>b[1]\n\nrd=sys.stdin.readlines()\nn=int(rd[0])\ndata={}\nfor _ in range(0,n):\n    x,y=map(int,rd[_+1].split())\n    if max(x,y) not in data:\n        data[max(x,y)]=[]\n    data[max(x,y)].append((x,y))\ndp1,dp2=0,0\npre1,pre2=(0,0),(0,0)\nfor i in sorted(list(data.keys())):\n    now1,now2=data[i][0],data[i][0]\n    for x in data[i]:\n        if cmp(now1,x):now1=x\n        if cmp(x,now2):now2=x\n    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))\n    pre1,pre2=now1,now2\nprint(min(dp1,dp2))", "passed": true, "time": 0.2, "memory": 14348.0, "status": "done"}, {"code": "import sys\n \ndef minp():\n\treturn sys.stdin.readline().strip()\n \ndef dist(a,b):\n\treturn abs(a[1]-b[1])+abs(a[2]-b[2])\n \nn = int(minp())\na = [None]*n\nfor i in range(n):\n\tx,y = list(map(int,minp().split()))\n\ta[i] = (max(x,y),x,-y)\na.sort()\n#print(a)\nd0 = 0\nd1 = 0\np0 = (0,0,0)\np1 = (0,0,0)\ni = 0\nk = 1\nwhile i < n:\n\tx = a[i]\n\txx = x[0]\n\tj = i + 1\n\twhile j < n and a[j][0] == xx:\n\t\tj += 1\n\ty = a[j-1]\n\tdd = dist(x,y)\n\td2 = dist(p0,x)\n\td3 = dist(p1,x)\n\tD0 = min(d0+d2,d1+d3)+dd\n\tP0 = y\n\td2 = dist(p0,y)\n\td3 = dist(p1,y)\n\tD1 = min(d0+d2,d1+d3)+dd\n\tP1 = x\n\tp0 = P0\n\tp1 = P1\n\td0 = D0\n\td1 = D1\n\tk += 1\n\ti = j\nprint(min(d0,d1))\n\t\n", "passed": true, "time": 0.14, "memory": 14312.0, "status": "done"}, {"code": "import itertools as it\n     \ndef dist(a, b):\n    return abs(a[0] - b[0]) + abs(a[1] - b[1])\n     \ndef spir_dist(x):\n    a, b = x\n    if a >= b:\n        return b\n    else:\n        return 2 * b - a\n     \nn = int(input())\n     \nA = [[0, 0]]\n     \nfor _ in range(n):\n    x, y = list(map(int, input().split()))\n    A += [[x, y]]\n     \nA_s = sorted(A, key=max)\n     \nA_g = it.groupby(A_s, key=max)\n     \nA_t = [p + p if len(p) == 1 else [p[0], p[-1]]\n           for p in [sorted(list(q[1]), key=spir_dist) for q in A_g]]\n     \nB = [[0,0]]\n     \nfor i in range(1, len(A_t)):\n    pa, pb = A_t[i]\n    d = dist(pa, pb)\n    y = min([B[i - 1][k] + dist(A_t[i - 1][k], pa) for k in [0, 1]]) + d\n    x = min([B[i - 1][k] + dist(A_t[i - 1][k], pb) for k in [0, 1]]) + d\n    B += [[x, y]]\n     \nprint(min(B[len(A_t) - 1]))\n#JSR\n", "passed": true, "time": 0.14, "memory": 14460.0, "status": "done"}, {"code": "\nimport itertools as it\n     \ndef dist(a, b):\n    return abs(a[0] - b[0]) + abs(a[1] - b[1])\n     \ndef spir_dist(x):\n    a, b = x\n    if a >= b:\n        return b\n    else:\n        return 2 * b - a\n     \nn = int(input())\n     \nA = [[0, 0]]\n     \nfor _ in range(n):\n    x, y = list(map(int, input().split()))\n    A += [[x, y]]\n     \nA_s = sorted(A, key=max)\n     \nA_g = it.groupby(A_s, key=max)\n     \nA_t = [p + p if len(p) == 1 else [p[0], p[-1]]\n           for p in [sorted(list(q[1]), key=spir_dist) for q in A_g]]\n     \nB = [[0,0]]\n     \nfor i in range(1, len(A_t)):\n    pa, pb = A_t[i]\n    d = dist(pa, pb)\n    y = min([B[i - 1][k] + dist(A_t[i - 1][k], pa) for k in [0, 1]]) + d\n    x = min([B[i - 1][k] + dist(A_t[i - 1][k], pb) for k in [0, 1]]) + d\n    B += [[x, y]]\n     \nprint(min(B[len(A_t) - 1]))\n", "passed": true, "time": 0.14, "memory": 14360.0, "status": "done"}]