Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import defaultdict
 
n, k = map(int, input().split())
hhh = list(map(int, input().split()))
INF = 10 ** 18
dp = defaultdict(lambda: INF)
dp[0, 0] = 0
for h in hhh:
    ndp = defaultdict(lambda: INF)
    for (changed, prev_h), operate in dp.items():
        if h == prev_h:
            ndp[changed, h] = min(ndp[changed, h], operate)
        elif h > prev_h:
            ndp[changed, h] = min(ndp[changed, h], operate + h - prev_h)
            if changed < k:
                ndp[changed + 1, prev_h] = min(ndp[changed + 1, prev_h], operate)
        else:
            ndp[changed, h] = min(ndp[changed, h], operate)
            if changed < k:
                ndp[changed + 1, prev_h] = min(ndp[changed + 1, prev_h], operate)
    dp = ndp
print(min(dp.values()))

### FIXED CODE ###

from collections import defaultdict

n, k = map(int, input().split())
hhh = list(map(int, input().split()))
INF = 10 ** 18
dp = defaultdict(lambda: INF)
dp[0] = 0
mask1 = (1 << 10) - 1
mask2 = ((1 << 63) - 1) ^ mask1

for h in hhh:
    ndp = defaultdict(lambda: INF)
    h_key = h << 10
    for changed_prev_h, operate in dp.items():
        changed = changed_prev_h & mask1
        prev_h = changed_prev_h >> 10
        if h == prev_h:
            key = h_key + changed
            ndp[key] = min(ndp[key], operate)
        elif h > prev_h:
            key = h_key + changed
            ndp[key] = min(ndp[key], operate + h - prev_h)
            if changed < k:
                key = changed_prev_h + 1
                ndp[key] = min(ndp[key], operate)
        else:
            key = h_key + changed
            ndp[key] = min(ndp[key], operate)
            if changed < k:
                key = changed_prev_h + 1
                ndp[key] = min(ndp[key], operate)
    # print(h)
    # print(dict(dp))
    # print(dict(ndp))
    dp = ndp
print(min(dp.values()))
### BUGGY CODE ###

A, B, K = list(map(int, input().split()))
x = [i for i in range(A, B+1)]
for i in x:
    if (i < A+K) or (i>B-K):
        print(i)

### FIXED CODE ###

A, B, K = list(map(int, input().split()))

if abs(A-B)<K:
    for i in range(A, B+1):
        print(i)
else:
    x = {i for i in range(A, A+K)}
    y = {j for j in range(B-K+1, B+1)}
    z = x | y
    z = sorted(list(z))
    for a in z:
        print(a)
### BUGGY CODE ###

from fractions import gcd
mod = 10**9+7
def lcm(x, y):
  return x//gcd(x, y)*y
n = int(input())
A = list(map(int, input().split()))
cnt = 0
m = 1
for i in A:
  m = lcm(m, i)
ans = 0
for i in A:
  ans += m//i
  ans %= mod
print(ans)

### FIXED CODE ###

from fractions import gcd
mod = pow(10, 9)+7
n = int(input())
A = list(map(int, input().split()))
m = A[0]
for i in range(1, n):
  m = m // gcd(m, A[i]) * A[i]
ans = 0
for i in A:
  ans += m//i
print(ans%mod)
### BUGGY CODE ###

n = int(input())
a = input().split()
b = []

if n % 2 == 0:
  for x in range(n):
    if x % 2 == 0:
      b.append(a[x])
    else:
      b.insert(0, a[x])
else:
  for y in range(n):
    if y % 2 == 1:
      b.append(a[y])
    else:
      b.insert(0, a[y])

print(" ".join(b))

### FIXED CODE ###

from collections import deque
N = int(input())
A = [int(x) for x in input().split()]
if N%2==0:
    queue = deque()
    for i in range(0, N, 2):
        queue.append(A[i])
        queue.appendleft(A[i+1])
else:
    queue = deque([A[0]])
    for i in range(1, N, 2):
        queue.append(A[i])
        queue.appendleft(A[i+1])
 
print(*queue)
### BUGGY CODE ###

a, b, n = map(int, input().split())
m = max(1, n - b)
c = 0
for i in range(n, m, - 1):
    d = (a * i) // b - a * (i // b)
    if d >= c:
        c = d
print(c)

### FIXED CODE ###

