Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
treedic = {}
for i in range(1, N+1):
    treedic[i] = {}
for i in range(N-1):
    a, b, c = map(int, input().split())
    treedic[a][b] = c
    treedic[b][a] = c

Q, K = map(int, input().split())
checked = set([K])
length = [0]*(N+1)
check = set([K])

while len(checked) < N:
    nextcheck = set()
    for i in check:
        for j in treedic[i].keys():
            if j not in checked:
                length[j] = length[i] + treedic[i][j]
                checked.add(j)
                nextcheck.add(j)
    check = nextcheck

for i in range(Q):
    x, y = map(int, input().split())
    print(length[x] + length[y])


Fixed submission:
def main():
    N = int(input())
    treedic = {}
    for i in range(1, N+1):
        treedic[i] = {}
    for i in range(N-1):
        a, b, c = map(int, input().split())
        treedic[a][b] = c
        treedic[b][a] = c

    Q, K = map(int, input().split())
    checked = set([K])
    length = [0]*(N+1)
    check = set([K])

    while len(checked) < N:
        nextcheck = set()
        for i in check:
            for j in treedic[i].keys():
                if j not in checked:
                    length[j] = length[i] + treedic[i][j]
                    checked.add(j)
                    nextcheck.add(j)
        check = nextcheck

    for i in range(Q):
        x, y = map(int, input().split())
        print(length[x] + length[y])


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = list(map(int, input().split()))

A = sorted(A)
if A[N-1] < K:
    print("IMPOSSIBLE")
    exit()

min_A = A[0]
for i in range(1,N):
    min_A = min(min_A,A[i]-A[i-1])

for j in range(N):
    if A[j]%min_A != 0:
        print("POSSIBLE")
        exit()
if K % min_A == 0:
    print("POSSIBLE")
else:
    print("INPOSSIBLE")


Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))

A = sorted(A)
if A[N-1] < K:
    print("IMPOSSIBLE")
    exit()

min_A = A[0]
for i in range(1,N):
    if A[i]-A[i-1] != 0:
        min_A = min(min_A,A[i]-A[i-1])

for j in range(N):
    if A[j]%min_A != 0:
        print("POSSIBLE")
        exit()
if K % min_A == 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]

S_list = {}
for i in range(M):
    S_list[i+1] = 0

participants = 10000
while len(S_list) > 0:
    for i in range(N):
        for j in range(M):
            if A[i][j] in S_list:
                S_list[A[i][j]] += 1
                break
    participants = min(participants,max(S_list.values()))
    for i in S_list.keys():
        if S_list[i] == max(S_list.values()):
            del S_list[i]
            break
    for i in S_list.keys():
        S_list[i] = 0

print(participants)


Fixed submission:
N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]

S_list = {}
for i in range(M):
    S_list[i+1] = 0

participants = 10000
while len(S_list) > 0:
    for i in range(N):
        for j in range(M):
            if A[i][j] in S_list:
                S_list[A[i][j]] += 1
                break
    participants = min(participants,max(S_list.values()))
    if participants == 1:
        break
    for i in S_list.keys():
        if S_list[i] == max(S_list.values()):
            del S_list[i]
            break
    for i in S_list.keys():
        S_list[i] = 0

print(participants)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect


def main():
    N = int(input())
    a = list(map(int, input().split()))

    s = [0, N+1]
    order = [0]*(N+1)

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

    ans = 0
    for i in range(1, N+1):
        bisect.insort_left(s, order[i])
        ans += i*(order[i]-s[bisect.bisect_left(s, order[i])-1]) * \
            (s[bisect.bisect_left(s, order[i])+1]-order[i])
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
N = int(input())
a = list(map(int, input().split()))

order = [0]*(N+1)

for i in range(N):
    order[a[i]] = i

ans = 0
checkR = list(range(N+1))
checkL = list(range(N+1))

for i in range(N, 0, -1):
    ans += i*(order[i] - checkR[order[i]] + 1)*(checkL[order[i]] - order[i]+1)
    checkR[checkL[order[i]]+1] = checkR[order[i]]
    checkL[checkR[order[i]]-1] = checkL[order[i]]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
