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

from collections import deque

INF = 10**12

H, W = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3)
        for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
maze = []

for _ in range(H):
    maze.append(list(input()))

q = deque()
d = [[INF] * W for i in range(H)]
d[sx][sy] = 0
q.append((sx, sy, 0))

while q:
    x, y, s = q.pop()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and d[nx][ny] > s:
            d[nx][ny] = s
            q.append((nx, ny, s))
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and d[nx][ny] > s+1:
            d[nx][ny] = s + 1
            q.append((nx, ny, s+1))

if d[gx][gy] == INF:
    print(-1)
else:
    print(d[gx][gy])


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

n = int(input())
ans = 0

def gcd(a,b):
    if a>b:
        p = a
        q = b
    else:
        p = b
        q = a
    d = q
    while p % q != 0:
        d = p % q
        p = q
        q = d
    return d


for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans += gcd(gcd(i,j),k)

print(ans)


### FIXED CODE ###

n = int(input())
ans = 0
 
def max(a,b):
    if a>b:
        return a
    else:
        return b
 
def min(a,b):
    if a<b:
        return a
    else:
        return b
 
def gcd(a,b):
    p = max(a,b)
    q = min(a,b)
    d = q
    while p % q != 0:
        d = p % q
        p = q
        q = d
    return d
 
 
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans += gcd(gcd(i,j),k)
 
print(ans)
### BUGGY CODE ###

n = int(input())
ans = 1 + n
if n % 2 == 0:
    max = int(n / 2 + 1)
else:
    max = int((n + 1) / 2)

for i in range (1, max):
    if n % i == 0 and i + n / i < ans:
        ans = i + n / i

print(int(ans - 2))


### FIXED CODE ###

import math
n = int(input())
ans = 1 + n

max = math.ceil(n**0.5)

for i in range (2, max+1):
    if n % i == 0 and i + n / i < ans:
        ans = i + n / i

print(int(ans - 2))
### BUGGY CODE ###

data = list(map(lambda x: int(x),input().split(" ")))

cardNum = []

for n in range(data[1]):
	cardNum.append(list(map(lambda x: int(x),input().split(" "))))

#print(cardNum)

card = [0]*(data[0]+1)

for n in range(data[1]):
	for m in range(cardNum[n][0],cardNum[n][1]+1):
		card[m] += 1

print(card.count(data[1]))

### FIXED CODE ###

data = list(map(lambda x: int(x),input().split(" ")))

cardNum = []

for n in range(data[1]):
	cardNum.append(list(map(lambda x: int(x),input().split(" "))))


card = [0]*(data[0])

check = [0,1000000]

for n in range(data[1]):
	if check[0] < cardNum[n][0]:
		check[0] = cardNum[n][0]
	if check[1] > cardNum[n][1]:
		check[1] = cardNum[n][1]

if check[1]-check[0] < 0:
	print(0)
else:
	print(check[1]-check[0]+1)
### BUGGY CODE ###

N = int(input())
ans = 0

for i in range(1, N + 1):
    for j in range(1, N - i + 1):
        if i * j >= N:
            break
        else:
            ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
 
for i in range(1, N + 1):
    for j in range(1, N - i + 1):
        if i * j >= N:
            break
        else:
            ans += 1
 
print(ans)
### BUGGY CODE ###

h, w = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
a = [list(map(int, input().split())) for _ in range(h)]

mp2 = []
for i in range(10):
    for j in range(10):
        mp2.append([i, j, c[i][j]])
n_v = 10
from heapq import heappop, heappush

total = 0
for i in range(len(a)):
    _a = a[i]
    for j in range(len(_a)):
        if _a[j] != -1:
            start = _a[j]

            # コストテーブルの作成
            inf = float('inf')
            d = [inf for i in range(n_v)] # 最短距離
            d[start] = 0
            prev = [None] * n_v # 経路をたどるときに使う
            cost = dict() # コストテーブル
            for i, j, k in mp2:
                cost[i] = cost.get(i, []) + [(j, k)]

            q = [] # min-heap, (距離, 頂点)
            heappush(q, (d[start], start))
            while q:
                # print(q, d, prev)
                du, u = heappop(q) # 最短距離とその頂点
                if d[u] < du:
                    continue
                for v, weight in cost.get(u, []):
                    alt = du + weight
                    if d[v] > alt:
                        d[v] = alt
                        prev[v] = u
                        heappush(q, (alt, v))

            total += d[1]

