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

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
#N=10**18
if N==1:
    print(0)
    exit()

i=2
#N=10**12
def sosuu(x):
    sosuulst=[]
    i=2
    while i<int(x**.5+1):
        for s in sosuulst:
            if i%s==0:
                break
        else:
            sosuulst.append(i)
        i+=1
    for s in sosuulst:
        if x%s==0:
            while x%s==0:
                x//=s
            if x==1:
                return(1)
            else:
                return(0)
    return(1)


c=0
lst=[]
lst2=[]
for i in range(2,int(N**.5+1)):
    if N%i==0:
        lst.append(i)
        lst2.append(N//i)
lst2.reverse()
lst+=lst2
lst.append(N)
#print(lst)
for i in lst:

    if N%i==0:

        if sosuu(i):
        #    print(N,i)
            N//=i
            c+=1
print(c)


### FIXED CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
#N=10**18

lst=defaultdict(int)
lst2=[]
lst3=[]
for i in range(2,int(N**.5)+100):
    if N%i==0:
        lst2.append(i)
        lst3.append(N//i)
lst3.reverse()
lst2+=lst3

for i in lst2+[N]:
    while N>1 and N%i==0:
        N//=i
        lst[i]+=1
c=0
#print(lst)
for s in lst:
    l=lst[s]
    i=1
    while l>=i:
        l-=i
        c+=1
        i+=1
print(c)
### BUGGY CODE ###

import sys
import numpy as np

input = sys.stdin.readline
N = int(input())
B = [int(i)*2 for i in input().split()]

a = [[0]*N for i in range(N)]

for i in range(N-1):
    a[i][i] += 1
    a[i][i+1] += 1

a[-1][0] += 1
a[-1][-1] += 1

A = np.array(a)
b = np.array(B)

x = np.linalg.solve(A, b)

print(*x.astype(int))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
a = [int(i) for i in input().split()]

s = sum(a)
x = [None]*N
x[0] = s - 2 * (sum(a[1::2]))

for i in range(1,N):
    x[i] = 2 * a[i-1] - x[i-1]

print(*x)
### BUGGY CODE ###

import numpy as np
import itertools
N, M, K = map(int, input().split())
Q = [np.asarray(input().split(), dtype=int) for i in range(N)]
min_cost = 10**9
for q in itertools.permutations(Q):
  cost = 0
  C = np.zeros(M)
  for i in q:
    cost += i[0]
    C = C + i[1:]
    if (C >= K).all():
      min_cost = min([cost, min_cost])
      break
print(min_cost) if min_cost != 10**9 else print(-1)


### FIXED CODE ###

import numpy as np
import itertools
N, M, K = map(int, input().split())
Q = [np.asarray(input().split(), dtype=int) for i in range(N)]
min_cost = 10**9
def dfs(cost, C, depth=0):
  global min_cost
  if (C >= K).all():
    min_cost = min([cost, min_cost])
    return
  if depth == N:
    return
  dfs(cost+Q[depth][0], C + Q[depth][1:], depth+1)
  dfs(cost, C, depth+1)
  
dfs(0, np.zeros(M))
    
print(min_cost) if min_cost != 10**9 else print(-1)
### BUGGY CODE ###

n=int(input())
s=list(input())
b=[]
for i in range(1000):
	while len(str(i))<3:
		i="0"+str(i)
	for j in range(n):
		if str(i)[0]==s[j]:
			for k in range(j+1,n):
				if str(i)[1]==s[k]:
					for l in range(k+1,n):
						if str(i)[2]==s[l]:
							b.append(i)	
print(len(set(b)))

### FIXED CODE ###

n=int(input())
s=list(input())
counter=0
for i in range(1000):
	while len(str(i))<3:
		i="0"+str(i)
	i=str(i)
	if i[0] in s:
		a=s.index(i[0])
		if i[1] in s[a+1:]:
			b=s[a+1:].index(i[1])+a+1
			if i[2] in s[b+1:]:
				counter+=1
print(counter)
### BUGGY CODE ###


x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(key=lambda x:-x)
b.sort(key=lambda x:-x)
c.sort(key=lambda x:-x)
# queue=[beauty, indexa, indexb, indexc]
queue=[(a[0]+b[0]+c[0],0,0,0)]
canAdd=[[[1 for _ in range(z)]for _ in range(y)]for _ in range(x)]
beauty=[0 for _ in range(k)]
for index in range(k):
    queue.sort(key=lambda x:-x[0])
    # print(queue)
    beauty[index],indexa,indexb,indexc=queue[0]
    queue.pop(0)
    for da,db,dc in [(1,0,0),(0,1,0),(0,0,1)]:
        if indexa+da<x and indexb+db<y and indexc+dc<z:
            if canAdd[indexa+da][indexb+db][indexc+dc]:
                queue.append((a[indexa+da]+b[indexb+db]+c[indexc+dc],indexa+da,indexb+db,indexc+dc))
                canAdd[indexa+da][indexb+db][indexc+dc]=0
for i in range(k):
    print(beauty[i])


### FIXED CODE ###


x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(key=lambda x:-x)
b.sort(key=lambda x:-x)
c.sort(key=lambda x:-x)
beauty=[]
index=0
for i in range(x):
    for j in range(y):
        for l in range(z):
            if (i+1)*(j+1)*(l+1)<=k:
                beauty.append(a[i]+b[j]+c[l])
            else:
                break
beauty.sort(key=lambda x:-x)
for i in range(k):
    print(beauty[i])
### BUGGY CODE ###

S = input()
N = len(S)
 
for _ in range(N):
    fn = len(S)
    S = S.replace('01', '').replace('10', '')
    if fn == len(S):
        break
 
print(N - len(S))

### FIXED CODE ###

S = input()
N = len(S)
A = 0

for i in range(N):
    if S[i] == '1':
        A = A + 1

print(min(N - A, A)*2)
### BUGGY CODE ###

H,W,D = list(map(int,input().split()))
mat = [0 for i in range(H*W)]
A = []
for h in range(H):
    a = list(map(int,input().split()))
    A.append(a)
    for w in range(W):
        mat[a[w]-1] = [h,w]
Q = int(input())
LR = [list(map(int,input().split())) for i in range(Q)]

for l,r in LR:
    dis = 0
    now = mat[l-1]
    for i in range(l-1,r,D):
        dis += abs(mat[i][0]-now[0])+abs(mat[i][1]-now[1])
        now = mat[i]
    print(dis)
    

### FIXED CODE ###

H,W,D = list(map(int,input().split()))
mat = [0 for i in range(H*W)]
A = []
for h in range(H):
    a = list(map(int,input().split()))
    A.append(a)
    for w in range(W):
        mat[a[w]-1] = [h,w]
Q = int(input())
LR = [list(map(int,input().split())) for i in range(Q)]
dlist = [0 for i in range(H*W)]
for i in range(H*W):
    if i+1 > D:
        dlist[i] = abs(mat[i][0]-mat[i-D][0]) + abs(mat[i][1]-mat[i-D][1]) +dlist[i-D]
for l,r in LR:
    print(dlist[r-1]-dlist[l-1])
### BUGGY CODE ###

S = input()
N = len(S)
 
for i in range(N):
    fn = len(S)
    S = S.replace('01', '')
    S = S.replace('10', '')
    if fn == len(S):
        break
 
print(N - len(S))

### FIXED CODE ###

S = input()
N = len(S)
A = 0

for i in range(N):
    if S[i] == '1':
        A = A + 1

print(min(N - A, A)*2)
### BUGGY CODE ###

import itertools

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

ans = 0

for a,b,c in itertools.combinations(li, 3):
    if (a < b+c) and (b < c+a) and (c < a+b):
        ans += 1

print(ans)

### FIXED CODE ###

import bisect

N = int(input())
li = list(map(int, input().split()))
li = sorted(li)

ans = 0

for i in range(N):
    for j in range(i+1, N):
        cnt = bisect.bisect_left(li, li[i]+li[j])
        ans += cnt - j - 1

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

def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*w for _ in range(h))
    d=tuple([0]*w for _ in range(h))
    for i in range(h):
        for j in range(w):
            a[i][j]=a[i][j-1]+1if s[i][j]=='.'else 0
            b[i][~j]=b[i][-j]+1if s[i][-j-2]=='.'else 0
    for j in range(w):
        for i in range(h):
            c[i][j]=c[i-1][j]+1if s[i][j]=='.'else 0
            d[~i][j]=d[-i][j]+1if s[~i][j]=='.'else 0
    print(max(sum(u)-3for t in zip(a,b,c,d)for u in zip(*t)))
main()

### FIXED CODE ###

def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*w for _ in range(h))
    d=tuple([0]*w for _ in range(h))
    for i in range(h*w):
        i,j=divmod(i,w)
        a[i][j]=a[i][j-1]+1if s[i][j]=='.'else 0
        b[i][~j]=b[i][-j]+1if s[i][-j-2]=='.'else 0
        c[i][j]=c[i-1][j]+1if s[i][j]=='.'else 0
        d[~i][j]=d[-i][j]+1if s[~i][j]=='.'else 0
    print(max(a[i][j]+b[i][j]+c[i][j]+d[i][j]-3for i in range(h)for j in range(w)))
