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

import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
def main():
    S = input()
    l = len(S)
    dp = [[0]*(13) for _ in range(len(S)+5)]
    dp[0][0] = 1
    mul = 1  
    for i in range(l):
        x = S[-(i+1)]
        if x == "?":
            for k in range(10):
                for j in range(13):
                    dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                    dp[i + 1][(mul * k + j) % 13] %= MOD
        else:
            k = int(x) # これしか選ぶ余地なし
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
        mul *= 10 % 13
    print(dp[l][5]%MOD)


if __name__ == "__main__":
    main()


### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

def main():
#    N, X, T = map(int, input().split())
    N = input()
    heights = [int(s) for s in input().split()]

    sum = 0
    while True:
        max_value = max(heights)
        max_index = heights.index(max_value)

        for i in range(max_index,len(heights)):
            sum = sum + max_value - heights[i]

        if max_index == 0 :
            break

        heights = heights[0:max_index]
    print(sum)
main()


### FIXED CODE ###

def main():
#    N, X, T = map(int, input().split())
    N = input()
    heights = [int(s) for s in input().split()]

    sum = 0

    max_value = 0

    for i in range(0, len(heights)):
        if max_value < heights[i]:
            max_value = heights[i]
        else:
            sum = sum + max_value - heights[i]


    print(sum)
main()
### BUGGY CODE ###

import sys

H, W = map(int, sys.stdin.readline().split())
s = [list(sys.stdin.readline().rstrip()) for _ in range(H)]

ans = []


def dfs(x, y, tmp=0):
    if s[x][y] == "#":
        tmp = tmp + 1
    if x == H - 1 and y == W - 1:
        return ans.append(tmp)
    else:
        if x == H - 1:
            dfs(x, y + 1, tmp)
        elif y == W - 1:
            dfs(x + 1, y, tmp)
        else:
            dfs(x, y + 1, tmp)
            dfs(x + 1, y, tmp)


def main():
    dfs(0, 0)
    print(min(ans))


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys


def main():
    dp = [[0] * W for _ in range(H)]

    for y in range(H):
        for x in range(W):
            if x == 0 and y == 0:
                if s[0][0] == "#":
                    dp[0][0] = 1
            elif x == 0:
                if s[y][x] == "#" and s[y - 1][x] == ".":
                    dp[y][x] = dp[y - 1][x] + 1
                else:
                    dp[y][x] = dp[y - 1][x]
            elif y == 0:
                if s[y][x] == "#" and s[y][x - 1] == ".":
                    dp[y][x] = dp[y][x - 1] + 1
                else:
                    dp[y][x] = dp[y][x - 1]
            else:
                if s[y][x] == "#" and s[y][x - 1] == "." and s[y - 1][x] == ".":
                    dp[y][x] = min(dp[y][x - 1], dp[y - 1][x]) + 1
                elif s[y][x] == "#" and s[y][x - 1] == ".":
                    dp[y][x] = min(dp[y][x - 1] + 1, dp[y - 1][x])
                elif s[y][x] == "#" and s[y - 1][x] == ".":
                    dp[y][x] = min(dp[y][x - 1], dp[y - 1][x] + 1)
                else:
                    dp[y][x] = min(dp[y][x - 1], dp[y - 1][x])

    print(dp[-1][-1])


if __name__ == "__main__":
    H, W = map(int, sys.stdin.readline().split())
    s = [list(sys.stdin.readline().rstrip()) for _ in range(H)]
    main()
### BUGGY CODE ###

n, q = list(map(int, input().split(' ')))
splice = [[] for i in range(n)]

for i in range(q):
    op = list(map(int, input().split(' ')))
    if op[0] == 0:
        splice[op[1]].append(op[2])
    elif op[0] == 1:
        print(' '.join(list(map(str, splice[op[1]]))))
    elif op[0] == 2:
        splice[op[2]].extend(splice[op[1]])
        splice[op[1]] = []


### FIXED CODE ###