print(total)


### FIXED CODE ###

h, w = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
a = [list(map(int, input().split())) for _ in range(h)]

from scipy.sparse.csgraph import floyd_warshall
cost=floyd_warshall(c)

total = 0
for i in range(h):
    for j in range(w):
        if a[i][j] != -1:
            start = a[i][j]
            d = cost[start][1]
            total += int(d)

print(total)
### BUGGY CODE ###

memo = {}

def gcd(a, b):
    if (a, b) in memo.keys():
        return memo[(a, b)]
    if b == 0:
        return a
    return gcd(b, a % b)

n = input()
a_list = map(int, raw_input().split())
max_g = 0
for exclude in xrange(n):
    g = a_list[0] if exclude > 0 else a_list[1]
    for i, a in enumerate(a_list):
        if i == 0 or i == exclude:
            continue
        g_new = gcd(g, a)
        if (g, a) not in memo:
            memo[(g, a)] = g_new
        g = g_new
        if g <= max_g:
            break
    if g > max_g:
        max_g = g
print(max_g)


### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    g = gcd(b, a % b)
    return g

n = input()
a_list = map(int, raw_input().split())

gs1 = [None] * n
gs1[0] = a_list[0]
for i in xrange(1, n):
    gs1[i] = gcd(gs1[i - 1], a_list[i])

gs2 = [None] * n
gs2[n - 1] = a_list[n - 1]
for i in reversed(xrange(n - 1)):
    gs2[i] = gcd(gs2[i + 1], a_list[i])

max_g = 0
for exclude in xrange(n):
    if exclude == 0:
        g = gs2[1]
    elif exclude == n - 1:
        g = gs1[n - 2]
    else:
        g = gcd(gs1[exclude - 1], gs2[exclude + 1])
    if g > max_g:
        max_g = g
print(max_g)
### BUGGY CODE ###

import math

for i in range(int(input()),100004):
  ri = math.floor(i**0.5) + 1
  for j in range(ri):
    for k in range(ri,i):
      if j*k == i:
        break
    else:
      continue
    break
  else:
    print(i)
    break

### FIXED CODE ###

for i in range(int(input()),100004):
  for j in range(2, i):
    if i % j == 0:
      break
  else:
    print(i)
    break
### BUGGY CODE ###

N = int(raw_input())
A = []
B = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))
  B.append(A[-1]+[])

for i in xrange(N):
  for j in xrange(i):
    for k in xrange(j):
      L1 = A[i][k] + A[k][j]
      L2 = A[k][j] + A[j][i]
      L3 = A[j][i] + A[i][k]
      if A[i][j] > L1 or A[k][i] > L2 or A[j][k] > L3:
        print -1
        exit()
      if A[i][j] == L1: B[i][j] = B[j][i] = 0
      if A[k][i] == L2: B[k][i] = B[i][k] = 0
      if A[j][k] == L3: B[j][k] = B[k][j] = 0

print sum(map(sum, B))/2

### FIXED CODE ###

N = int(raw_input())
A = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))
  A[n][n] = 1000000001

answer = 0
for i in range(N):
  Ai = A[i]
  for j in range(i):
    Aij = Ai[j]
    L = min(map(sum, zip(Ai, A[j])))
    if Aij < L:
      answer += Aij
    else:
      if Aij > L:
        print -1
        exit()
print answer
### BUGGY CODE ###

a,b,m=map(int, input().split())
rei=list(map(int, input().split())) 
den=list(map(int, input().split())) 
ans = []
cou=[list(map(int, input().split())) for i in range(m)]
[ans.append(rei[cou[i][0]-1]+den[cou[i][1]-1]-cou[i][2]) for i in range(m)]
[[ans.append(rei[j]+den[i]) for i in range(b)] for j in range(a)]
print(min(ans))