main()
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

from collections import Counter

N = int(input())
a = list(map(float, input().split()))

dp_memo = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]

def dp(i,j,k):
    if i==0 and j==0 and k==0:
        return 0
    elif i<0 or j<0 or k<0:
        return 0
    elif dp_memo[i][j][k] > 0:
        return dp_memo[i][j][k]
    else:
        tmp = dp(i,j+1,k-1)*(k/(i+j+k)) + dp(i+1,j-1,k)*(j/(i+j+k)) + dp(i-1,j,k)*(i/(i+j+k)) + N/(i+j+k)
        dp_memo[i][j][k] = tmp
        return tmp

c = Counter(a)
print(dp(c[1], c[2], c[3]))

### FIXED CODE ###

def main():
    from collections import Counter

    N = int(input())
    a = list(map(float, input().split()))

    dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    c = Counter(a)

    # メモ化再帰ではpypy3でもTLEするのでforループを使う
    # j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
    for k in range(c[3]+1):
        for j in range(c[3]+c[2]-k+1):
            for i in range(N-j-k+1):
                if i+j+k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: # IndexError防止
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) # 割り算をまとめないとTLE

    print(dp[c[1]][c[2]][c[3]])

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

'''input
3
1
2 1
1
1 1
1
2 0
'''
# A coding delight
from sys import stdin, stdout
import gc
from copy import deepcopy
# gc.disable()
input = stdin.readline



