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

def main():
    h, n = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    dp = [[float("inf")]*(2*10**4+1) for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        p, a, b = i+1, arr[i][0], arr[i][1]
        for j in range(2*10**4+1):
            if j < a:
                dp[p][j] = dp[p-1][j]
            else:
                if dp[p][j-a] + b < dp[p-1][j]:
                    dp[p][j] = dp[p][j-a] + b
                else:
                    dp[p][j] = dp[p-1][j]
    print(min(dp[-1][h:2*10**4+1]))

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    h, n = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    dp = [[float("inf")]*(2*10**4+1) for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        p, a, b = i+1, arr[i][0], arr[i][1]
        for j in range(2*10**4+1):
            if j < a:
                dp[p][j] = dp[p-1][j]
            else:
                if dp[p][j-a] + b < dp[p-1][j]:
                    dp[p][j] = dp[p][j-a] + b
                else:
                    dp[p][j] = dp[p-1][j]
    print(min(dp[-1][h:2*10**4+1]))

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

from sys import stdin
inf = 10**10
h,w = map(int,stdin.readline().rstrip().split())
li = [stdin.readline().rstrip() for _ in range(h)]
visited = [[0 for i in range(w)]for j in range(h)]
q = []
for i in range(h):
    for j in range(w):
        if li[i][j] == ".":
            continue
        q.append((i,j))
        visited[i][j] = 1
dx = [1,0,-1,0]
dy = [0,1,0,-1]
ans = -1
while q:
    qq = []
    ans += 1
    for y,x in q:
        for i,j in zip(dy,dx):
            ny,nx = i+y,j+x
            if ny < 0 or ny >= h or nx < 0 or nx >= w:
                continue
            elif li[ny][nx] == "#":
                continue
            elif visited[ny][nx] == 0:
                visited[ny][nx] = 1
                qq.append((ny,nx))
    q = qq
print(ans)

### FIXED CODE ###

from sys import stdin
inf = 10**10
h,w = map(int,stdin.readline().rstrip().split())
li = [stdin.readline().rstrip() for _ in range(h)]
visited = [[0 for i in range(w)]for j in range(h)]
q = []
for i in range(h):
    for j in range(w):
        if li[i][j] == ".":
            continue
        q.append((i,j))
        visited[i][j] = 1
dx = [1,0,-1,0]
dy = [0,1,0,-1]
ans = -1
while q:
    qq = []
    ans += 1
    for y,x in q:
        for i,j in zip(dy,dx):
            ny,nx = i+y,j+x
            if ny < 0 or ny >= h or nx < 0 or nx >= w:
                continue
            elif li[ny][nx] == "#":
                continue
            elif visited[ny][nx] == 0:
                visited[ny][nx] = 1
                qq.append((ny,nx))
    q = qq
print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(x) for x in input().split()]

def func1(a):
    a.sort()
    cnt=0
    chker={}
    for i in a:
        candiv=False
        if a.count(i)>1:
            candiv=True
        else:
            for j2 in chker:
                j=int(j2)
                if j*2>i:
                    break
                if i%j==0:
                    candiv=True
                    break
        if candiv==False:
            cnt+=1
        chker[str(i)]=1
    print(cnt)
func1(a)


### FIXED CODE ###

n=int(input())
a=[int(x) for x in input().split()]
a.sort()
max=a[-1]
dp=[False for _ in range(max+1)]

for i in a:
    if dp[i]==False:
        j=1
        while 1:
            j+=1
            if i*j>max:
                break
            dp[i*j]=True
for i in range(len(a)-1):
    if a[i]==a[i+1]:
        dp[a[i]]=True
cnt=0
for i in a:
    if dp[i]==False:
        cnt+=1

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

def main():
  _range = range
  h, w = map(int, input().split())
  s = [input() + '#' for _ in _range(h)]
  s.append('#' * (w + 1))
  t = [[-1] * w for _ in _range(h + 1)]
  tstart = [-1] * (w + 1)
  for i in _range(h + 1):
    ystart = -1
    si = s[i]
    ti = t[i]
    for j in _range(w + 1):
      if si[j] == '#':
        if ystart != -1:
          n = j - ystart
          for k in _range(ystart, j):
            ti[k] += n
          ystart = -1
        if tstart[j] != -1:
          n = i - tstart[j]
          for k in _range(tstart[j], i):
            t[k][j] += n
          tstart[j] = -1
      else:
        if ystart == -1:
          ystart = j
        if tstart[j] == -1:
          tstart[j] = i
  print(max(map(max, t)))
main()

### FIXED CODE ###

h, w = map(int, input().split())
s = [input() + '#' for _ in range(h)]
s.append('#' * w)

yoko = [[0] * w for _ in range(h)]
for i in range(h):
  if s[i][0] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, w + 1):
    if s[i][j] == '#':
      if start != -1:
        for k in range(start, j):
          yoko[i][k] = j - start
        start = -1
    else:
      if start == -1:
        start = j