### FIXED CODE ###

m=list(map(int, input().split()))
rei=list(map(int, input().split())) 
den=list(map(int, input().split())) 
cou = [0] * m[2]
ans = []
for i in range(m[2]):
	cou[i]=list(map(int, input().split()))
	ans.append(rei[cou[i][0]-1]+den[cou[i][1]-1]-cou[i][2])

ans.append(min(rei)+min(den))
print(min(ans))
### BUGGY CODE ###

N=int(input())
S = []
for i in range(N):
    s = input()
    if s in S:
        continue
    S.append(s)

print(len(S))

### FIXED CODE ###

N=int(input())
S = []
for i in range(N):
    s = input()
    S.append(s)

print(len(list(set(S))))
### BUGGY CODE ###

S = input()
Q = int(input())
Query = [list(map(str,input().split())) for _ in range(Q)]
from collections import deque 
flag = True
f = ""
l = ""
#print(Query)
for i in Query:
    if i[0]=="1":
        if flag:
            flag = False
        else:
            flag = True
    else:
        if (flag==True and i[1]=="1") or (flag==False and i[1]=="2"):
            f += i[2] 
        elif (flag==True and i[1]=="2") or (flag==False and i[1]=="1"):
            l += i[2]
S = f[::-1]+S+l
if flag:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

S = input()
Q = int(input())
Query = [list(map(str,input().split())) for _ in range(Q)]
from collections import deque 
flag = True
f = ""
l = ""
#print(Query)
for i in Query:
    if i[0]=="1":
        if flag:
            flag = False
        else:
            flag = True
    else:
        if (flag==True and i[1]=="1") or (flag==False and i[1]=="2"):
            f += i[2] 
        elif (flag==True and i[1]=="2") or (flag==False and i[1]=="1"):
            l += i[2]
S = f[::-1]+S+l
if flag:
    print(S)
else:
    print(S[::-1])
### BUGGY CODE ###

N = int(input())
l = list(map(int, input().split()))
max_gcd = 1

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def gcd_list(l):
    max_gcd = l[0]
    for el in l[1:]:
        max_gcd = gcd(max_gcd,el)
    return max_gcd


for i in range(N):
    max_gcd = max(max_gcd, gcd_list(l[:i]+l[i+1:]))

print(max_gcd)


### FIXED CODE ###

N = int(input())
l = list(map(int, input().split()))
l_gcd = [None] * N
l_gcd[0] = l[0]


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


for i in range(1, N):
    l_gcd[i] = gcd(l_gcd[i-1], l[i])

r_gcd = [None] * N
r_gcd[-1] = l[-1]

for i in range(2, N+1):
    r_gcd[-i] = gcd(r_gcd[-i+1], l[-i])

max_gcd = max(l_gcd[-2], r_gcd[1])

for i in range(1, N-1):
    max_gcd = max(max_gcd, gcd(l_gcd[i-1], r_gcd[i+1]))

print(max_gcd)
### BUGGY CODE ###

import math
A, B, N = [int(n) for n in input().split()]

max = 0
for x in range(N+1):
    # val = A * ((x / B) % 1) - ((A*x/B) % 1)
    val = math.floor(A*x/B) - A*math.floor(x/B)
    if val > max:
        max = val
print(int(max))

### FIXED CODE ###

A, B, N = [int(n) for n in input().split()]

print(int(A*min(N,B-1)/B))
### BUGGY CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-

''' ????????????????????£????????\??? '''


class PQueue(object):
    """ Priority Queue """

    def __init__(self):
        self.pqueue = []

    def insert(self, x):
        self.pqueue.append(x)

    def extractMax(self):
        max_value = max(self.pqueue)
        self.pqueue.pop(self.pqueue.index(max_value))
        return max_value


if __name__ == '__main__':

    pqueue = PQueue()
    result = []

    line = input()
    while line != 'end':
        if line.split()[0] == 'insert':
            pqueue.insert(int(line.split()[1]))
        elif line.split()[0] == 'extract':
            result.append(pqueue.extractMax())
        line = input()

    for i in range(len(result)):
        print(result[i])

### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-