class Node:
    def __init__(self, val=None, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

class DoublyLinkedList():
    def __init__(self):
        self.start = Node(val='START', prev=None, next=None)
        self.end = Node(val='END', prev=self.start, next=None)
        self.start.next = self.end

    def insert(self, x):
        new_node = Node(val=x, prev=self.end.prev, next=self.end)
        self.end.prev.next = new_node
        self.end.prev = new_node

    def dump(self):
        node_list = []
        crnode = self.start.next
        while crnode != self.end:
            node_list.append(crnode.val)
            crnode = crnode.next
        print(' '.join(list(map(str, node_list))))

    def extend(self, dll):
        self.end.prev.next = dll.start.next
        dll.start.next.prev = self.end.prev
        self.end = dll.end

n, q = list(map(int, input().split(' ')))
splice = [DoublyLinkedList() for i in range(n)]

for i in range(q):
    op, *val = list(map(int, input().split(' ')))
    if op == 0:
        splice[val[0]].insert(val[1])
    elif op == 1:
        splice[val[0]].dump()
    else:
        splice[val[1]].extend(splice[val[0]])
        splice[val[0]] = DoublyLinkedList()
### BUGGY CODE ###

#import numpy as np
import sys
# import copy


def xnxn(n=0, flag="v"):
    """
    args:
        int n: a number of lows to read
    example:
        input   1
        retrun  1

        input   1 2 3
        return  [1,2,3]
        input   1 2 3
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        temp = list(map(int, input().split()))
        if len(temp) == 1:
            if flag == "l":
                return temp
            else:
                return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        temp = [list(map(int, input().split())) for _ in range(n)]
        return temp


n, k = xnxn()
a = xnxn(flag="l")
for _ in range(k):
    add = [0]*n
    for i in range(0, n):
        idx_min = max(0, i - a[i])
        idx_max = min(n-1, i + a[i])
        for t in range(idx_min, idx_max + 1):
            add[t] = add[t]+1
    a = add

for i in a:
    print(i, end=" ")


### FIXED CODE ###

# import numpy as np
import sys
# import copy


def xnxn(n=0, flag="v"):
    """
    args:
        int n: a number of lows to read
    example:
        input   1
        retrun  1

        input   1 2 3
        return  [1,2,3]
        input   1 2 3
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        temp = list(map(int, input().split()))
        if len(temp) == 1:
            if flag == "l":
                return temp
            else:
                return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        temp = [list(map(int, input().split())) for _ in range(n)]
        return temp


n, k = xnxn()
a = xnxn(flag="l")
for _ in range(k):
    tmp = [0]*(n+1)
    for i in range(0, n):
        l = max(0, i - a[i])
        r = min(n, i + a[i]+1)
        tmp[l] += 1
        tmp[r] -= 1
    for i in range(1, n):
        tmp[i] += tmp[i - 1]
    if a == tmp:
        break
    a = tmp

for i in a[:n]:
    print(i, end=" ")
### BUGGY CODE ###

D, G = [int(i) for i in input().split()]
pc = [list(map(lambda x: int(x), input().split())) for i in range(D)]
pc.insert(0,[])
ans = float('inf')

def f(score, i, kaitousu):
	global ans
	if i <= D:
		for j in range(pc[i][0] + 1):
			if j == pc[i][0]:
				newScore = score + 100 * i * j + pc[i][1]
			else:
				newScore = score + 100 * i * j
			newKaitousu = kaitousu + j
			if newScore >= G:
				if newKaitousu < ans:
					ans = newKaitousu
				break
			else:
				f(newScore, i + 1, newKaitousu)

f(0, 1, 0)
print(ans)

### FIXED CODE ###

D, G = map(int, input().split())
P = [0]
C = [0]
ans = 0
for _ in range(D):
    p, c = map(int, input().split())
    P.append(p)
    C.append(c)
    ans += p

for i in range(1<<D):
    point = 0
    count = 0
    for j in range(D, 0, -1):
        if i>>j-1&1:
            point += j * 100 * P[j] + C[j]
            count += P[j]
    for k in range(D, 0, -1):
        if not i>>k-1&1 and P[k] > 1:
            for _ in range(P[k]-1):
                if point < G:
                    point += k * 100
                    count += 1
                else:
                    break
            if point >= G:
                ans = min(ans, count)
            break
print(ans)
### BUGGY CODE ###

n = int(input())
dp = [0]*n
cnt = 0
L = []
flag = True
for i in range(n):
  T = []
  N = list(map(int,input().split()))
  for j in range(n-1):
    T.append([i+1,N[j]])
  L.append(T)
while dp != [n-1]*n:
  B = [0]*n
  act = 0
  for i in range(n):
    if B[i] != 0:
      None
    else:
      B[i] = 1
      if dp[i] == n-1:
        None
      else:
        miru = L[i][dp[i]][1]-1
        if dp[miru] == n-1:
          flag = False
          break
        else:
          if B[miru] != 1:
            sie = dp[miru]
            if L[miru][sie][1] == i+1:
              dp[i] += 1
              dp[miru] += 1
              B[miru] = 1
              act += 1
            else:
              None
          else:
              None
  if act == 0:
    dp = [n-1]*n
    flag = False
  cnt += 1
if flag == False:
  print(-1)
else:
  print(cnt)

### FIXED CODE ###

import time
start = time.time()
n = int(input())
dp = [0]*n
cnt = 0
L = []
flag = True
for i in range(n):
  T = []
  N = list(map(int,input().split()))
  for j in range(n-1):
    T.append((i+1,N[j]))
  L.append(T)
while dp != [n-1]*n:
  B = [0]*n
  act = 0
  for i in range(n):
    if B[i] == 0:
      B[i] = 1
      if dp[i] != n-1:
        miru = L[i][dp[i]][1]-1
        if dp[miru] == n-1:
          flag = False
          dp = [n-1]*n
        else:
          if B[miru] != 1:
            if L[miru][dp[miru]][1] == i+1:
              dp[i] += 1
              dp[miru] += 1
              B[miru] = 1
              if act == 0:
                act = 1
  if act == 0:
    dp = [n-1]*n
    flag = False
  cnt += 1
  ela = time.time()-start
  if ela > 1.7:
    dp = [n-1]*n
if flag == False:
  print(-1)
else:
  if ela < 1.7:
    print(cnt)
  else:
    print(n*(n-1)//2)
### BUGGY CODE ###

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

cities = {}
prefs = []

for i in range(1, M + 1):
  p, y = list(map(int, input().split()))
  
  pref = {"city": p, "year": y}
  prefs.append(pref)

  if p not in cities:
    cities[p] = [pref]
  else:
    city = cities[p]
    for idx_city, pref_in_city in enumerate(city):
      if y < pref_in_city['year']:
        city.insert(idx_city, pref)
        break
      elif idx_city == len(city) - 1:
        city.append(pref)
        break

[print("%s%s" % (
  str(int(pref['city'])).zfill(6), 
  str(cities[pref['city']].index(pref) + 1).zfill(6))) for pref in prefs]


### FIXED CODE ###

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

cities = {}
prefs = []

for i in range(1, M + 1):
  p, y = list(map(int, input().split()))
  
  pref = {"city": p, "year": y}
  prefs.append(pref)

  if p not in cities:
    cities[p] = [pref]
  else:
    cities[p].append(pref)

for city in cities.values():
  city.sort(key=lambda p: p['year'])
  for idx, pref in enumerate(city):
    pref['pref_id'] = str(idx + 1).zfill(6)

[print("%s%s" % (
  str(int(pref['city'])).zfill(6), 
  pref['pref_id'])) for pref in prefs]
### BUGGY CODE ###

A,B,C,K = map(int,input().split())
sum = 0
for i in range(K):
    if A > 0:
        sum += 1
        A -= 1
    elif B > 0:
        sum += 0
        B -= 1
    elif C > 0:
        sum -= 1
        C -= 1
        
print(sum)
    

### FIXED CODE ###

A,B,C,K = map(int,input().split())
if A >= K:
    print(1*K)

else:
    K -= A
    if B >= K:
        print(1*A)
    
    else:
        K -= B
        if K <= C:
            print(1*A + -1*K)
### BUGGY CODE ###

n = int(input())
 
ls = list(map(int, input().split()))

def find(list, n):
  for i in range(len(list)):
    if list[i] == n:
      return i+1
    
for i in range(n):
  a = find(ls, i+1) #f(ls,1) -> a = 3 
  print(a, end=" ")


### FIXED CODE ###

n = int(input())
 
ls = list(map(int, input().split()))
ans = []

for i in range(n):
  ans.append(0)
  
for i in range(n):
  ans[ls[i]-1] = i + 1
  
for i in range(n):
  print(ans[i], end = " ")
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
H,W = map(int,readline().split())
S = ''.join(read().decode().split())
 
INF = 10 ** 9
N = H*W
U = 250
dp = [[INF] * U for _ in range(N)]
# そのマスをいじる回数 → 総回数の最小値
dp[0] = list(range(U))
for n in range(H*W):
    for i in range(U-1,0,-1):
        if dp[n][i-1]> dp[n][i]:
            dp[n][i-1] = dp[n][i]
    for i in range(1,U):
        if dp[n][i-1] + 1 < dp[n][i]:
            dp[n][i] = dp[n][i-1] + 1
    s = S[n]
    if s == '#':
        for i in range(0,U,2):
            dp[n][i] = INF
    else:
        for i in range(1,U,2):
            dp[n][i] = INF
    x,y = divmod(n,W)
    to = []
    if y < W - 1:
        to.append(n+1)
    if x < H - 1:
        to.append(n+W)
    for m in to:
        for i in range(U):
            if dp[m][i] > dp[n][i]:
                dp[m][i] = dp[n][i]

print(min(dp[-1]))

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
H,W = map(int,readline().split())
S = ''.join(read().decode().split())
 
INF = 10 ** 9
N = H*W
U = 250
dp = [[INF] * U for _ in range(N)]
# そのマスをいじる回数 → 総回数の最小値
dp[0] = list(range(U))
for n in range(H*W):
    for i in range(U-1,0,-1):
        if dp[n][i-1]> dp[n][i]:
            dp[n][i-1] = dp[n][i]
    for i in range(1,U):
        if dp[n][i-1] + 1 < dp[n][i]:
            dp[n][i] = dp[n][i-1] + 1
    s = S[n]
    if s == '#':
        for i in range(0,U,2):
            dp[n][i] = INF
    else:
        for i in range(1,U,2):
            dp[n][i] = INF
    x,y = divmod(n,W)
    to = []
    if y < W - 1:
        to.append(n+1)
    if x < H - 1:
        to.append(n+W)
    for m in to:
        for i in range(U):
            if dp[m][i] > dp[n][i]:
                dp[m][i] = dp[n][i]
 
print(min(dp[-1]))
### BUGGY CODE ###

n,w = map(int,input().split())
wv_list = [map(int,input().split()) for _ in range(n)]
dp = [0]*(w+1)

for ww,vv in wv_list:
    for i in range(w, ww-1, -1):
        t = dp[i-ww] + vv
        dp[i] = max(dp[i], t)
print(max(dp))

### FIXED CODE ###

n,w = map(int,input().split())
wv_list = [map(int,input().split()) for _ in range(n)]
dp = [0]*(w+1)

for ww,vv in wv_list:
    for i in range(w, ww-1, -1):
        t = dp[i-ww] + vv
        if dp[i] < t:
            dp[i] = t
print(max(dp))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))