tate = [[0] * w for _ in range(h)]
for i in range(w):
  if s[0][i] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, h + 1):
    if s[j][i] == '#':
      if start != -1:
        for k in range(start, j):
          tate[k][i] = j - start
        start = -1
    else:
      if start == -1:
        start = j
result = 0
for i in range(h):
  for j in range(w):
    t = yoko[i][j] + tate[i][j] - 1
    if t > result:
      result = t

print(result)
### BUGGY CODE ###

K,S=map(int,input().split())
count =0
for i in range(K+1):
  for j in range(K+1):
    for k in range(K+1):
      if i+j+k==S:
        count +=1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k + 1):
    for y in range(k + 1):
        z = s - x - y
        if 0 <= z <= k:
            count += 1
print(count)
### BUGGY CODE ###

import heapq

class PriorytyQueue(object):

    def __init__(self, arr, target='min'):
        self.arr = arr
        self.target = target
        self._heapify()
    
    def _heapify(self):
        if self.target == 'max':
            self.arr = list(map(lambda x:x*(-1), self.arr))
        heapq.heapify(self.arr)
    
    def push(self, x):
        if self.target == 'max':
            x *= -1
        heapq.heappush(self.arr, x)

    def pop(self):
        res = heapq.heappop(self.arr)
        if self.target == 'max':
            return res*(-1)
        else:
            return res
    
    def get_arr(self):
        if self.target == 'max':
            return list(map(lambda x:x*(-1), self.arr))
        else:
            return self.arr
    
    def is_empty(self):
        return len(self.arr) == 0

# ------------------------------------------ #
from collections import defaultdict

N, M = map(int, input().split())
jobs = defaultdict(list)
for i in range(N):
    a, b = map(int, input().split())
    jobs[a].append(b)

if __name__ == "__main__":

    ans = 0
    pq = PriorytyQueue([], target='max')
    # d: 残りの日数(d日以上の仕事なら可能)
    for d in range(1, M+1):
        moneys = jobs[d]
        for money in moneys:
            pq.push(money)
        if len(pq.get_arr()) != 0:
            ans += pq.pop()
    print(ans)

### FIXED CODE ###

import heapq
from collections import defaultdict

class PriorytyQueue(object):

    def __init__(self, arr, target='min'):
        self.arr = arr
        self.target = target
        self._heapify()
    
    def _heapify(self):
        if self.target == 'max':
            self.arr = list(map(lambda x:x*(-1), self.arr))
        heapq.heapify(self.arr)
    
    def push(self, x):
        if self.target == 'max':
            x *= -1
        heapq.heappush(self.arr, x)

    def pop(self):
        res = heapq.heappop(self.arr)
        if self.target == 'max':
            return res*(-1)
        else:
            return res
    
    def get_arr(self):
        if self.target == 'max':
            return list(map(lambda x:x*(-1), self.arr))
        else:
            return self.arr
    
    def is_empty(self):
        return len(self.arr) == 0

