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

def main():
    n, a = map(int, input().split())
    x = tuple(map(int, input().split()))

    sm_mx = sum(x)

    dp = [[[0] * (sm_mx + 1) for i in range(n + 1)] for j in range(n + 1)]

    dp[0][0][0] = 1

    for i, e in enumerate(x, 1):
        for j in range(n + 1):
            for sm in range(sm_mx + 1):
                if i >= 1 and sm < e:
                    dp[i][j][sm] = dp[i-1][j][sm]
                elif i >= 1 and j >= 1 and sm >= e:
                    dp[i][j][sm] = dp[i-1][j][sm] + dp[i-1][j-1][sm-e]
                else:
                    dp[i][j][sm] = 0

    ans = 0
    for i in range(1, n + 1):
        if i <= sm_mx / a:
            ans += dp[n][i][i*a]

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    n, a = map(int, input().split())
    x = tuple(map(int, input().split()))

    sm_mx = sum(x)

    dp = [[[0] * (sm_mx + 1) for _ in range(n + 1)] for _ in range(n + 1)]

    dp[0][0][0] = 1

    for i, e in enumerate(x, 1):
        for j in range(n + 1):
            for sm in range(sum(x[:i]) + 1):
                if sm < e:
                    dp[i][j][sm] = dp[i-1][j][sm]
                elif j >= 1 and sm >= e:
                    dp[i][j][sm] = dp[i-1][j][sm] + dp[i-1][j-1][sm-e]

    ans = 0
    for i in range(1, n + 1):
        if i > sm_mx / a:
            break
        ans += dp[n][i][i*a]

    print(ans)


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

a=input()
b=[]
for i in range(a):
    c=input()
    if c in b:
        b.remove(c)
    else:
        b.append(c)
print len(b)

### FIXED CODE ###

a=input()
b=[]
for i in range(a):
    b.append(input())
b.sort()
c=[]
pre=0
time=0
for i in b:
    if pre==i:
        time+=1
    else:
        if time%2==1:
            c.append(pre)
        pre=i
        time=1
if time%2!=0 and pre!=0:
    c.append(pre)
print len(c)
### BUGGY CODE ###

n, m = map(int, input().split())

MOD = 10 ** 9 + 7

if m == 1:
    print('1')
    exit()

factor = []
temp = 0
x = 2
while m > 1:
    if m % x == 0:
        m //= x
        temp += 1
    elif temp > 0:
        factor.append(temp)
        temp = 0
        x += 1
    else:
        x += 1
factor.append(temp)

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n;

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p;
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result;

ans = 1
for x in factor:
    ans *= cmb(x + n - 1, n - 1)
    ans %= MOD

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())

MOD = 10 ** 9 + 7

if m == 1:
    print('1')
    exit()

factor = []
temp = 0
x = 2
while m > 1:
    if m % x == 0:
        m //= x
        temp += 1
    elif temp > 0:
        factor.append(temp)
        temp = 0
        x += 1
    else:
        x += 1
factor.append(temp)

nCr = {}
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n;
    if (n, r) in nCr: return nCr[(n, r)]

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p;
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    nCr[(n, r)] = result
    return result;

ans = 1
for x in factor:
    ans *= cmb(x + n - 1, n - 1)
    ans %= MOD

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

import math
import copy
import fractions
import numpy as np
from functools import reduce

# ===FUNCTION===

def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

n, q = map(int, input().split())
inputStr = map(str, input())
condi = getSomeInputListInt(q)

string = list(inputStr)

tmpstring = []
for i in range(q):
    cnt = 0
    tmpstring = string[condi[i][0]-1 : condi[i][1]]

    for j in range(len(tmpstring)-1):
       if tmpstring[j]=="A" and tmpstring[j+1]=="C":
           cnt+=1

    print(cnt)



### FIXED CODE ###

import math
import copy
import fractions
import numpy as np
from functools import reduce

# ===FUNCTION===

def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

n, q = map(int, input().split())
inputStr = map(str, input())
condi = getSomeInputListInt(q)

string = list(inputStr)

cnt = 0
cntArray = np.zeros(len(string))

tmpstring = []
for i in range(1, len(string)):
    if string[i-1]=="A" and string[i]=="C":
        cnt+=1
    cntArray[i] = cnt