if n%2 == 0:
  for i in range(1,n//2+1):
    if a.count(i*2-1) != 2:
      print(0)
      exit()
  print(2**(n//2))
else:
  if a.count(0) != 1:
    print(0)
    exit()
  for i in range(1,n//2):
    if a.count(i*2) != 2:
      print(0)
      exit()
  print(2**(n//2))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
m = 10**9+7
if n%2 == 0:
  l = []
  for i in range(1,n//2+1):
    l.append(i*2-1)
    l.append(i*2-1)
  if a != l:
    print(0)
    exit()
  print(2**(n//2) %m)
else:
  l = [0]
  for i in range(1,n//2+1):
    l.append(i*2)
    l.append(i*2)
  if a != l:
    print(0)
    exit()
  print(2**(n//2) %m)
### BUGGY CODE ###


import math
import sys
sys.setrecursionlimit(2000000)
# import itertools
# import statistics
# import numpy as np
# x = int(input())
a, b, n = list(map(int, input().split()))
ans = a*n//b - a*(n//b)
count = 0
same = 0
# print(ans)
for i in range(n, int(pow(n, 0.75))-1, -1):
    if ans < a*i//b - a*(i//b):
        ans = a*i//b - a*(i//b)
        if count == 1:
            print(ans)
            exit()
    elif a*i//b - a*(i//b) == 0:
        count += 1
    elif a*i//b - a*(i//b) == ans:
        same += 1
    if same > b:
        print(ans)
        exit()

print(ans)


### FIXED CODE ###

a, b, n = list(map(int, input().split()))

x = min(b-1, n)
ans = a*x//b - a*(x//b)

print(ans)
### BUGGY CODE ###

N,W=map(int,input().split())
w=[]
v=[]
for i in range(N):
  w_,v_=map(int,input().split())
  w.append(w_)
  v.append(v_)
  
dp=[[0]*(W+1) for i in range(N+1)]
for i in range(N):
  for j in range(W+1):
    dp[i+1][j]=max(dp[i+1][j],dp[i][j])
    if j+w[i] <=W:
      dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i])

print(dp[N][W])
#print(dp)

### FIXED CODE ###

N,W=map(int,input().split())
w=[]
v=[]
for i in range(N):
  w_,v_=map(int,input().split())
  w.append(w_)
  v.append(v_)
  
dp=[[0]*(W+1) for i in range(N+1)]
for i in range(N):
  for j in range(W+1):
    dp[i+1][j]=max(dp[i+1][j],dp[i][j])
    if j+w[i] <=W:
      dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i])

print(dp[N][W])
#print(dp)
### BUGGY CODE ###

N,K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

for _ in range(K):
    new = [0]*N
    for i in range(N):
        m = max(0,i-A[i])
        new[m] += 1
        if i+A[i]+1 < N:
            new[i+A[i]+1] -= 1
    A[0] = new[0]
    for i in range(1,N):
        new[i] += new[i-1]
        A[i] = new[i]

A = [str(i) for i in A]
print(" ".join(A))

### FIXED CODE ###

N,K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

for _ in range(K):
    new = [0]*N
    for i in range(N):
        m = max(0,i-A[i])
        new[m] += 1
        if i+A[i]+1 < N:
            new[i+A[i]+1] -= 1
    A[0] = new[0]
    for i in range(1,N):
        new[i] += new[i-1]
        A[i] = new[i]
    for a in A:
        if a != N:
            break
    else:
        break

A = [str(i) for i in A]
print(" ".join(A))
### BUGGY CODE ###

from collections import Counter

N = int(input())
S = list(input() for i in range(N))

d = Counter(S)
max_k_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
ans = '\n'.join(sorted(max_k_list))
print(ans)

### FIXED CODE ###

from collections import Counter
 
N = int(input())
S = list(input() for i in range(N))
 
d = Counter(S)

num = max(d.values())
max_k_list = [i for i,j in d.items() if j == num]

ans = '\n'.join(sorted(max_k_list))
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, P: int, S: str):
    if 10%P == 0:
        sum = 0
        for i in range(1,N+1):
            if int(S[-i]) % P == 0:
                sum += (N-i)+1
        print(sum)
        return
    else:
        sArr = [0] * N
        C = 1
        counts = [0] * P
        for i in range(1,N+1):
            if i == 1:
                sArr[i - 1] = int(S[-1])%P
            else:
                sArr[i-1]  = (int(S[-i])*C + sArr[i-2])%P
            counts[sArr[i-1]]+=1
            C*=10
        sum = 0
        for c in counts:
            if c == 0:
                continue
            sum += int((c*(c-1)/2))
        sum += counts[0]
        print(sum)

    # sum = 0
    # for i in range(N):
    #     sDiv = 0
    #     coeff = 1
    #     for j in range(i,N):
    #         sDiv= (sDiv*coeff + arr[j])%P
    #         coeff*=10
    #         if sDiv == 0:
    #             sum+=1
    # print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, P, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import defaultdict

def solve(N: int, P: int, S: str):
    if 10%P == 0:
        sum = 0
        for i in range(1,N+1):
            if int(S[-i]) % P == 0:
                sum += (N-i)+1
        print(sum)
        return
    else:
        current = 0
        C = 1
        counts = defaultdict(int)
        for i in range(1,N+1):
            if i == 1:
                current = int(S[-1])%P
            else:
                current = (int(S[-i])*C + current)%P
            counts[current]+=1
            C=C*10%P
        sum = 0
        for k in counts:
            c = counts[k]
            sum += int((c*(c-1)/2))
        sum += counts[0]
        print(sum)

    # sum = 0
    # for i in range(N):
    #     sDiv = 0
    #     coeff = 1
    #     for j in range(i,N):
    #         sDiv= (sDiv*coeff + arr[j])%P
    #         coeff*=10
    #         if sDiv == 0:
    #             sum+=1
    # print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, P, S)

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

class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


N = int(input())
x, y = [], []
for i in range(N):
    a, b = map(int, input().split())
    x.append([a, i])
    y.append([b, i])
x.sort()
y.sort()

e = []
for i in range(N-1):
    e.append([abs(x[i][0]-x[i+1][0]), x[i][1], x[i+1][1]])
    e.append([abs(y[i][0]-y[i+1][0]), y[i][1], y[i+1][1]])

e.sort()
uft = UnionFindTree()
for i in range(N):
    uft.make(i)

ans = 0
for w, s, t in e:
    if not uft.same(s, t):
        uft.unite(s, t)
        ans += w

print(ans)


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


N = int(input())
x, y = [], []
for i in range(N):
    a, b = map(int, input().split())
    x.append([a, i])
    y.append([b, i])
x.sort()
y.sort()

e = []
for i in range(N-1):
    e.append([abs(x[i][0]-x[i+1][0]), x[i][1], x[i+1][1]])
    e.append([abs(y[i][0]-y[i+1][0]), y[i][1], y[i+1][1]])

e.sort()

uft = UnionFind(N)

ans = 0
for w, s, t in e:
    if not uft.same(s, t):
        uft.union(s, t)
        ans += w

print(ans)