n, m = map(int, input().split())
jobs = defaultdict(list)
for _ in range(n):
    a, b = map(int, input().split())
    if a > m:
        continue
    jobs[a].append(b)

res = 0
candidates = PriorytyQueue(arr=[],
                           target='max')
for d in range(1, m+1):
    if d in jobs.keys():
        for m in jobs[d]:
            candidates.push(m)
    if not(candidates.is_empty()):
        res += candidates.pop()
print(res)
### BUGGY CODE ###

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

P = 998244353

N, A, B, K = reads()

fact = [1]
for i in range(1, N+1):
  fact.append(fact[i-1] * i % P)

def egcd(a, b):
  if b == 0:
    return a, 1, 0
  else:
    q, r = divmod(a, b)
    g, x, y = egcd(b, r)
    return g, y, x - q * y

def inv(n):
  g, x, _ = egcd(n, P)
  # assert g == 1
  return x

def comb(n, k):
  # assert 0 <= k <= n
  return fact[n] * inv(fact[k]) * inv(fact[n-k]) % P

result = 0
for x in range(N+1):
  y, r = divmod(K - A * x, B)
  if r == 0 and 0 <= y <= N:
    result = result + comb(N, x) * comb(N, y) % P

print(result % P)

### FIXED CODE ###

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

P = 998244353

N, A, B, K = reads()

def inv(n):
  return pow(n, P-2, P)

fact = [1] * (N+1)
for i in range(1, N+1):
  fact[i] = fact[i-1] * i % P

invfact = [inv(fact[N])] * (N+1)
for i in range(N, 0, -1):
  invfact[i-1] = invfact[i] * i % P

def comb(n, k):
  # assert 0 <= k <= n
  return fact[n] * invfact[k] * invfact[n-k] % P

result = 0
for x in range(N+1):
  y, r = divmod(K - A * x, B)
  if r == 0 and 0 <= y <= N:
    result = result + comb(N, x) * comb(N, y) % P

print(result % P)
### BUGGY CODE ###

N, M = map(int, input().split())
A, B = [], []
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

class Rs():
    def __init__(self):
        self.Rs = []

    def append(self, R):
        self.Rs.append(R)

    def search(self):
        count = 1
        new_nodes, count = self._search(1, count)
        while count < N:
            _new_nodes = []
            for num in new_nodes:
                _new_node, count = self._search(num, count)
                _new_nodes.extend(_new_node)
            new_nodes = _new_nodes

        return [ self.Rs[i].fastest_room for i in range(1,len(self.Rs)) ]

    def _search(self, num, count):
        r = self.Rs[num-1]
        cons = r.connection
        new_nodes = []
        cons -= r.searched_from

        for con in cons:
            if len(self.Rs[con-1].searched_from) == 0:
                self.Rs[con-1].fastest_room = num
                self.Rs[con-1].searched_from.add(num)
                new_nodes.append(con)
                count += 1
            else:
                continue
        return new_nodes, count

class R():
    def __init__(self, num, connection):
        self.num        = num
        self.connection = connection
        self.searched_from = set([])
        self.fastest_room = None

r = Rs()
for i in range(N):
    cons = []
    for j, (a, b) in enumerate(zip(A, B)):
        if a == (i+1):
            cons.append(B[j])
        elif b == (i+1):
            cons.append(A[j])
    r.append(R(i+1, set(cons)))

l = r.search()
print("Yes")
for room in l:
    print(room)



### FIXED CODE ###

N, M = map(int, input().split())
A, B = [], []
graph = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    graph[a].append(b)
    graph[b].append(a)