''' ????????????????????£????????\??? '''

import heapq


class PQueue(object):
    """ Priority Queue """

    def __init__(self):
        self.pqueue = []

    def insert(self, x):
        # self.pqueue.append(x)
        heapq.heappush(self.pqueue, -x)

    def extractMax(self):
        # return self.pqueue.pop(self.pqueue.index(max(self.pqueue)))
        return -heapq.heappop(self.pqueue)


if __name__ == '__main__':

    pqueue = PQueue()
    result = []

    while True:
        line = input()
        if line == 'end':
            break

        if line.split()[0] == 'insert':
            pqueue.insert(int(line.split()[1]))
        elif line.split()[0] == 'extract':
            result.append(pqueue.extractMax())

    for i in range(len(result)):
        print(result[i])
### BUGGY CODE ###

import itertools
n=int(input())
A=list(map(int,input().split()))
x=0
for i in range(n-1):
  for j in range(i+1,n):
    x+=A[i]*A[j]%(10**9+7)
print(x%(10**9+7))

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
sumA=sum(A)
x=0
for i in range(n-1):
  sumA-=A[i]
  x+=A[i]*sumA
print(x%(10**9+7))
### BUGGY CODE ###

class Puzzle():
  def __init__(self, mat, h,w,k):
    self.mat = mat
    self.h = h
    self.w = w
    self.k = k
    self.score = 0

  def calc(self, t):
    tmp_score = 0

    # print("before")
    # for m in self.mat:
    #   print(m)

    for i in range(self.h):
      for j in range(self.w):
        if self.mat[i][j] > 0:
          for k in range(self.w, -1, -1):
            # if k - j < self.k: break
            if k-j >= self.k:
              s = set(self.mat[i][j:k])
              if len(s) == 1 and -1 not in s:
                tmp_score += list(s)[0] * (k-j)
                for l in range(j, k):
                  self.mat[i][l] = -1
            else:
              break

    # print("calced")
    # for m in self.mat:
    #   print(m)

    if tmp_score == 0:
      return False
    else:
      self.score += pow(2, t) * tmp_score
      if self.score == 642: import pdb; pdb.set_trace()
      return True

  def flatten(self):
    pivot_mat = []
    for i in range(self.w):
      row = []
      for j in range(self.h):
        if self.mat[j][i] != -1:
          row.append(self.mat[j][i])

      short = self.h - len(row)
      if short > 0:
        row.reverse()
        for k in range(short):
          row.append(-1)
        row.reverse()
      
      pivot_mat.append(row)

    mat = [ [-1]*self.w for i in range(self.h) ]
    for i in range(self.h):
      for j in range(self.w):
        mat[i][j] = pivot_mat[j][i]

    self.mat = mat

h,w,k = map(int,input().split())
mat = []
for _ in range(h):
  mat.append([int(e) for e in list(input())])

res = 0
for i in range(h):
  for j in range(w):
    old = mat[i][j]
    mat[i][j] = -1
    puzzle = Puzzle(mat,h,w,k)
    puzzle.flatten()
    time = 0
    while True:
      if puzzle.calc(time):
        puzzle.flatten()
        time += 1
      else:
        break
    res = max(res, puzzle.score)
    mat[i][j] = old

print(res)


### FIXED CODE ###

from itertools import groupby

def calc(time):
  t = 0
  for i in range(h):
    gr = groupby(g[i])
    lst = []
    p = 0
    for key,it in gr:
      j = len(list(it))
      lst.append([p,key,j])
      p += j
    for j in range(len(lst)):
      if lst[j][1] == -1:
        continue
      if lst[j][2] >= K:
        t += (2**time)*lst[j][1]*lst[j][2]
        for k in range(lst[j][0],lst[j][0]+lst[j][2]):
          g[i][k] = 0

  return t

def flatten():
  for j in range(w):
    lst = []
    for i in range(h-1, -1, -1):
      if g[i][j] > 0:
        lst.append(g[i][j])

    lst += [-1] * (h - len(lst))

    for i in range(h-1, -1, -1):
      g[i][j] = lst[h-i-1]