def consistent(choose):
	T = set()
	F = set()
	for i in choose:
		T.add(i + 1)

	for i in choose:
		aux = data[i]
		for j in range(len(aux)):
			p, v = aux[j]
			if v == 0:
				if p in T:
					return False 
				else:
					F.add(p)
			else:
				if p in F:
					return False
				else:
					T.add(p)
	pT = set()
	pF = set()
	while len(T) + len(F) != len(pT) + len(pF):
		# print(T, F)
		pT = deepcopy(T)
		pF = deepcopy(F)
		for i in range(n):
			aux = data[i]
			if i + 1 in T:
				for j in range(len(aux)):
					p, v = aux[j]
					if v == 0:
						if p in T:
							return False 
						else:
							F.add(p)
					else:
						if p in F:
							return False
						else:
							T.add(p)
	# print(T, F)		
	return True

	
# main starts
n = int(input().strip())
data = []
for _ in range(n):
	k = int(input().strip())
	temp =[]
	for i in range(k):
		x, y = list(map(int, input().split()))
		temp.append([x, y])
	data.append(temp)
ans = 0

# generating subset
for i in range(1, 2**n):
	choose = []
	for k in range(n):
		if (1 << k) & i:
			choose.append(k)

	if consistent(choose):
		ans = max(ans, len(choose))
		# print(choose)