class Rs():
    def __init__(self):
        self.Rs = []

    def append(self, R):
        self.Rs.append(R)

    def search(self):
        count = 1
        new_nodes, count = self._search(1, count)
        while count < N:
            _new_nodes = set()
            for num in new_nodes:
                _new_node, count = self._search(num, count)
                _new_nodes.update(_new_node)
            new_nodes = _new_nodes

        return [ self.Rs[i].fastest_room for i in range(1,len(self.Rs)) ]

    def _search(self, num, count):
        r = self.Rs[num-1]
        cons = r.connection
        new_nodes = set()
        cons -= r.searched_from

        for con in cons:
            if len(self.Rs[con-1].searched_from) == 0:
                self.Rs[con-1].fastest_room = num
                self.Rs[con-1].searched_from.add(num)
                new_nodes.add(con)
                count += 1
            else:
                continue
        return new_nodes, count

class R():
    def __init__(self, num, connection):
        self.num        = num
        self.connection = connection
        self.searched_from = set([])
        self.fastest_room = None

r = Rs()
for i in range(N):
    r.append(R(i+1, set(graph[i+1])))

l = r.search()
print("Yes")
for room in l:
    print(room)
### BUGGY CODE ###

import math
K = int(input())

ans = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            x = math.gcd(i, j)
            ans += math.gcd(x, k)
print(ans)

### FIXED CODE ###

import math
K = int(input())

ans = 0
a = 0
b = 0
c = 0
for i in range(1, K + 1):
    a += i

for i in range(1, K):
    for j in range(i + 1, K + 1):
        b += math.gcd(i, j) * 6

for i in range(1, K - 1):
    for j in range(i + 1, K):
        for k in range(j + 1, K + 1):
            x = math.gcd(i, j)
            c += math.gcd(x, k) * 6
ans = a + b + c
print(ans)
### BUGGY CODE ###

mod=10**9+7
n=int(input())
A=list(map(int,input().split()))
cnt=0
for i in range(n):
    for j in range(i):
        cnt +=A[i]^A[j]
        cnt %=mod
print(cnt)

### FIXED CODE ###

import numpy as np
mod=10**9+7
n=int(input())
A=np.array(list(map(int,input().split())))

ans=0

for i in range(60):
    cnt=np.count_nonzero(A&1)
    ans +=2**i*cnt*(n-cnt)
    A >>=1

print(ans%mod)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
ans=1

for a in A:
  ans *= a
  
if ans > 10**18:
  print('-1') 
else:
  print(ans)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
ans=1
if 0 in A:
  print('0')
else:
  for a in A:
    ans *= a
    if ans > 10**18:
      print('-1')
      exit()
  print(ans)
### BUGGY CODE ###

r, c, k = map(int, input().split())

dp = [[[0,0,0,0] for _j in range(c+1)] for _i in range(2)]
bord = [[0]*(c+1) for _i in range(r)]

for _i in range(k):
    _r, _c, _v = map(int, input().split())
    bord[_r-1][_c-1] = _v
            
for i in range(r):
    for j in range(c):
        dp[1][j][0] = max(dp[0][j])
        dp[1][j][1] = dp[1][j][0] + bord[i][j]
        for x in range(1, 4):
            dp[1][j][x] = max(
                dp[1][j][x],
                dp[1][j-1][x],
                dp[1][j-1][x-1]+bord[i][j],             
            )
    dp[0] = dp[1][::]

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

### FIXED CODE ###

r, c, k = map(int, input().split())

dp = [[[0,0,0,0] for _j in range(c+1)] for _i in range(2)]
bord = [[0]*(c+1) for _i in range(r)]

for _i in range(k):
    _r, _c, _v = map(int, input().split())
    bord[_r-1][_c-1] = _v
            
for i in range(r):
    for j in range(c):
        dp[1][j][0] = max(dp[0][j])
        dp[1][j][1] = max(
            dp[1][j][0] + bord[i][j],
            dp[1][j-1][1],
            dp[1][j-1][0]+bord[i][j]
        )

        dp[1][j][2] = max(
            dp[1][j-1][2],
            dp[1][j-1][1]+bord[i][j],             
        )
        dp[1][j][3] = max(
            dp[1][j-1][3],
            dp[1][j-1][2]+bord[i][j],             
        )

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

print(max(dp[1][c-1]))
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)