for i in range(q):
    ans = cntArray[condi[i][1]-1] - cntArray[condi[i][0]-1]
    print(int(ans))
### BUGGY CODE ###

n, k = map(int, input().split())
ps = list(map(int, input().split()))

pnmax = 0
for i in range(0, n-k+1):
  pn = 0
  for j in range(k):
  	pn = pn + ps[i+j]
  pnmax = max(pnmax, pn)

print((pnmax+k)/2)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

ans = sum(p[:k])

psum = [0] * n
psum[0] = p[0]
for i in range(1, n):
  psum[i] = psum[i-1] + p[i]

anss = [0] * n
for i in range(n-k):
  anss[i] = psum[i+k] - psum[i]

print((max(ans, max(anss))+k)/2)
### BUGGY CODE ###

X,Y,Z,K = map(int, input().split())
a_list = [int(i) for i in input().split()]
b_list = [int(i) for i in input().split()]
c_list = [int(i) for i in input().split()]
a_list.sort(reverse = True)
b_list.sort(reverse = True)
c_list.sort(reverse = True)
total_list = []
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if (i+1)*(j+1)*(k+1) <= K:
                total_list.append(a_list[i] + b_list[j] + c_list[k])
total_list =  sorted(total_list, reverse = True)
for i in range(K):
    print(total_list[i])

### FIXED CODE ###

from heapq import heappush, heappop

# input
X,Y,Z,K = map(int, input().split())
a_list = [int(i) for i in input().split()]
b_list = [int(i) for i in input().split()]
c_list = [int(i) for i in input().split()]
a_list.sort(reverse = True)
b_list.sort(reverse = True)
c_list.sort(reverse = True)

#solve
hq = []
arg_hash = {}
val = a_list[0] + b_list[0] + c_list[0]
heappush(hq, (-val,0,0,0))

for i in range(K):
    ans, a, b, c = heappop(hq)
    print(-ans)

    arg_a = (a+1, b, c)
    arg_b = (a, b+1, c)
    arg_c = (a, b, c+1)

    if a < X-1 and arg_a not in arg_hash:
        arg_hash[arg_a] = 1
        heappush(hq, (-(a_list[a+1]+b_list[b]+c_list[c]),)+arg_a)
    if b < Y-1 and arg_b not in arg_hash:
        arg_hash[arg_b] = 1
        heappush(hq, (-(a_list[a]+b_list[b+1]+c_list[c]),)+arg_b)
    if c < Z-1 and arg_c not in arg_hash:
        arg_hash[arg_c] = 1
        heappush(hq, (-(a_list[a]+b_list[b]+c_list[c+1]),)+arg_c)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
import itertools
N, P = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
odd = [ tmp for tmp in a if tmp%2 != 0]
even = [ tmp for tmp in a if tmp%2 == 0]
if P == 0:
    ans += 1
    b = [ len(list(itertools.combinations(odd,tmp))) for tmp in range(2, len(odd)+1, 2) ]
else:
    b = [ len(list(itertools.combinations(odd,tmp))) for tmp in range(1, len(odd)+1, 2) ]
c = [ len(list(itertools.combinations(even, tmp))) for tmp in range(1, len(even)+1) ]
factor = sum(b)
for tmp in c:
    ans += tmp*factor
if P == 0:
    ans += factor+sum(c)
else:
    ans += factor

print(ans)

### FIXED CODE ###