print(ans)

### FIXED CODE ###

'''input
3
1
2 1
1
1 1
1
2 0
'''
# A coding delight
from sys import stdin, stdout
import gc
from copy import deepcopy
# gc.disable()
input = stdin.readline



def consistent(choose):
	T = set()
	F = set()
	for i in choose:
		T.add(i + 1)

	for i in choose:
		aux = data[i]
		for j in range(len(aux)):
			p, v = aux[j]
			if v == 0:
				if p in T:
					return False 
				else:
					F.add(p)
			else:
				if p in F:
					return False
				else:
					T.add(p)
	pT = set()
	pF = set()
	while len(T) + len(F) != len(pT) + len(pF):
		# print(T, F)
		pT = deepcopy(T)
		pF = deepcopy(F)
		for i in range(n):
			aux = data[i]
			if i + 1 in T:
				for j in range(len(aux)):
					p, v = aux[j]
					if v == 0:
						if p in T:
							return False 
						else:
							F.add(p)
					else:
						if p in F:
							return False
						else:
							T.add(p)
	# print(T, F)		
	return True

	
# main starts
n = int(input().strip())
data = []
for _ in range(n):
	k = int(input().strip())
	temp =[]
	for i in range(k):
		x, y = list(map(int, input().split()))
		temp.append([x, y])
	data.append(temp)
ans = 0

# generating subset
for i in range(1, 2**n):
	choose = []
	for k in range(n):
		if (1 << k) & i:
			choose.append(k)

	if consistent(choose):
		ans = max(ans, len(choose))
		# print(choose)

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

import sys
def input(): return sys.stdin.readline().rstrip()
S = input()
Q = int(input())
qs = list(input() for _ in range(Q))
rev = 0
for q in qs:
    q = q.split()
    if q[0] == '1':
        rev += 1
        rev %= 2
    else:
        if (q[1]=='1' and rev==0) or (q[1]=='2' and rev==1):
            S = q[2] + S
        else:
            S = S + q[2]
print(S if rev == 0 else S[::-1])

### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()
S = deque(input())
rev = False
apdlft = S.appendleft
apd = S.append

for _ in range(int(input())):
    q = input().split()
    if q[0] == '1':
        rev = not(rev)
    else:
        if (q[1]=='1' and rev is False) or (q[1]=='2' and rev is True):
            apdlft(q[2])
        else:
            apd(q[2])

if rev:
    print((''.join(S))[::-1])
else:
    print(''.join(S))
### BUGGY CODE ###

from heapq import heappop,heappush
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
lst=[]
for i in range(n):
    heappush(lst,[-b[i],i])
count=0
while lst:
    c=heappop(lst)
    num, j=c
    if -num==a[j]:
        continue
    count+=1
    if j==0:
        i=n-1
        k=1
    elif j==n-1:
        i=n-2
        k=0
    else:
        i=j-1
        k=j+1
    num*=(-1)
    num-=(b[i]+b[k])
    if num>a[j]:
        heappush(lst,[-num, j])
        b[j]=num
    elif num==a[j]:
        b[j]=num
        continue
    else:
        print(-1)
        break
else:
    print(count)

### FIXED CODE ###

from heapq import heappush,heappop
import sys
input=sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
lst=[]
for i in range(N):
    heappush(lst,(-B[i],i))

count=0
while lst:
    h,i=heappop(lst)
    h=-h
    x,z=B[i-1],B[(i+1)%N]
    kkk=x+z
    if (h-A[i])%kkk==0:
        count+=(h-A[i])//kkk
        B[i]=A[i]
        continue
    elif kkk>=h:
        print(-1)
        sys.exit()
    else:
        count+=h//kkk
        h=h%kkk
        B[i]=h    
        if A[i]>h:
            print(-1)
            sys.exit()
        heappush(lst,(-h,i))

if A==B:
    print(count)
else:
    print(-1)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