def main():
    K = int(input())
    ans = 0
    for i in range(1, K+1):
        for j in range(1, K+1):
            for k in range(1, K+1):
                ans += gcd(i, j, k)
    print(ans)
main()

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)


def main():
    K = int(input())
    ans = 0
    for i in range(1, K+1):
        for j in range(1, K+1):
            for k in range(1, K+1):
                ans += gcd(i, j, k)
    print(ans)
main()
### BUGGY CODE ###

S = str(input())
T = str(input())

s_box = []
t_box = []

for i in range(len(S)):
    s_box.append(S.count(S[i]))
    t_box.append(T.count(T[i]))
    if s_box[i] == t_box[i]:
        continue
    else:
        print('No')
        exit()
print('Yes')

### FIXED CODE ###

#ABC110 C String Transformation

S = input()
T = input()

StoT = {}
TtoS = {}

for s, t in zip(S, T):
    if s in StoT.keys():
        if StoT[s] != t:
            print('No')
            exit()
    elif t in TtoS.keys():
        if TtoS[t] != s:
            print('No')
            exit()
    else:
        StoT[s] = t
        TtoS[t] = s
        
print('Yes')
### BUGGY CODE ###

n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
ikeruheya = [[] for i in range(n)]
ans = [0]*(n+1)
check = [0]*n

for i in range(m):
    ikeruheya[a[i][0]-1].append(a[i][1])
    ikeruheya[a[i][1]-1].append(a[i][0])
    
next=[1]

while len(next) != 0:
    imaheya = next.pop(0)
    for j in range(len(ikeruheya[imaheya-1])):
        if check[ikeruheya[imaheya-1][j]-1]==0:
            ans[ikeruheya[imaheya-1][j]]= imaheya 
            check[ikeruheya[imaheya-1][j]-1] = 1
            next.append(ikeruheya[imaheya-1][j])
            
print("Yes")
for i in range(2, n+1):
    print(ans[i])

    
    
    

### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
a=[list(map(int, input().split())) for i in range(m)]
b=[[] for j in range(n)] 

michi=[-1]*(n)
michi[0]=0
heya=[]


for i in range(m):
    b[a[i][0]-1].append(a[i][1])
    b[a[i][1]-1].append(a[i][0])



heya.append(1)


while len(heya):
    now=heya.pop(0)-1
    
    for i in range(len(b[now])):
        if michi[b[now][i]-1] == -1:
            heya.append(b[now][i])
            michi[b[now][i]-1] = now+1
print("Yes")
for i in range(1,n):
    print(michi[i])
### BUGGY CODE ###

A, B, K = map(int, input().split())
num = A
while num <= B:
  if num <= A+K-1 or num >= B-K+1:
    print(num)
  num += 1
    


### FIXED CODE ###

A, B, K = map(int, input().split())

nums = []
for num in range(A, min(A+K, B+1)):
  nums.append(num)
for num in range(max(B-K+1, A), B+1):
  if not num in nums:
    nums.append(num)
nums.sort()
for num in nums:
  print(num)
### BUGGY CODE ###

from collections import deque

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

L.sort(reverse=True)

List = deque()
Sum = 0

for i in range(1, N - 1):
    for j in range(i + 1, N):
        List.append(L[i] + L[j])

for i in range(N - 2):
    for j in range(len(List)):
        if List[j] > L[i]:
            Sum += 1

    for j in range(N-2-i):
        List.popleft()

print(Sum)



### FIXED CODE ###

import bisect

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

Sum = 0
L.sort(reverse=False)

for i in reversed(range(2,N)):
    for j in reversed(range(1,i)):
        hoge = 0
        hoge = j - bisect.bisect(L, L[i] - L[j])
        if hoge < 0:
            hoge = 0
        Sum += hoge

print(Sum)
### BUGGY CODE ###

A,B=[int(_) for _ in input().split()]
def fxor(a,b):
    return a^b
import functools
print(functools.reduce(fxor,range(A,B+1)))


### FIXED CODE ###