h,w,K = map(int,input().split())
mat = [ [int(e) for e in list(input())] for _ in range(h) ]

res = 0
for i in range(h):
  for j in range(w):
    score = 0
    g = [ [ mat[n][m] for m in range(w) ] for n in range(h) ]
    g[i][j] = -1
    time = 0
    flatten()
    while True:
      s = calc(time)
      if s==0: break
      score += s
      flatten()
      time += 1
    res = max(res, score)

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

import math
n, k = map(int, input().strip().split())
A = list(map(int, input().strip().split()))

for _ in range(k):
    start=[0]*n
    end=[0]*n
    
    for i in range(n):
        start[max(0,i-A[i])]+=1
        end[min(n-1,i+A[i])]+=1
    # update ans
    cnt=0
    for i in range(n):
        cnt+=start[i]
        A[i]=cnt
        cnt-=end[i]
    if A[0]==n:
        break
print(*A)

### FIXED CODE ###

import sys
from itertools import accumulate
input=sys.stdin.buffer.readline

def main():
    n, k = map(int, input().split())
    A = [*map(int, input().split())]
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            if i>v:
            # b[max(0,i-v)]+=1
                b[i-v]+=1
            else:
                b[0]+=1
            j=i-~v
            # if i+v+1<n:
            #     b[i+v+1]-=1
            if j<n:
                b[j]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

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

n, q = map(int, input().split())
s = input()
l, r = [0]*q, [0]*q
for i in range(q):
    l[i], r[i] = map(int, input().split())
for i in range(q):
    print(s[l[i]-1:r[i]].count("AC"))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
count = [0]*(n+1)
for i in range(1, n):
    count[i] += count[i-1]
    if s[i-1:i+1] == "AC":
      count[i] += 1
for i in range(q):
    l, r = map(int, input().split())
    print(count[r-1] - count[l-1])
### BUGGY CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
dp = [0] * n
dp[0] = 0
for i in range(1, n):
    dp[i] = min([dp[i - j] + abs(h[i] - h[i - j]) for j in range(1, min(i, k) + 1)])
print(dp[n - 1])


### FIXED CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
dp = [0] * n
dp[0] = 0
for i in range(1, n):
    dp[i] = min([dp[i - j] + abs(h[i] - h[i - j]) for j in range(1, min(i, k) + 1)])
print(dp[n - 1])
### BUGGY CODE ###

from collections import deque
import heapq
import sys
input = sys.stdin.readline

f=lambda:map(int,input().split())
V,E,L=f()
G=[[] for _ in [0]*(V+1)]
# G=[]

for _ in range(E):
    s,t,d=f()
    if d<=L:
        G[s].append((t,d))
        G[t].append((s,d))

INF=V+5

res=[[(INF,0)]*(V+1) for _ in  [0]*(V+1)]

for start in range(1,V+1):
    q=[((0,0),start)]
    while q:
        c,town=heapq.heappop(q)
        if c<res[start][town]:
            res[start][town]=c
        else:
            continue
        h,cost=c
        for next_town,d in G[town]:
            D=cost+d
            if D<=L and (h,D)<res[start][next_town]:
                heapq.heappush(q,((h,D),next_town))
            elif D>L and (1+h,d)<res[start][next_town]:
                heapq.heappush(q,((1+h,d),next_town))

Q=int(input())
for _ in [0]*Q:
    s,t=f()
    r=res[s][t][0]
    print(r if r<INF else -1)

### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

f=lambda:map(int,input().split())
N,M,L=f()
G=[[0]*N for _ in [0]*N]
for _ in [0]*M:
    a,b,c=f()
    G[a-1][b-1]=c
    G[b-1][a-1]=c
    
csr=csr_matrix(G)

D=floyd_warshall(csr)
INF=float('inf')
G=[[INF]*N for _ in [0]*N]
for i in range(N):
    for j in range(N):
        if i!=j and D[i][j]<=L:
            G[i][j]=1
            G[j][i]=1
csr=csr_matrix(G)
res=floyd_warshall(csr)
Q=int(input())
for _ in [0]*Q:
    s,t=f()
    r=res[s-1][t-1]
    print(int(r-1) if r<INF else -1)