# -*- coding:utf-8 -*-
import itertools, math
N, P = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
odd = [ tmp for tmp in a if tmp%2 != 0]
even = [ tmp for tmp in a if tmp%2 == 0]
d = math.factorial(len(odd))
e = math.factorial(len(even))
if P == 0:
    ans += 1
    b = sum([ (d//math.factorial(len(odd)-tmp))//math.factorial(tmp) for tmp in range(2, len(odd)+1, 2) ])
else:
    b = sum([ (d//math.factorial(len(odd)-tmp))//math.factorial(tmp) for tmp in range(1, len(odd)+1, 2) ])
c = [ (e//math.factorial(len(even)-tmp))//math.factorial(tmp) for tmp in range(1, len(even)+1) ]
for tmp in c:
    ans += tmp*b
else:
    if P == 0:
        ans += b+sum(c)
    else:
        ans += b
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    s = input()
    res = 0
    r = []
    g = []
    b = []
    for i, c in enumerate(s):
        if c == 'R':
            r.append(i)
        elif c == 'G':
            g.append(i)
        else:
            b.append(i)
    
    cnt = 0
    for i in r:
        for j in g:
            diff = abs(j-i)
            for k in b:
                if abs(i-k) != diff and abs(j-k) != diff and abs(j-k) != abs(i-k):
                    cnt += 1
    print(cnt)
                    


if __name__ == '__main__':
    main()



### FIXED CODE ###

from itertools import permutations

def main():
    n = int(input())
    s = input()
    res = 0
    r = 0
    g = 0
    b = 0
    for i, c in enumerate(s):
        if c == 'R':
            r += 1
        elif c == 'G':
            g += 1
        else:
            b += 1
    
    rgb = []
    for t in permutations('RGB'):
        rgb.append(''.join(t))

    cnt = 0
    for i in range(n-2):
        for j in range(i+1, n-1):
            k = 2*j - i 
            if k >= n:
                break
            if (s[i] + s[j] + s[k]) in rgb:
                cnt += 1
    print(r*g*b - cnt)


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

N,W = map(int,input().split())
info = [list(map(int,input().split())) for i in range(N)]
# dp[i+1][w] i+1番目まで品物を選んで重さwのときの価値の最大値
# dp[0] = [0]*(W+1)
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
    for w in range(W+1):
        if  w - info[i][0] >= 0:
            dp[i+1][w] = max(dp[i][w-info[i][0]] + info[i][1],dp[i][w])
        else:    
            dp[i+1][w] = dp[i][w]
print(max(dp[N]))

### FIXED CODE ###

N,W = map(int,input().split())
info = [list(map(int,input().split())) for i in range(N)]
# dp[i+1][w] i+1番目まで品物を選んで重さwのときの価値の最大値
# dp[0] = [0]*(W+1)
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
    for w in range(W+1):
        if  w - info[i][0] >= 0:
            dp[i+1][w] = max(dp[i][w-info[i][0]] + info[i][1],dp[i][w])
        else:    
            dp[i+1][w] = dp[i][w]
print(dp[N][W])
### BUGGY CODE ###

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

mod = 10**9+7

import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


l = lcm(*A)
B = 0
for i in range(N):
  B += l//A[i]%mod
B %= mod
print(B)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7

import fractions
from functools import reduce

def gcd(x,y):
  if x == 0:
    return y
  else:
    return gcd(y-x*(y//x),x)
 

def lcm(x, y):
    return (x*y)//gcd(x,y)
    
l = 1
B = 0

for i in range(N):
  l = lcm(l,A[i])
for i in range(N):
  B += l//A[i]
B %= mod

print(B)
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
# 期待値
E = [(p+1)/2 for p in P]
#print(E)
# 隣接K個の和
ans = 0
for i in range(K, N+1):
    tmp_e = sum(E[i-K: i])
    #print(i, tmp_e)
    ans = max(ans, tmp_e)
print(ans)

### FIXED CODE ###

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

# 期待値
E = [(p+1)/2 for p in P]
#print(E)

# 累積和
S = [0] * (N+1)
for i in range(N):
    S[i+1] = S[i] + E[i]
#print(S)

# 隣接K個を取り出して足す
max_E = 0
for i in range(N-K+1):
    tmp_E = S[i+K] - S[i]
    #print(tmp_E)
    if tmp_E > max_E:
        max_E = tmp_E

print(max_E)
### BUGGY CODE ###

N = int(input())
L = sorted(list(map(int,input().split())))
table = [[0 for _ in range(N)] for _ in range(N)]
ans = 0
for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      if L[i]+L[j]<=L[k]:break 
      elif L[i]+L[j]>L[k] and L[j]+L[k]>L[i] and L[k]+L[i]>L[j]:
        ans += 1
print(ans)

### FIXED CODE ###

import bisect 
N = int(input())
L = sorted(list(map(int,input().split())))
ans = 0
for i in range(N-2):
  for j in range(i+1,N-1):
    idx = bisect.bisect(L,L[i]+L[j]-1)
    ans += idx-j-1
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())

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

L = []
for i in range(m):
    b,c = map(int, input().split())
    L.append((b,c))
    
A = sorted(A)

from bisect import bisect_left
import numpy as np
A = np.array(A)
for l in L:
    tmp0 = l[0]
    tmp1 = l[1]
    A_select = A[0:tmp0]
    A_len = bisect_left(A_select, tmp1)
    A[0:A_len] = tmp1
    A = np.sort(A)
    
    
print(sum(A))

### FIXED CODE ###

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

D = {}
for i in range(M):
    b,c = map(int, input().split())
    if c in D:
        D[c] += b
    else:
        D[c] = b
        
for a in A:
    if a in D:
        D[a] += 1
    else:
        D[a] = 1
        
D_sort = sorted(D.items(), reverse=True)
check = 0
ans = 0
for d in D_sort:
    check += d[1]
    if check <= N:
        ans += d[0] * d[1]
    else:
        ans += d[0] * (d[1] - (check - N))
        break
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [[c]*b for b, c in [map(int, input().split()) for _ in range(M)]]

R=sum(BC,[])
T=sorted(A+R,reverse=True)
print(sum(T[:len(A)]))



### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

A.sort(reverse=True)
BC.sort(key=lambda x:x[1],reverse=True)

R=[]
n=0
for i in range(M):
    R.extend([BC[i][1]]*BC[i][0])
    n = n + BC[i][0]
    if n >= N:
        break

R=sorted(A+R, reverse=True)[:N]
print(sum(R))
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))

h.sort(reverse=True)

cnt = 0

for i in range(k):
  h.pop(0)
  if not h:
    break
  
for i in h:
  cnt += i

print(cnt)

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))

h.sort()

cnt = 0

for i in range(k):
  h.pop()
  if not h:
    break
  
for i in h:
  cnt += i

print(cnt)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < n:
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            maxHeapify(A, largest)
def insert(S, k):
    global n
    S[n] = k
    n += 1
    i = n - 1
    p = (i - 1) // 2
    while i > 0 and S[i] > S[p]:
        S[i], S[p] = S[p], S[i]
        i = p
        p = (i - 1) // 2
def extractMax(S):
    global n
    if n == 1:
        n -= 1
        return S[0]
    ans = S[0]
    n -= 1
    S[0] = S[n]
    maxHeapify(S, 0)
    return ans
A = [0] * 2000000
n = 0
while True:
    s = readline()
    if s[2] == "d":
        break
    elif s[2] == "t":
        print(extractMax(A))
    else:
        insert(A, int(s[7:]))



### FIXED CODE ###

import sys
from heapq import heapify, heappush, heappop
hq = []
S = []
for s in sys.stdin:
    if s[2] == "s":
        heappush(hq, -int(s[7:]))
    elif s[2] == "t":
        S.append(-heappop(hq))
    else:
        break
print("\n".join(map(str, S)))
### BUGGY CODE ###

import collections
s = input()
t = input()
if not set(t).issubset(set(s)): print(-1)
else:
    d = collections.defaultdict(list)
    for i, letter in enumerate(s):
        d[letter].append(i+1)
    prev = 0
    cnt = 0
    for target in t:
        for num in d[target]:
            if num > prev:
                prev = num
                break
        else:
            cnt += 1
            prev = d[target][0]
    print(cnt * len(s) + prev)

### FIXED CODE ###

import collections
import bisect
s = input()
t = input()
if not set(t).issubset(set(s)): print(-1)
else:
    d = collections.defaultdict(list)
    for i, letter in enumerate(s):
        d[letter].append(i+1)
    prev = 0
    cnt = 0
    for target in t:
        li = d[target]
        idx = bisect.bisect_left(li, prev+1)
        if idx == len(li):
            cnt += 1
            prev = li[0]
        else:
            prev = li[idx]
    print(cnt * len(s) + prev)
### BUGGY CODE ###

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

### FIXED CODE ###

import math
n=int(input())
ans=int(0)
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            g=math.gcd(i,j)
            ans+=math.gcd(g,k)
print(ans)
### BUGGY CODE ###

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

A_set = list(set(A))
len_A_set = len(A_set)

# i = 0
# ct = 0
# while True:
#     if ct >= len_A_set - K:
#         break
#     min = 10000000
#     for i in A_set:
#         if A.count(i) < min:
#             min = A.count(i)
#     ct += min
# 
# print(ct)



A_count =[]
for i in range(len_A_set):
    A_count.append(A.count(A_set[i]))

ans=0
for i in range(len_A_set-K):
    ans += min(A_count)
    A_count.pop(A_count.index(min(A_count)))

print(ans)


### FIXED CODE ###

from collections import Counter
N, K=list(map(int, input().split()))
A=list(map(int, input().split()))

X=Counter(A)
X2 = sorted(X.items(), key=lambda x:x[1])
ans=0
for i in range(len(X2)-K):
    ans+=X2[i][1]
print(ans)
### BUGGY CODE ###

N = int(input())
d = list(map(int, input().split()))
cnt = 0
maxd = max(d)
mind = min(d)
for K in range(mind, maxd+1):
  if len([i for i in d if i >= K]) == len([i for i in d if i < K]): cnt += 1
print(cnt)
  

### FIXED CODE ###

N = int(input())
d = list(map(int, input().split()))
sor_d = sorted(d)
print(sor_d[int(N*0.5)]-sor_d[int(N*0.5)-1])
### BUGGY CODE ###

import heapq
import sys
sys.setrecursionlimit(10 ** 7)

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]
		self.count = 0

#	def find(self, x):
#		while self.table[x] >= 0:
#			x = self.table[x]
#		return x

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

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1

			self.count += 1
			return True
		return False

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

vx = sorted(x, key=lambda x: x[1])
vy = sorted(y, key=lambda x: x[1])

edges = []
uf = UnionFind(n)

for i in range(n - 1):
	if vx[i][1] == vx[i + 1][1]:
		uf.union(vx[i][0], vx[i + 1][0])
	else:
		heapq.heappush(edges, (vx[i + 1][1] - vx[i][1], vx[i][0], vx[i + 1][0]))

	if vy[i][1] == vy[i + 1][1]:
		uf.union(vy[i][0], vy[i + 1][0])
	else:
		heapq.heappush(edges, (vy[i + 1][1] - vy[i][1], vy[i][0], vy[i + 1][0]))


#edges = sorted(edges, key=lambda x: x[2], reverse=True)
#print(edges)

ans = 0

while edges != []:
	e = heapq.heappop(edges)
	if uf.union(e[1], e[2]):
		ans += e[0]
	if uf.count == n - 1:
		break

print(ans)


### FIXED CODE ###

import heapq
import sys
sys.setrecursionlimit(10 ** 7)

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]
		self.count = 0

#	def find(self, x):
#		while self.table[x] >= 0:
#			x = self.table[x]
#		return x

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

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1

			self.count += 1
			return True
		return False

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

vx = sorted(x, key=lambda x: x[1])
vy = sorted(y, key=lambda x: x[1])

edges = []
uf = UnionFind(n)

for i in range(n - 1):
	if vx[i][1] == vx[i + 1][1]:
		uf.union(vx[i][0], vx[i + 1][0])
	else:
		heapq.heappush(edges, (vx[i + 1][1] - vx[i][1], vx[i][0], vx[i + 1][0]))

	if vy[i][1] == vy[i + 1][1]:
		uf.union(vy[i][0], vy[i + 1][0])
	else:
		heapq.heappush(edges, (vy[i + 1][1] - vy[i][1], vy[i][0], vy[i + 1][0]))


#edges = sorted(edges, key=lambda x: x[2], reverse=True)
#print(edges)

ans = 0

while edges != []:
	e = heapq.heappop(edges)
	if uf.union(e[1], e[2]):
		ans += e[0]
	if uf.count == n - 1:
		break

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

s=input()

ans=0
while "ABC" in s:
    ans+=len(s.split("ABC"))-1
    s=s.replace("ABC", "BCA")

print(ans)

### FIXED CODE ###

s = input()
n = len(s)
s += "???"

i = 0
ans = 0

while i < n:
    abc = []
    if s[i] == "A":
        i += 1
        abc.append(0)
        while True:
            if s[i] == "A":
                i += 1
                abc.append(0)
            elif s[i:i+2] == "BC":
                i += 2
                ans += len(abc)
            else:
                break
    i += 1

print(ans)