ans_arr = []
for i in range(Q):
    l, r = map(int, input().split())
    tmp = S[l-1:r]
    tmp = tmp.replace("AC", "_")
    ans_arr.append(tmp.count("_"))

for i in range(Q):
    print(ans_arr[i])

### FIXED CODE ###

N, Q = map(int, input().split())
S = list(input())

arr = [0 for j in range(N)]
A_tmp = 0
S_tmp = 0

for i in range(N):
    if S[i] == "A":
        A_tmp = 1
        arr[i] = S_tmp
    elif A_tmp == 1 and S[i] == "C":
        S_tmp += 1
        arr[i] = S_tmp
        A_tmp = 0
    else:
        arr[i] = S_tmp
        A_tmp = 0

ans_arr = []
for i in range(Q):
    l, r = map(int, input().split())
    
    ans_arr.append(arr[r-1]-arr[l-1])

for i in range(Q):
    print(ans_arr[i])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
answer = 1
for i in range(N):
    answer *= A[i]
print(answer if answer <= 10 ** 18 else -1)


### FIXED CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
if A[0] == 0:
    print(0)
    exit()
answer = 1
for i in A:
    answer *= i
    if answer > 10 ** 18:
        print(-1)
        break
else:
    print(answer)
### BUGGY CODE ###

import heapq
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
q = []
for i, b in enumerate(B):
    q.append([-b, i])