a, b, n = map(int, input().split())
if n <= b - 1:
    print((a * n) // b - a * (n // b))
else:
    print((a * (b - 1)) // b - a * ((b - 1) // b))
### BUGGY CODE ###

count=0
def merge(A, left, mid, right):
    global count
    n1=mid - left
    n2=right - mid
    L=[i for i in range(n1)]
    R=[i for i in range(n2)]
    for i in range(n1):
        L[i] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    L.append(100000000001)
    R.append(100000000001)
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
        count+=1
def merge_sort(A, left, right):
    if left+1 < right:
        mid=(left+right)//2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right) 

if __name__ == "__main__":
    n=int(input())
    A=list(map(int,input().split()))
    merge_sort(A,0,n)
    print(*A)
    print(count)


### FIXED CODE ###

count=0
def merge(A, left, mid, right):
    global count
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        count+=1
def merge_sort(A, left, right):
    if left+1 < right:
        mid=(left+right)//2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right) 

if __name__ == "__main__":
    n=int(input())
    A=list(map(int,input().split()))
    merge_sort(A,0,n)
    print(*A)
    print(count)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(S: str, T: str):
    lenS, lenT = len(S), len(T)
    DP = [[""]*(lenT+1) for _ in range(lenS+1)]
    for i in range(lenS):
        for j in range(lenT):
            if S[i] == T[j]:
                if len(DP[i+1][j+1]) < len(DP[i][j])+1:
                    DP[i+1][j+1] = DP[i][j]+S[i]
            if len(DP[i+1][j+1]) < len(DP[i+1][j]):
                DP[i+1][j+1] = DP[i+1][j]
            if len(DP[i+1][j+1]) < len(DP[i][j+1]):
                DP[i+1][j+1] = DP[i][j+1]
    print(DP[-1][-1])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(S: str, T: str):
    lenS, lenT = len(S), len(T)
    DP = [[0]*(lenT+1) for _ in range(lenS+1)]
    for i in range(lenS):
        for j in range(lenT):
            if S[i] == T[j]:
                DP[i+1][j+1] = max(DP[i][j]+1, DP[i+1][j+1])
            DP[i+1][j+1] = max(DP[i+1][j], DP[i][j+1], DP[i+1][j+1])

    ans = ""
    i, j = lenS, lenT
    while i > 0 and j > 0:
        if DP[i][j] == DP[i-1][j]:
            i -= 1
        elif DP[i][j] == DP[i][j-1]:
            j -= 1
        else:
            ans = S[i-1] + ans
            i -= 1
            j -= 1
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
K = K-1
ans = -10**9-1
i = 0
for h in range(N):
   i += 1
   start = i
   circle = [c[i-1]]
   i = p[i-1]
   while i != start:
      l = len(circle)
      score = circle[l-1] + c[i-1]
      circle.append(score)
      i = p[i-1]
   l=len(circle)
   for j in range(min(l, K+1)):
      if circle[l-1] > 0:
         score = circle[j] + ((K - j)//l)*circle[l-1]
      else:
         score = circle[j]
      ans = max(score, ans)      
print(ans)

### FIXED CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
K = K-1
ans = -10**9-1
for h in range(N):
   i = h+1
   start = i
   circle = [c[i-1]]
   i = p[i-1]
   while i != start:
      score = circle[-1] + c[i-1]
      circle.append(score)
      i = p[i-1]
   l=len(circle)
   for j in range(min(l, K+1)):
      if circle[l-1] > 0:
         score = circle[j] + ((K - j)//l)*circle[l-1]
      else:
         score = circle[j]
      ans = max(score, ans)      
print(ans)
### BUGGY CODE ###

n = int(input())
print(sum(range(n)))

### FIXED CODE ###

n = int(input())
d,m = divmod(n,2)
if m != 0:
    print(n*d)

else:
    print(n*(d - 1) + d)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort(reverse=True)
#s = input()
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      #print(i,j,k)
      if l[i] < l[j] + l[k]:
        ans += 1
      else:
        break

print(ans)

### FIXED CODE ###

import bisect as bi
n = int(input())
l = list(map(int,input().split()))
l.sort()
#print(l)
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    ans += (bi.bisect_left(l,l[i]+l[j]))-j-1
    #print(i,j,bi.bisect_right(l,l[i]+l[j])-j-1)
    #print(ans)
print(ans)
### BUGGY CODE ###

# https://atcoder.jp/contests/agc009/tasks/agc009_a

n = int(input())

A = []
B = []
for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

ans = 0
for i in range(n)[::-1]:
    a = A[i]
    b = B[i]
    if a % b != 0:
        multi = a // b + 1
        t = b * multi - a
        ans += t
        for j in range(i + 1):
            A[j] += t
print(ans)

### FIXED CODE ###

# https://atcoder.jp/contests/agc009/tasks/agc009_a

n = int(input())

A = []
B = []
for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

ans = 0
plus = 0
for i in range(n)[::-1]:
    a = A[i] + plus
    b = B[i]
    if a % b != 0:
        multi = a // b + 1
        t = b * multi - a
        ans += t
        plus += t
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

rr = [0]*N
gr = [0]*N
br = [0]*N

r = 0
g = 0
b = 0
for i in range(N-1, -1, -1):
    if S[i] == "R":
        r += 1
    if S[i] == "G":
        g += 1
    if S[i] == "B":
        b += 1
    rr[i] = r
    gr[i] = g
    br[i] = b

wa = {"R":rr, "G":gr, "B":br}

res = 0

for i in range(N):
    c1 = S[i]
    for j in range(i+1, N):
        c2 = S[j]
        if c1 == c2:
            continue
        c = (c1, c2)
        if "R" not in c:
            c3 = "R"
        elif "G" not in c:
            c3 = "G"
        else:
            c3 = "B"

        for k in range(j+1, N):
            if wa[c3][k] == 0:
                break
            if S[k] == c3:
                res += wa[c3][k]
                x = i+(j-i)*2
                if x < N:
                    if S[x] == c3:
                        res -= 1
                        pass
                break

print(res)

### FIXED CODE ###

N = int(input())
S = input()

rr = [0]*N
gr = [0]*N
br = [0]*N

r = 0
g = 0
b = 0
for i in range(N-1, -1, -1):
    if S[i] == "R":
        r += 1
    if S[i] == "G":
        g += 1
    if S[i] == "B":
        b += 1
    rr[i] = r
    gr[i] = g
    br[i] = b

wa = {"R":rr, "G":gr, "B":br}

res = 0

for i in range(N):
    c1 = S[i]
    for j in range(i+1, N):
        c2 = S[j]
        if c1 == c2:
            continue
        c = (c1, c2)
        if "R" not in c:
            c3 = "R"
        elif "G" not in c:
            c3 = "G"
        else:
            c3 = "B"

        if wa[c3][j] == 0:
            break

        res += wa[c3][j]
        x = i+(j-i)*2
        if x < N:
            if S[x] == c3:
                res -= 1
                pass

print(res)
### BUGGY CODE ###

k, s = map(int, input().split())
cnt = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                cnt += 1
print(cnt)


### FIXED CODE ###

k, s = map(int, input().split())
cnt = 0
for x in range(k+1):
    for y in range(k+1):
        if (0 <= s-x-y) and (s-x-y <= k):
            cnt += 1
print(cnt)
### BUGGY CODE ###

n= int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())
b = a
max1 = max(a)

for i in range(n):
    if a[i] == max1:
        a[i] = 0
        max2 = max(a)
        print(max2)
        a[i] = max1
        
    else:
        print(max1)

### FIXED CODE ###

import numpy as np
n= int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())
    
b = np.array(a)
b = np.sort(b)[::-1]

ans = [0]*n

for i in range(n):
    if a[i] == b[0]:
        ans[i] = b[1]
    else:
        ans[i] = b[0]
        
for i in range(n):
  print(ans[i])
### BUGGY CODE ###

def bellman_ford(s, n, G, st):
    d = [float('inf')]*n
    d[s] = 0
    for i in range(n):
        update = False
        for x, y, z in G:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                if y in st:
                    update = True
        if not update:
            break
        if i == n - 1:
            return None
    return d

def main():
    n, m, p = map(int, input().split())
    G = []
    U = [[] for _ in range(n)]
    dic = {}
    for _ in range(m):
        a, b, c = map(int, input().split())
        if (a-1, b-1) in dic:
            if dic[(a-1, b-1)] > -c+p:
                dic[(a-1, b-1)] = -c+p
        else:
            dic[(a-1, b-1)] = -c+p
    for v in dic.keys():
        G.append([v[0], v[1], dic[v]])
        U[v[1]].append(v[0])
    st = set()
    st.add(n-1)
    q = [n-1]
    while len(q) > 0:
        t = q.pop(-1)
        for v in U[t]:
            if not v in st:
                q.append(v)
                st.add(v)
    ans = bellman_ford(0, n, G, st)
    if ans is None:
        print(-1)
    else:
        print(max(0, -ans[n-1]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def bellman_ford(s, n, G):
    d = [float('inf')]*n
    d[s] = 0
    for i in range(n):
        update = False
        for x, y, z in G:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        if i == n - 1:
            return None
    return d

def main():
    n, m, p = map(int, input().split())
    G = []
    U = [[] for _ in range(n)]
    V = [[] for _ in range(n)]
    dic = {}
    for _ in range(m):
        a, b, c = map(int, input().split())
        if (a-1, b-1) in dic:
            if dic[(a-1, b-1)] > -c+p:
                dic[(a-1, b-1)] = -c+p
        else:
            dic[(a-1, b-1)] = -c+p
    for v in dic.keys():
        G.append([v[0], v[1], dic[v]])
        U[v[1]].append(v[0])
        V[v[0]].append(v[1])
    st1 = set()
    st1.add(n-1)
    q = [n-1]
    while len(q) > 0:
        t = q.pop(-1)
        for v in U[t]:
            if not v in st1:
                q.append(v)
                st1.add(v)
    st2 = set()
    st2.add(0)
    q = [0]
    while len(q) > 0:
        t = q.pop(-1)
        for v in V[t]:
            if not v in st2:
                q.append(v)
                st2.add(v)
    st = st1 & st2
    eg = []
    for v in G:
        if v[0] in st and v[1] in st:
            eg.append(v)
    ans = bellman_ford(0, n, eg)
    if ans is None:
        print(-1)
    else:
        print(max(0, -ans[n-1]))

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import math
sum = 0
K = int(input())
for k in range(K):
  for j in range(K):
    for i in range(K):
      sum = sum + math.gcd(math.gcd(k+1,j+1),i+1)
print(sum)

### FIXED CODE ###

from math import gcd
sum = 0
K = int(input())
for k in range(1,K+1):
  for j in range(1,K+1):
    t = gcd(k,j)
    for i in range(1,K+1):
      sum += gcd(t,i)
print(sum)
### BUGGY CODE ###

x,k,d = list(map(int,input().split()))
#偶数回前後に移動したら0
#偶数回一方向に移動したら2D

for i in range(k):
  x = abs(x) - d

  if x < 0:
    break



if (k-i+1) % 2 == 0:
  #そのまま
  ans = abs(x)
else:
  ans = min(abs(x-d),abs(x+d))

print(ans)

### FIXED CODE ###


x,k,d = list(map(int,input().split()))
#偶数回前後に移動したら0
#偶数回一方向に移動したら2D

if x >= 0:
  capa_iter = x // d
  if capa_iter < k:
    if (k - capa_iter) % 2 == 0:
      print(x - capa_iter*d)
    else:
      print(min([abs(x - capa_iter*d-d),x - capa_iter*d+d]))
    exit()

  ans =x-d*k
  print(ans)

if x < 0:
  capa_iter = abs(-x // d)
  if capa_iter < k:
    if (k - capa_iter) % 2 == 0:
      print(abs(x + capa_iter*d))
    else:
      print(min([abs(x + capa_iter*d+d),abs(x + capa_iter*d -  d)]))
    exit()

  ans =abs(x+d*k)
  print(ans)
### BUGGY CODE ###

from itertools import product
s = input()

mx = 0
mxstr = ""
index = []
for i in range(len(s)):
    if s[i] == "?":
        index.append(i)

for i in product(range(2), repeat=s.count("?")):
    tmp = s
    for indx, zerone in zip(index, i):
        if zerone:
            tmp = tmp[:indx] + "P" + tmp[indx+1:]
        else:
            tmp = tmp[:indx] + "D" + tmp[indx+1:]
    sm = tmp.count("D") + tmp.count("PD")
    if sm > mx:
        mx = sm
        mxstr = tmp
print(mxstr)


### FIXED CODE ###

s = input()
s = s.replace("?", "D")
print(s)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N, M = map(int, input().split())

# A[i], B[i] はまとめてしまう
stores = [list(map(int, input().split())) for n in range(N)]

# 最も安い店を探す
def getCheapest():
  cheapest = 0
  for i in range(1, N):
    if (stores[i][0] < stores[cheapest][0] and stores[i][1] > 0):
      cheapest = i
  return cheapest

bought = 0
money = 0
cheapest = getCheapest()

# M本買うまで繰り返す
while(bought < M):
  if (stores[cheapest][1] == 0):
    cheapest = getCheapest()
  money += stores[cheapest][0]
  stores[cheapest][1] -= 1
  bought += 1

# 最後にかかった金額を出力
print(money)

### FIXED CODE ###

# -*- coding: utf-8 -*-

N, M = map(int, input().split())

# A[i], B[i] はまとめてしまう
stores = [list(map(int, input().split())) for n in range(N)]

# 安さ順にソート
stores.sort(key = lambda s: s[0])

remaining = M
cost = 0

while True:
  store = stores[0]
  if store[1] >= remaining: # もしこの店で買いきれるなら
    cost += store[0] * remaining
    break
  else: #買い切れないなら
    cost += store[0] * store[1]
    remaining -= store[1]
    stores.pop(0)

print(cost)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline

N, K = map(int, input().split())

es = [[] for _ in range(N)]
g = [0] * N
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    g[a] += 1
    es[b].append(a)
    g[b] += 1

gs = [0] * (N + 1)
gs[0] = -1
gs[N] = -1
visited = [False] * N
ans = 1


def rec(v, bf):
    global ans
    visited[v] = True
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if not visited[nv]:
            rec(nv, v)
    return


rec(0, N)
print(ans)
# print(gs)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline


def rec(v, bf):
    global ans
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if nv == bf: continue
        rec(nv, v)
    return


N, K = map(int, input().split())

es = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    es[b].append(a)

gs = [0] * (N + 1)
gs[0] = -1
gs[N] = -1

ans = 1

rec(0, N)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC141 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def lcs_length(a, b):
    table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i, ca in enumerate(a, 1):
        for j, cb in enumerate(b, 1):
            table[i][j] = (
                table[i - 1][j - 1] + 1 if ca == cb else
                max(table[i][j - 1], table[i - 1][j]))
    return table[-1][-1]
n = I()
S = list(input())
ans = 0
for k in range(1,n):
    if k <= ans or n - k <= ans:
        continue
    s = S[:k]
    t = S[k:]
    ans = max(ans,lcs_length(s,t))
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
#ABC141 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = input()
dp = [[0]*(n+1) for _ in range(n+1)]
dp[-1][-1] = 1
for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
ans = 0
for i in range(n):
    for j in range(n):
        ans = max(ans,min(i-j,dp[i][j]))
print(ans)
### BUGGY CODE ###

from heapq import heappop,heappush

def prim():
    used = [True]*n
    edgelist = []
    for e in edge[0]:
        heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        short_edge = heappop(edgelist)
        if not used[short_edge[1]]:
            continue
        v = short_edge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heappush(edgelist,e)
        res += short_edge[0]
    return res

n = int(input())
A = [list(map(int,input().split()))+[i] for i in range(n)]
A.append([-10**12,-10**12,-1])
A.append([10**12,10**12,-1])
X = sorted(A)
Y = sorted(A,key = lambda x:x[1])
d = []
for i in range(1,n+1):
    sx = X[i-1][0]
    sy = Y[i-1][1]
    mx = X[i][0]
    my = Y[i][1]
    lx = X[i+1][0]
    ly = Y[i+1][1]
    nsx = X[i-1][2]
    nsy = Y[i-1][2]
    nmx = X[i][2]
    nmy = Y[i][2]
    nlx = X[i+1][2]
    nly = Y[i+1][2]
    i -= 1
    d.append((nsx,nmx,mx-sx))
    d.append((nmx,nlx,lx-mx))
    d.append((nsy,nmy,my-sy))
    d.append((nmy,nly,ly-my))

edge = [[] for i in range(n)]
for x,y,z in d:
    if x==-1 or y==-1:
        continue
    edge[x].append([z,y])
    edge[y].append([z,x])

print(prim())

### FIXED CODE ###

def main():
    import sys 
    input = sys.stdin.readline
    from heapq import heappop,heappush
    from operator import itemgetter
    
    def prim():
        used = [True]*n
        edgelist = []
        for e in edge[0]:
            heappush(edgelist,e)
        used[0] = False
        res = 0
        while len(edgelist) != 0:
            short_edge = heappop(edgelist)
            if not used[short_edge[1]]:
                continue
            v = short_edge[1]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heappush(edgelist,e)
            res += short_edge[0]
        return res

    n = int(input())
    A = [list(map(int,input().split()))+[i] for i in range(n)]
    A.append([-10**12,-10**12,-1])
    A.append([10**12,10**12,-1])
    X = sorted(A)
    Y = sorted(A,key = itemgetter(1))
    edge = [[] for i in range(n)]
    for i in range(1,n+1):
        sx = X[i-1][0]
        sy = Y[i-1][1]
        mx = X[i][0]
        my = Y[i][1]
        lx = X[i+1][0]
        ly = Y[i+1][1]
        nsx = X[i-1][2]
        nsy = Y[i-1][2]
        nmx = X[i][2]
        nmy = Y[i][2]
        nlx = X[i+1][2]
        nly = Y[i+1][2]
        edge[nsx].append((mx-sx,nmx))
        edge[nmx].append((mx-sx,nsx))
        edge[nlx].append((lx-mx,nmx))
        edge[nmx].append((lx-mx,nlx))
        edge[nsy].append((my-sy,nmy))
        edge[nmy].append((my-sy,nsy))
        edge[nly].append((ly-my,nmy))
        edge[nmy].append((ly-my,nly))

    print(prim()) 

if __name__ == '__main__':
    main()