A,B=[int(_) for _ in input().split()]
def fxor(a,b):
    return a^b

def fxorA2B(a,b,iD):
    def calcFD(g,b):
        return (g -1) //2 % 2 if b else g//2 % 2
    if a < b:
        if a == 2**iD :
            sB = bin(b)[2:][::-1]
            i2 = 2**iD -1
            bB = (b - i2)%2
            iC = 0
            for i in range(iD+1):
                iB = int(sB[i])
                if i == 0 and calcFD(b-i2,bB):
                    iC += 1
                elif iB and bB:
                    iC += 2**i
        else:
            a -= 1
            sA = bin(a)[2:][::-1]
            sB = bin(b)[2:][::-1]
            i2 = 2**iD -1
            bA = (a - i2)%2
            bB = (b - i2)%2
            iC = 0
            for i in range(iD+1):
                iA = int(sA[i])
                iB = int(sB[i])
                if i == 0 and calcFD(a-i2,bA) ^ calcFD(b-i2,bB):
                    iC += 1
                elif (iA and bA) ^ (iB and bB):
                    iC += 2**i
        return iC
    else:
        return a
def lenbin(X):
    return len(bin(X)) - 3
iA = lenbin(A)
iB = lenbin(B)
if iA == iB:
    print(fxorA2B(A,B,iA))
else:
    if iA == 0 :
        print(fxorA2B(2**iB,B,iB))
    else:
        print(fxorA2B(A,(2**(iA+1) - 1),iA)^fxorA2B(2**iB,B,iB))
### BUGGY CODE ###

import sys
read = sys.stdin.read

def main():
    # heapqをつかうプリム法
    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())
    xy = [tuple(map(int, input().split())) for _ in range(n)]
    edge = {e:[] for e in range(n)}
    for i1 in range(n):
        for i2 in range(i1 + 1):
            dis = min(abs(xy[i1][0] - xy[i2][0]), abs(xy[i1][1] - xy[i2][1]))
            edge[i1].append([dis, i2])
            edge[i2].append([dis, i1])
    r = prim_heap()
    print(r)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.read
from operator import itemgetter
from copy import deepcopy
from collections import deque
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]

    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def same(x, y):
        return find(x) == find(y)
    def size(x):
        return -par[find(x)]
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]
    def roots():
        return [i for i, x in enumerate(par) if x < 0]

    # input
    n = int(input())
    m = map(int, read().split())
    # inputされたノード座標のリストをｘ座標とｙ座標それぞれでソート。
    mm = zip(m, m)
    cnt = 0
    nodes = []
    nodes_a = nodes.append
    for a, b in mm:
        # nodes_a(x座標、y座標、ノード名) ※ノード名は0origin。union-findを使うため。
        nodes_a((a, b, cnt))
        cnt += 1
    nodes.sort(key=itemgetter(0))
    nodes_y = deepcopy(nodes)
    nodes_y.sort(key=itemgetter(1))
    # ノード座標リストからｘ軸とｙ軸それぞれで「隣接するノードをむすぶ辺」のリストをedgesに格納。
    edges = []
    for i1 in range(n - 1):
        # 辺のコスト、端のノード２つ
        edges.append((nodes[i1+1][0] - nodes[i1][0], nodes[i1][2], nodes[i1+1][2]))
        edges.append((nodes_y[i1+1][1] - nodes_y[i1][1], nodes_y[i1][2], nodes_y[i1+1][2]))
    # 「コストが小さい順」でソート
    edges.sort(key=itemgetter(0))
    # union-findをつかってクラスカル法をする。
    par = [-1] * n  # union-find用のデータ初期化
    edges = deque(edges)  # edgesを左から１つずつpopするのでdequeに変換。
    r = 0  # rに「森に加えた辺のコスト」を加算していく
    while edges:
        e = edges.popleft()
        if not same(e[1], e[2]):
            r += e[0]
            unite(e[1], e[2])
    print(r)

if __name__ == '__main__':
    main()