heapq.heapify(q)
ans = 0
while len(q)>0:
    b, idx = q[0]#heapq.heappop(q)
    b = -b
    b_p1, b_m1 = B[(idx+1)%N], B[idx-1]
    d = b_p1 + b_m1

    p = min((b-A[idx])//d, (b-b_m1)//d+1, (b-b_p1)//d+1)

    b -= p * d
    B[idx] = b
    ans += p
    #print(B, idx, ans, p_)
    if b > A[idx]:
        #heapq.heappush(q, [-b, idx])
        heapq.heapreplace(q, [-b, idx])
        if q[0][1] ==idx:
            print(-1)
            exit()
    else:
        heapq.heappop(q)
print(ans)


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline

# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
q = []
q = [(-b, i) for i, b in enumerate(B)]
heapq.heapify(q)
ans = 0
N_m1 = N-1
while len(q)>0:
    b, idx = q[0]
    b = -b
    b_p1, b_m1 = B[idx+1 if idx<N_m1 else 0], B[idx-1]
    d = b_p1 + b_m1

    a = A[idx]
    p = min((b-a)//d, (b-b_m1)//d+1, (b-b_p1)//d+1)

    b -= p * d
    B[idx] = b
    ans += p
    if b > a:
        heapq.heapreplace(q, (-b, idx))
        if q[0][1] == idx:
            print(-1)
            exit()
    else:
        heapq.heappop(q)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import heapq
def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

n = int(input())
st = []
edge = [[] for i in range(n)]
for i in range(n):
    x,y = map(int,input().split())
    st.append((i,x,y))
    
from operator import itemgetter
bb = tuple(sorted(st,key=itemgetter(1)))
chk = tuple(sorted(st,key=itemgetter(2)))
#print(bb,chk)

for i in range(n-1):
  x = bb[i][0]
  y = bb[i+1][0]
  z = bb[i+1][1]-bb[i][1]
  #print(z)
  edge[x].append([z,y])
  edge[y].append([z,x])
  
for i in range(n-1):
  a = chk[i][0]
  b = chk[i+1][0]
  c = chk[i+1][2]-chk[i][2]
  #print(c)
  edge[a].append([c,b])
  edge[b].append([c,a])
  
print(prim_heap())

### FIXED CODE ###

import sys
input = sys.stdin.readline
import heapq
def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

from collections import deque
n = int(input())
st = deque([])

edge = deque([[] for i in range(n)])
for i in range(n):
    x,y = map(int,input().split())
    st_append = st.append
    st_append((i,x,y))
    
from operator import itemgetter
bb = tuple(sorted(st,key=itemgetter(1)))
chk = tuple(sorted(st,key=itemgetter(2)))
#print(bb,chk)

for i in range(n-1):
  x = bb[i][0]
  y = bb[i+1][0]
  z = bb[i+1][1]-bb[i][1]
  edge[x].append((z,y))
  edge[y].append((z,x))
  
for i in range(n-1):
  a = chk[i][0]
  b = chk[i+1][0]
  c = chk[i+1][2]-chk[i][2]
  edge[a].append((c,b))
  edge[b].append((c,a))
  
edge = tuple(edge)
print(prim_heap())
### BUGGY CODE ###

import collections
n = int(input())
A = list(map(int,input().split()))
B = collections.Counter(A)
C = B.copy()
for i in A:
    B[i] -= 1
    total = 0
    for j in B.values():
        total += j*(j-1)//2
    B = C.copy()
    print(total)

### FIXED CODE ###

import collections
n = int(input())
A = list(map(int,input().split()))
B = collections.Counter(A)
C = B.copy()
total = 0
for i in B.values():
    total += i*(i-1)//2
for i in A:
    print(total - B[i]+1)
### BUGGY CODE ###

# input
N, M = map(int, input().split())
check = []
c_append = check.append
for i in range(1, M + 1):
    L, R = map(int, input().split())
    c_append(set(list(range(L, R + 1))))

# check
mastar_keys = set(list(range(1, N + 1)))
for c in sorted(check, key=lambda x: len(x)):
    mastar_keys = mastar_keys & c
    if len(mastar_keys) == 0:
        break

print(len(mastar_keys))

### FIXED CODE ###

# input & check
N, M = map(int, input().split())
x, y = 0, N
for i in range(1, M + 1):
    L, R = map(int, input().split())
    x = max(x, L)
    y = min(y, R)

print(len(range(x, y + 1)))
### BUGGY CODE ###

n = int(input())
n = str(n)
k = 0
pay = 0
n_list = []
for i in n[::-1]:
    n_list.append(int(i))
n_list.append(0)
ans = 0
for i in range(len(n_list) - 1):
    num = n_list[i]
    if (num <= 5 and n_list[i + 1] < 5) or num < 5:
        # pay += num * 10 ** k
        ans += num
    else:
        n_list[i + 1] += 1
        ans += 10 - n_list[i]
    k += 1

# pay += n_list[-1] * 10 ** k
ans += n_list[-1]
print(ans)
# oturi = pay - int(n)
# ans = 0
#
# for i in str(pay):
#     ans += int(i)
# for i in str(oturi):
#     ans += int(i)
# print(ans)

### FIXED CODE ###

n = input()
k = 0
pay = 0
n_list = []
for i in n[::-1]:
    n_list.append(int(i))
n_list.append(0)
ans = 0
for i in range(len(n_list) - 1):
    num = n_list[i]
    if num < 5:
        ans += num
    elif (num <= 5 and n_list[i + 1] < 5):
        ans += num
    else:
        n_list[i + 1] += 1
        ans += 10 - num

ans += n_list[-1]
print(ans)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
sharps = []
for h, line in enumerate(A):
    for w, p in enumerate(line):
        if p == '#':
            sharps.append([h, w, 0])

q = deque(sharps)
while q:
    i, j, score = q.popleft()
    for mi, mj in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        ni = i + mi
        nj = j + mj
        if ni < 0 or H <= ni or nj < 0 or W <= nj or A[ni][nj] == '#':
            continue
        A[ni][nj] = '#'
        q.append([ni, nj, score+1])
print(score)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
sharps = []
for h, line in enumerate(A):
    sharps += [[h, w, 0] for w, p in enumerate(line) if p == '#']

q = deque(sharps)
while q:
    i, j, score = q.popleft()
    for mi, mj in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        ni = i + mi
        nj = j + mj
        if ni < 0 or H <= ni or nj < 0 or W <= nj or A[ni][nj] == '#':
            continue
        A[ni][nj] = '#'
        q.append([ni, nj, score+1])
print(score)