a = list(map(int, input().split()))

s = [0, N+1]
order = [0]*(N+1)

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

ans = 0
for i in range(1, N+1):
    bisect.insort_left(s, order[i])
    ans += i*(order[i]-s[bisect.bisect_left(s, order[i])-1]) * \
        (s[bisect.bisect_left(s, order[i])+1]-order[i])
print(ans)


Fixed submission:
N = int(input())
a = list(map(int, input().split()))

order = [0]*(N+1)

for i in range(N):
    order[a[i]] = i

ans = 0
checkR = list(range(N+1))
checkL = list(range(N+1))

for i in range(N, 0, -1):
    ans += i*(order[i] - checkR[order[i]] + 1)*(checkL[order[i]] - order[i]+1)
    checkR[checkL[order[i]]+1] = checkR[order[i]]
    checkL[checkR[order[i]]-1] = checkL[order[i]]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, x = map(int, input().split())
a = list(map(int, input().split()))

ans = float("INF")
b = [float("INF")]*N
for k in range(N):
    temp_ans = k*x
    for i in range(N):
        b[i] = min(b[i],a[i-k])
        temp_ans += b[i]
    ans = min(ans,temp_ans)
print(ans)


Fixed submission:
N, x = map(int, input().split())
a = list(map(int, input().split()))

ans = float("INF")
b = [[float("INF")]*N for _ in range(N)]
b[0] = a
for k in range(N):
    for i in range(N):
        b[k][i] = min(b[k-1][i],a[i-k])
    ans = min(ans, sum(b[k])+k*x)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N, x = map(int, input().split())
a = list(map(int, input().split()))

ans = float("INF")
b = np.full((N,N),np.inf)
b[0] = a
for k in range(N):
    for i in range(N):
        b[k][i] = min(b[k-1][i],a[i-k])
    ans = min(ans, sum(b[k])+k*x)

print(int(ans))


Fixed submission:
N, x = map(int, input().split())
a = list(map(int, input().split()))

ans = float("INF")
b = [[float("INF")]*N for _ in range(N)]
b[0] = a
for k in range(N):
    for i in range(N):
        b[k][i] = min(b[k-1][i],a[i-k])
    ans = min(ans, sum(b[k])+k*x)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, x = map(int, input().split())
a = list(map(int, input().split()))

ans = float("INF")
b = a
for k in range(N):
    c = [float("INF")]*N
    ans_inst = 0
    for i in range(N):
        c[i] = min(b[i],a[i-k])
        ans_inst += c[i]
    ans = min(ans, ans_inst+k*x)
    b = c
print(ans)


Fixed submission:
N, x = map(int, input().split())
a = list(map(int, input().split()))

ans = float("INF")
b = [[float("INF")]*N for _ in range(N)]
b[0] = a
for k in range(N):
    for i in range(N):
        b[k][i] = min(b[k-1][i],a[i-k])
    ans = min(ans, sum(b[k])+k*x)

print(ans)
Buggy python submission (verdict: Runtime Error):
atcoder-tools: The pre-rendered templates are not found.import numpy as np

N, M = map(int, input().split())
AC_or_not = np.array([0] * N)
n_penalty = np.array([0] * N)

for _ in range(M):
    prob, wa_ac = input().split()
    prob = int(prob) - 1
    if wa_ac == 'AC':
        AC_or_not[prob] = 1
    else:
        if not AC_or_not[prob]:
            n_penalty[prob] += 1

print(sum(AC_or_not), sum(n_penalty * AC_or_not))

Fixed submission:
import numpy as np

N, M = map(int, input().split())
AC_or_not = np.array([0] * N)
n_penalty = np.array([0] * N)

for _ in range(M):
    prob, wa_ac = input().split()
    prob = int(prob) - 1
    if wa_ac == 'AC':
        AC_or_not[prob] = 1
    else:
        if not AC_or_not[prob]:
            n_penalty[prob] += 1