### BUGGY CODE ###

# ABC065D

import sys
input=sys.stdin.readline
import heapq

class UnionFind:
    def __init__(self, n):
        self.p=[-1]*n
        self.size=[1]*n
    def root(self, x):
        st=set()
        while(self.p[x]>=0):
            st.add(x)
            x=self.p[x]
        for y in st:
            self.p[y]=x
        return x
    def find(self, x, y):
        return self.root(x)==self.root(y)
    def union(self, x, y):
        r1=self.root(x)
        r2=self.root(y)
        if r1==r2:
            return
        p1=self.p[r1]
        p2=self.p[r2]
        if p1<=p2:
            self.p[r2]=r1
            self.size[r1]+=self.size[r2]
            if p1==p2:
                self.p[r1]-=1
        else:
            self.p[r1]=r2
            self.size[r2]+=self.size[r1]

def main():
    N=int(input())
    r=[tuple(map(int,input().split())) for i in range(N)]
    pq=[]
    for i in range(N):
        for j in range(i+1, N):
            d=min(abs(r[i][0]-r[j][0]), abs(r[i][1]-r[j][1]))
            heapq.heappush(pq,(d,i,j))
    uft=UnionFind(N)
    ans=0
    while(uft.size[uft.root(0)]<N):
        e=heapq.heappop(pq)
        if not(uft.find(e[1],e[2])):
            ans+=e[0]
            uft.union(e[1],e[2])
    print(ans)
    
    
if __name__=="__main__":
    main()


### FIXED CODE ###

# ABC065D

import sys
input=sys.stdin.readline
import heapq

class UnionFind:
    def __init__(self, n):
        self.p=[-1]*n
        self.size=[1]*n
    def root(self, x):
        st=set()
        while(self.p[x]>=0):
            st.add(x)
            x=self.p[x]
        for y in st:
            self.p[y]=x
        return x
    def find(self, x, y):
        return self.root(x)==self.root(y)
    def union(self, x, y):
        r1=self.root(x)
        r2=self.root(y)
        if r1==r2:
            return
        p1=self.p[r1]
        p2=self.p[r2]
        if p1<=p2:
            self.p[r2]=r1
            self.size[r1]+=self.size[r2]
            if p1==p2:
                self.p[r1]-=1
        else:
            self.p[r1]=r2
            self.size[r2]+=self.size[r1]

def main():
    N=int(input())
    r=[tuple([i]+list(map(int,input().split()))) for i in range(N)]
    rx=sorted(r,key=lambda x:x[1])
    ry=sorted(r,key=lambda x:x[2])
    pq=[]
    for i in range(1,N):
        dx=abs(rx[i][1]-rx[i-1][1])
        heapq.heappush(pq,(dx,rx[i][0],rx[i-1][0]))
        dy=abs(ry[i][2]-ry[i-1][2])
        heapq.heappush(pq,(dy,ry[i][0],ry[i-1][0]))
    uft=UnionFind(N)
    ans=0
    while(uft.size[uft.root(0)]<N):
        e=heapq.heappop(pq)
        if not(uft.find(e[1],e[2])):
            ans+=e[0]
            uft.union(e[1],e[2])
    print(ans)
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

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

ans = 0
for x in range(1, n + 1):
    ax = a * x
    ans = max(ans, ax // b - a * (x // b))
print(ans)

### FIXED CODE ###

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

if n < b - 1:
    ans = (a * (n % b)) // b
else:
    ans = (a * ((b - 1) % b)) // b
print(ans)
### BUGGY CODE ###

MOD = int(1e9 + 7)
n = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(62):
    cnt = 0
    for a in A:
        if a & 1<<i:
            cnt += 1
    ans += (1<<i % MOD) * cnt % MOD * (n - cnt) % MOD
print(ans % MOD)


### FIXED CODE ###

MOD = int(1e9 + 7)
n = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(62):
    cnt = 0
    for a in A:
        if a & 1<<i:
            cnt += 1
    ans += (1<<i % MOD) * cnt % MOD * (n - cnt) % MOD
print(ans % MOD)