print(sum(AC_or_not), sum(n_penalty * AC_or_not))
Buggy python submission (verdict: Runtime Error):
from math import gcd, ceil

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

n, M = map(int, input().split())
A = tuple(map(lambda x: int(int(x)/2), input().split()))
scm_core = 1
for a in A:
    scm_core = lcm(scm_core, a)

print(ceil(M // scm_core / 2))

Fixed submission:
from fractions import gcd
from math import ceil

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

n, M = map(int, input().split())
A = tuple(map(lambda x: int(int(x)/2), input().split()))
scm_core = 1
for a in A:
    scm_core = lcm(scm_core, a)

canmake_scm = True
for a in A:
    if scm_core // a % 2 == 0:
        canmake_scm = False

if canmake_scm:
    print(ceil(M // scm_core / 2))
else:
    print(0)
Buggy python submission (verdict: Runtime Error):
from math import sqrt

x = int(input()) - 1
if x >= 2:
    pnums = []
    for i in range(2, int(sqrt(x))+1):
        for j in pnums:
            if i % j == 0:
                break
        else:    
            pnums.append(i)

while True:
    x += 1
    x_sqrt = sqrt(x)
    if x_sqrt.is_integer():
        pnums.append(x_sqrt)
        break
    
    for a in pnums:
        if x % a == 0:
            break
    else:
        print(x)
        break
    

Fixed submission:
from math import sqrt

x = int(input()) - 1
pnums = []
if x >= 4:
    for i in range(2, int(sqrt(x))+1):
        for j in pnums:
            if i % j == 0:
                break
        else:    
            pnums.append(i)

while True:
    x += 1
    x_sqrt = sqrt(x)
    if x_sqrt.is_integer():
        pnums.append(x_sqrt)
        continue
    
    for a in pnums:
        if x % a == 0:
            break
    else:
        print(x)
        break
Buggy python submission (verdict: Runtime Error):
d = ["-","SAT","FRI","THU","WED","TUR","MON","SUN"]
input()
for n,s in enumerate(d):
    if s == S:
        print(n)


Fixed submission:
d = ["-","SAT","FRI","THU","WED","TUE","MON","SUN"]
S = input()
for n,s in enumerate(d):
    if s == S:
        print(n)
Buggy python submission (verdict: Time Limit Exceeded):
def resolve():
    N = int(input())
    L = list(map(int,input().split()))
    L = sorted(L,reverse=True)
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            for k in range(N-1,j,-1):
                if L[k] + L[j] > L[i]:
                    ans += k-j
                    break
    print(ans)
resolve()

Fixed submission:
def resolve():
    import bisect
    N = int(input())
    L = list(map(int,input().split()))
    L = sorted(L)
    ans = 0
    for i in range(N-1,-1,-1):
        for j in range(i-1,-1,-1):
            p = j - bisect.bisect_left(L,L[i]-L[j]+1)
            if p < 1:
                break
            ans += p
    print(ans)
resolve()
Buggy python submission (verdict: Runtime Error):
import math
def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

A,B = map(int,input().split())
 
GCD = math.gcd(A,B)
 
prime_list = get_sieve_of_eratosthenes(GCD)
counter = 1
for p in prime_list:
    if GCD % p == 0:
        counter += 1
        while(GCD % p == 0):
            GCD = GCD // p
print(counter)
 

Fixed submission:
N = int(input())
if N % 2 == 1:
    odd = N // 2 + 1
else:
    odd = N // 2
print(odd/N)
Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
h = list(map(int,input().split))
h = [100,200,300,400,500]
counter = 0
for ph in h:
    if ph >= K:
        counter+= 1
print(counter)

Fixed submission:
N,K = map(int,input().split())
h = list(map(int,input().split()))
counter = 0
for ph in h:
    if ph >= K:
        counter+= 1
print(counter)
Buggy python submission (verdict: Runtime Error):
import numpy as np
N = int(input())
A = list(map(int,input().split()))
ans = np.argsort(A)+1
for a in ans:
    sys.stdout.write(str(a))
    sys.stdout.write(" ")

Fixed submission:
import numpy as np
import sys
N = int(input())
A = list(map(int,input().split()))
ans = np.argsort(A)+1
for a in ans:
    sys.stdout.write(str(a))
    sys.stdout.write(" ")

Buggy python submission (verdict: Runtime Error):
import numpy as np
N = int(input())
A = list(map(int,input().split()))
ans = np.argsort(A)+1
for a in ans:
    sys.stdout.write(str(a))
    sys.stdout.write(" ")


Fixed submission:
import numpy as np
import sys
N = int(input())
A = list(map(int,input().split()))
ans = np.argsort(A)+1
for a in ans:
    sys.stdout.write(str(a))
    sys.stdout.write(" ")
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB = sorted(AB,key=lambda x:x[0],reverse=True)
AB = sorted(AB,key=lambda x:x[1],reverse=True)
dp = [0 for _ in range(M)]
rest = M
for a,b in AB:
    aa = a-1
    if aa >= rest:
        continue
    if dp[aa] == 0:
        dp[aa] = b
    else:
        flag = False
        for i in range(aa,rest):
            if dp[i] == 0:
                dp[i] = b
                flag = True
                break
        if flag is False:
            rest = aa
print(sum(dp))

Fixed submission:
import heapq
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB = sorted(AB,key=lambda x:x[0])
dp = [0 for _ in range(M)]
p = 0
q = []
for a,b in AB:
    n = a-1
    if n > M-1:
        break
    if n != p:
        while q and p < n:
            dp[p] = heapq.heappop(q)
            p += 1
        p = n
    heapq.heappush(q,b*(-1))
while q and p < M:
    dp[p] = heapq.heappop(q)
    p += 1
print(sum(dp)*(-1))
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
first = []
for a in A:
    i = bisect.bisect_left(first,a)
    if i == 0:
        first.insert(0,a)
    else:
        first[i-1] = a
print(len(first))

Fixed submission:
import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
first = [-1 for _ in range(N)]
for a in A:
    i = bisect.bisect_left(first,a)
    first[i-1] = a
ctr = N
for f in first:
    if f == -1:
        ctr -= 1
print(ctr)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(input()) for _ in range(N)]
first = []
for a in A:
    i = bisect.bisect_left(first,a)
    if i == 0:
        first.insert(0,i)
    else:
        first[i-1] = a
print(len(first))

Fixed submission:
import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
first = [-1 for _ in range(N)]
for a in A:
    i = bisect.bisect_left(first,a)
    first[i-1] = a
ctr = N
for f in first:
    if f == -1:
        ctr -= 1
print(ctr)
Buggy python submission (verdict: Runtime Error):
import collections
N,M = map(int,input().split())
edge = collections.defaultdict(list)
for _ in range(M):
    u,v = map(int,input().split())
    edge[u-1].append(v-1)
S,T = map(int,fi.input().split())
dp = [-1 for _ in range(N)]
dp[S-1] = 0
q = collections.deque()
q.append(S-1)
while q:
    p = q.pop()
    for k1 in edge[p]:
        for k2 in edge[k1]:
            for k3 in edge[k2]:
                if dp[k3] == -1:
                    dp[k3] = dp[p] + 1
                    q.append(k3)
                    if k3 == T-1:
                        break
print(dp[T-1])

Fixed submission:
import collections
N,M = map(int,input().split())
edge = collections.defaultdict(list)
for _ in range(M):
    u,v = map(int,input().split())
    edge[u-1].append(v-1)
S,T = map(int,input().split())
dp = [[-3 for _ in range(3)] for _ in range(N)]
dp[S-1][0] = 0
q = collections.deque()
q.append((S-1,0))
while q:
    p,step = q.popleft()
    next_step = (step+1)%3
    for e in edge[p]:
        if dp[e][next_step] == -3:
            dp[e][next_step] = dp[p][step] + 1
            q.append((e,next_step))
            if e == T-1 and next_step == 0:
                break
print(dp[T-1][0] // 3)
Buggy python submission (verdict: Runtime Error):
def resolve():
    N = int(input())
    import collections
    n_dict = collections.defaultdict(list)
    for i in range(N-1):
        u,v,w = map(int,input().split())
        n_dict[u-1].append((v-1,w))
        n_dict[v-1].append((u-1,w))

    color = [-1 for _ in range(N)]

    def paint(i,c):
        color[i] = c
        for n,w in n_dict[i]:
            if color[n] == -1:
                paint(n,c^1) if w % 2 != 0 else paint(n,c)
            else:
                continue
        return
    for i in range(N):
        if color[i] == -1:
            paint(i,1)   
        print(color[i])
resolve()

Fixed submission:
def resolve():
    N = int(input())
    import collections
    n_dict = collections.defaultdict(list)
    for i in range(N-1):
        u,v,w = map(int,input().split())
        n_dict[u-1].append((v-1,w))
        n_dict[v-1].append((u-1,w))

    color = [-1 for _ in range(N)]

    d = collections.deque()
    for i in range(N):
        if color[i] == -1:
            d.append((i,1))
        while d:
            j,c = d.pop()
            color[j] = c
            for n,w in n_dict[j]:
                if color[n] == -1:
                    d.append((n,c^1)) if w % 2 != 0 else d.append((n,c))
                else:
                    continue
        print(color[i])
resolve()

Buggy python submission (verdict: Runtime Error):
def resolve():
    N = int(input())
    import collections
    n_dict = collections.defaultdict(list)
    for i in range(N-1):
        u,v,w = map(int,input().split())
        n_dict[u-1].append((v-1,w))
        n_dict[v-1].append((u-1,w))

    color = [-1 for _ in range(N)]

    def paint(i,c):
        color[i] = c
        for n,w in n_dict[i]:
            if color[n] == -1:
                paint(n,c^1) if w % 2 != 0 else paint(n,c)
            else:
                return
        return
    for i in range(N):
        if color[i] == -1:
            paint(i,1)   
        print(color[i])
resolve()

Fixed submission:
def resolve():
    N = int(input())
    import collections
    n_dict = collections.defaultdict(list)
    for i in range(N-1):
        u,v,w = map(int,input().split())
        n_dict[u-1].append((v-1,w))
        n_dict[v-1].append((u-1,w))

    color = [-1 for _ in range(N)]

    d = collections.deque()
    for i in range(N):
        if color[i] == -1:
            d.append((i,1))
        while d:
            j,c = d.pop()
            color[j] = c
            for n,w in n_dict[j]:
                if color[n] == -1:
                    d.append((n,c^1)) if w % 2 != 0 else d.append((n,c))
                else:
                    continue
        print(color[i])
resolve()
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
from copy import deepcopy
A_sum = deepcopy(A)
cur_len = 1
count = N
ans = N
while cur_len <= N and count > 0:
    for i in range(N-cur_len):
        if A_sum[i] >= 0 and A_sum[i] ^ A[i+cur_len] == A_sum[i] + A[i+cur_len]:
            A_sum[i] = A_sum[i] + A[i+cur_len]
        elif A_sum[i] >= 0:
            A_sum[i] = -1
            count -= 1
    if A_sum[N-cur_len] >= 0:
        A_sum[N-cur_len] = -1
        count -= 1
    cur_len += 1
    ans += count
print(ans)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
L = 0
R = 0
S = A[0]
ans = 0
while(R < N-1):
    if S + A[R+1] == S ^ A[R+1]:
        S += A[R+1]
        R+= 1
    elif R > L:
        S -= A[L]
        ans += R - L + 1
        L += 1
    else:
        L += 1
        R += 1
        ans += 1
        S = A[L]
print(ans+(R-L+2)*(R-L+1)//2)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))

A_sum = A.copy()
cur_len = 1
count = N
ans = N
while cur_len <= N and count > 0:
    for i in range(N-cur_len):
        if A_sum[i] >= 0 and A_sum[i] ^ A[i+cur_len] == A_sum[i] + A[i+cur_len]:
            A_sum[i] = A_sum[i] + A[i+cur_len]
        elif A_sum[i] >= 0:
            A_sum[i] = -1
            count -= 1
    if A_sum[N-cur_len] >= 0:
        A_sum[N-cur_len] = -1
        count -= 1
    cur_len += 1
    ans += count
print(ans)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
L = 0
R = 0
S = A[0]
ans = 0
while(R < N-1):
    if S + A[R+1] == S ^ A[R+1]:
        S += A[R+1]
        R+= 1
    elif R > L:
        S -= A[L]
        ans += R - L + 1
        L += 1
    else:
        L += 1
        R += 1
        ans += 1
        S = A[L]
print(ans+(R-L+2)*(R-L+1)//2)
Buggy python submission (verdict: Time Limit Exceeded):
class Prim():
    def __init__(self,N):
        import collections
        self.N = N
        self.edge = collections.defaultdict(list)
    def add(self,a,b,cost):
        self.edge[a].append((b,cost))
        self.edge[b].append((a,cost))
    def cut_edge(self,start=0):
        import heapq,collections
        #new_edge = collections.defaultdict(list)
        edge_sum = 0
        node_flag = [False for _ in range(self.N)]
        node_flag[start] = True
        q = []
        for to,cost in self.edge[start]:
            heapq.heappush(q,(cost,start,to))
        while q :
            c,s,t = heapq.heappop(q)
            if node_flag[t] is False:
                #new_edge[s].append((t,c))
                edge_sum += c
                node_flag[t] = True
                for to,cost in self.edge[t]:
                    if not node_flag[to]:
                        heapq.heappush(q,(cost,t,to))
        return edge_sum

N = int(input())
graph = Prim(N)
xy = [list(map(int,input().split())) for _ in range(N)]
nx = [(i,xy[i][0]) for i in range(N)]
ny = [(i,xy[i][1]) for i in range(N)]
nx.sort(key=lambda x:x[1])
ny.sort(key=lambda x:x[1])

for i in range(N-1):
    prev_n,prev_x = nx[i]
    next_n,next_x = nx[i+1]
    graph.add(prev_n,next_n,next_x-prev_x)
    prev_n,prev_y = ny[i]
    next_n,next_y = ny[i+1]
    graph.add(prev_n,next_n,next_y-prev_y)
print(graph.cut_edge())

Fixed submission:
class Prim():
    def __init__(self,N):
        import collections
        self.N = N
        self.edge = collections.defaultdict(list)
    def add(self,a,b,cost):
        self.edge[a].append((b,cost))
        self.edge[b].append((a,cost))
    def cut_edge(self,start=0):
        import heapq,collections
        #new_edge = collections.defaultdict(list)
        edge_sum = 0
        node_flag = [False for _ in range(self.N)]
        node_flag[start] = True
        q = []
        for to,cost in self.edge[start]:
            heapq.heappush(q,(cost,start,to))
        while q :
            c,s,t = heapq.heappop(q)
            if node_flag[t] is False:
                #new_edge[s].append((t,c))
                edge_sum += c
                node_flag[t] = True
                for to,cost in self.edge[t]:
                    if not node_flag[to]:
                        heapq.heappush(q,(cost,t,to))
        return edge_sum

N = int(input())
graph = Prim(N)
xy = [list(map(int,input().split())) for _ in range(N)]
nx = [(i,xy[i][0]) for i in range(N)]
ny = [(i,xy[i][1]) for i in range(N)]
nx.sort(key=lambda x:x[1])
ny.sort(key=lambda x:x[1])

for i in range(N-1):
    prev_n,prev_x = nx[i]
    next_n,next_x = nx[i+1]
    graph.add(prev_n,next_n,next_x-prev_x)
    prev_n,prev_y = ny[i]
    next_n,next_y = ny[i+1]
    graph.add(prev_n,next_n,next_y-prev_y)
print(graph.cut_edge())