Harryxun/stf_run huggingface dataset:
import math
N = int(input())
input_list = [int(input())for _ in range(N)]

def lcm(x, y):
    return (x * y) // math.gcd(x, y)
  
initial_num = 1
for i in input_list:
    if lcm(initial_num, i) > initial_num:
        initial_num = lcm(initial_num, i)
        
print(initial_num)

### FIXED CODE ###

N = int(input())
input_list = [int(input())for _ in range(N)]

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
  
def lcm(x, y):
    return (x * y) // gcd(x, y)
  
initial_num = 1
for i in input_list:
    t = lcm(initial_num, i)
    if  t > initial_num:
        initial_num = t
        
print(initial_num)
import math
b = list(map(int,input().split()))
ans=0
check=0
i=0
A=0
B=0
C=b[1]
max = b[2]//b[1]
if max==0 or max==1:
    for i in range(b[2]+1):
        if b[2]-i <=0:
            break
        check = math.floor((b[0]*(b[2]-i))/b[1]) - b[0]*math.floor((b[2]-i)/b[1])
        if check > ans:
            ans=check

else:
    for i in range(1,max+1):
        A=b[1]-1
        
        check = math.floor((b[0]*A)/C) - b[0]*math.floor(A/C)
        if check > ans:
            ans=check
        b[1]+=b[1]
print(ans)

### FIXED CODE ###

import math
b = list(map(int,input().split()))
ans=0
check=0
if b[2]>b[1]-1:
    check = math.floor((b[0]*(b[1]-1))/b[1]) - b[0]*math.floor((b[1]-1)/b[1])
else:
    check = math.floor((b[0]*b[2])/b[1]) - b[0]*math.floor(b[2]/b[1])
if check>ans:
    ans=check
print(ans)
N, M, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
a = [0] * (N+1)
b = [0] * (M+1)
for i in range(N):
    a[i+1] = a[i] + A[i]
for i in range(M):
    b[i+1] = b[i] + B[i]
ans = 0
j = M
for i in range(N+1):
    tmp = K - a[i]
    if tmp < 0:
        break
    while b[j] > tmp:
        j -= 1
    ans = max(ans, i + j)
print(ans)

### FIXED CODE ###

N = int(input())
mul = [0] * (N+1)
for i in range(1, N+1):
    for j in range(i, N+1, i):
        mul[j] += 1
ans = 0
for i in range(1, N+1):
    ans += i * mul[i]
print(ans)
from collections import deque

H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(input())

ret = 0
for i in range(H):
    for j in range(W):
        s = S[i][j]
        queue = deque([(i,j,0)])
        footprint = [(i,j)]
        if s == '#':
            continue
        while True:
            x, y, d = queue.popleft()
            for p in [(x-1, y), (x, y-1), (x, y+1), (x+1, y)]:
                if p[0] >= 0 and p[0] < H and p[1] >=0 and p[1] < W and p not in footprint and S[p[0]][p[1]] != '#':
                        queue.append((p[0], p[1], d+1))
                        footprint.append(p)

            if len(queue) == 0:
                break
        if d > ret:
            ret = d

print(ret)

### FIXED CODE ###

print(chr(ord(input())+1))
from collections import deque
h, w = map(int, input().split())
cnt_b = 0
s = []
for i in range(h):
    si = input()
    cnt_b += si.count('#')
    s.append(si)

def bfs(i0, j0):
    INF = 1000
    search = deque([(i0, j0)])
    d = [[INF] * w for i in range(h)]
    d[i0][j0] = 1
    while search:
        i, j = search.popleft()
        if (i, j) == (h - 1, w - 1):
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < h and 0 <= nj < w and s[ni][nj] == '.' and d[ni][nj] == INF:
                search.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]
print(h*w - cnt_b - bfs(0, 0))

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
cnt_b = 0
s = []
for i in range(h):
    si = input()
    cnt_b += si.count('#')
    s.append(si)

def bfs(i0, j0):
    INF = 1000
    search = deque([(i0, j0)])
    d = [[INF] * w for i in range(h)]
    d[i0][j0] = 1
    while search:
        i, j = search.popleft()
        if (i, j) == (h - 1, w - 1):
            break
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < h and 0 <= nj < w and s[ni][nj] == '.' and d[ni][nj] == INF:
                search.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j] if d[h - 1][w - 1] != INF else 0 
solvable = bfs(0, 0)
print(h*w - cnt_b - solvable if solvable else -1)
n,m,r=map(int,input().split())
a,b=sorted([n-1,r-m*n])
A=1
for i in range(a):A*=i+1
B=A
for i in range(a,b):B*=i+1
C=B
for i in range(b,a+b):C*=i+1
print(int(C/B/A))


### FIXED CODE ###

n,m,r=map(int,input().split())
r-=m*n
if r<0:print(0)
else:
 d=1
 for i in range(r):d*=i+1
 u=1
 for i in range(r):u*=i+n
 print(u//d)
n = int(input())

a = list(map(int, input().split()))
if len(a)%2 !=0:
  a.append(0)
  
a.sort()
d = 0

for i in range(n/2):
  d += a[2i+1] - a[2i]
 
print(d)


### FIXED CODE ###

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

if n%2 != 0:
  a.append(0)
  n += 1
 
a.sort()
d = 0

for i in range(int(n/2)):
               d += a[2*i+1]-a[2*i]
           
print(d)
#!/usr/bin/env python3
from functools import reduce

mod = 10**9 + 7
n, k, *a = map(int, open(0).read().split())
a.sort(key=lambda x: abs(x))
ans = reduce(lambda a, b: (a * b) % mod, a[-k:])

c = a[-k:]
j = sum(i < 0 for i in c) % 2
if j:
    c = a[-k:]
    neg = [i for i in c if i < 0]
    pos = [i for i in c if i > 0]
    b = sorted(a[:n - k])
    if 0 >= b[-1] / neg[0] > b[0] / pos[0]:
        ans = ans // pos[0] * b[0] % mod
    elif b[-1] / neg[0] <= 0:
        ans = ans // neg[0] * b[-1] % mod
    else:
        ans = reduce(lambda a, b: (a * b) % mod, a[:k])
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
from functools import reduce

mod = 10**9 + 7
n, k, *a = map(int, open(0).read().split())
a.sort(key=lambda x: abs(x))
ans = reduce(lambda a, b: (a * b) % mod, a[-k:])

c = a[-k:]
j = sum(i < 0 for i in c) % 2
if j:
    c = a[-k:]
    neg = [i for i in c if i < 0]
    pos = [i for i in c if i > 0]
    b = sorted(a[:n - k])
    if b == []:
        print(ans)
        exit()
    if neg == []:
        if pos[0] * b[0] < 0:
            ans = ans * pow(pos[0], mod - 2, mod) * b[0] % mod
        else:
            ans = reduce(lambda a, b: (a * b) % mod, a[:k])
    elif pos == []:
        if neg[0] * b[-1] < 0:
            ans = ans * pow(neg[0], mod - 2, mod) * b[-1] % mod
        else:
            ans = reduce(lambda a, b: (a * b) % mod, a[:k])
    elif pos[0] * b[-1] < neg[0] * b[0] and pos[0] * b[0] < 0:
        ans = ans * pow(pos[0], mod - 2, mod) * b[0] % mod
    elif 0 > b[-1] * neg[0]:
        ans = ans * pow(neg[0], mod - 2, mod) * b[-1] % mod
    else:
        ans = reduce(lambda a, b: (a * b) % mod, a[:k])
print(ans)
n = int(input())
arr = {}
for i in range(n):
    num = int(input())
    if num in arr:
        arr.remove(num)
    else:
        arr.add(num)
print(len(arr))

### FIXED CODE ###

n = input()
if "9" in n:
    print("Yes")
else:
    print("No")
while True:
    try:
        a,b = map(int,raw_input().split())
        c=str(a+b)
        print len(c)
    except EOFError:
        break

### FIXED CODE ###

a = [input() for i in range(10)]
a.sort(reverse=True)
#print "answer"
for i in range(3):
    print a[i]
def cross(x, y):
    return (x.conjugate() * y).imag

def area_polygon(points):
    area = 0
    n = len(points)
    for i in range(n):
        area += cross(points[i], points[(i+1)%n])
    return area / 2
    
    
import sys

p = []
for line in sys.stdin:
    p.append(list(map(float, line.split(','))))

print(area_polygon(p))

### FIXED CODE ###

def cross(x, y):
    return (x.conjugate() * y).imag

def area_polygon(points):
    area = 0
    n = len(points)
    for i in range(n):
        area += cross(points[i], points[(i+1)%n])
    return area / 2
    
    
import sys

p = []
for line in sys.stdin:
    x, y = map(float, line.split(','))
    p.append(complex(x, y))

print(area_polygon(p))
a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
b = int(input())
print(a[b])

### FIXED CODE ###

a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
print(a[k-1])
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
print(sum((r+((sum(a[i]>j for j in a[i:])*(k*(k+1)//2)%mod)+(sum(a[i]>j for j in a[:i+1])*(k*(k-1)//2)%mod))%mod)%mod for i in range(n)))

### FIXED CODE ###

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

mod = 10**9 + 7
x = (k*(k+1)//2)%mod
y = (k*(k-1)//2)%mod

r = 0
for i in range(n):
    right = sum(a[i] > j for j in a[i:])
    left = sum(a[i] > j for j in a[:i+1])
    r = (r+((right*x) + (left*y))%mod)%mod
print(r)
n = int(input())
s = list(map(int, input().split()))
color = 0  # appeared_zero (0~2)
ans = 1
MOD = 1000000007
cur = [-1, -1, -1]
for c in s:
    if c == 0:
        cur[color] = 0
        color += 1
        ans %= MOD
    else:
        x = cur.count(c - 1)
        ans *= x
        ans %= MOD
        idx = cur.index(c - 1)
        cur[idx] += 1
ans *= 3 if color == 0 else 3 if color == 1 else 6
ans %= MOD
print(ans)


### FIXED CODE ###

# なんか雑に書いたらサンプル3通ったしこれでよさそう
# なんかしらんけど2ケースでWAなる
n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 1
d = [0] * (n + 10)
d[0] = 3
for i in range(n):
    ans *= d[a[i]]
    d[a[i]] -= 1
    d[a[i] + 1] += 1
    ans %= mod
print(ans)
def acinput():
    return list(map(int, input().split(" ")))


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])
            #print(result)
            result%=(10**9+7)

    return result


X,Y=acinput()

import numpy as np
from numpy.linalg import solve
 

x=solve([[1,2],[2,1]],[X,Y])

#print(x)

if np.all(x%1.0==0) and np.all(x>=0):
    print(cmb(int(np.sum(x)),int(np.min(x)),10**9+7))

else:
    print(0)



### FIXED CODE ###


def acinput():
    return list(map(int, input().split(" ")))


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])
            #print(result)
            result%=(10**9+7)

    return result


X,Y=acinput()

import numpy as np
from numpy.linalg import solve
 

x=solve([[1,2],[2,1]],[X,Y])

#print(x)

if np.all(x%1.0==0) and np.all(x>=0):
    print(cmb(int(np.sum(x)),int(np.min(x))))
    #print(cmb(int(np.sum(x)),int(np.min(x)),10**9+7))

else:
    print(0)
a=input()
b=input()
s=[]
for i in range(len(a)):
    s.append(a[i])
    s.append(b[i])
print("".join(s))

### FIXED CODE ###

a=input()
b=input()
s=[]
if len(a)==len(b):
    for i in range(len(a)):
        s.append(a[i])
        s.append(b[i])
else:
    for i in range(len(b)):
        s.append(a[i])
        s.append(b[i])
    s.append(a[-1])
print("".join(s))
input_x = str(input())
input_y = str(input())
tmp = input_y
ary = list(input_y)
mongon = "Yes"
for c in input_x:
    idx = tmp.find(c)
    if idx == -1:
        mongon = "No"
        break
    else:
        ary.pop(idx)
        tmp = "".join(ary)


print(mongon)


### FIXED CODE ###

input_s = str(input())
ary = input_s.split(" ")
ary.sort()
task = 0
tmp1 = 0
tmp2 = 0
for i in ary:
    if tmp1 == 0:
        tmp1 = int(i)
    else:
        tmp2 = int(i)
        if tmp1 < tmp2:
            task += tmp2 - tmp1
        else:
            task += tmp1 - tmp2
        tmp1 = tmp2
print(task)
N, K= map(int, input().split())
S = input()

ones_list = S.split('0')
zeros_list = S.split('1')

ones = []
if S[0] == '0':
    ones.append(0)
for k in range(len(ones_list)):
    if ones_list[k] != '':
        ones.append(len(ones_list[k]))
if S[-1] == '0':
    ones.append(0)

zeros = []
for k in range(len(zeros_list)):
    if zeros_list[k] != '':
        zeros.append(len(zeros_list[k]))

if K >= len(zeros):
    print(len(S))
 
else:
  result = []
	maximum = 0
	for k in range(K):
    	maximum += ones[k]
    	maximum += zeros[k]
	maximum += ones[K]
	result.append(maximum)


	for j in range(len(ones) - K - 1):
    	maximum += zeros[K+j] + ones[K+1+j] - ones[j] - zeros[j]
    	result.append(maximum)
	print(max(result))

### FIXED CODE ###

import sys

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

ones_list = S.split('0')
zeros_list = S.split('1')

ones = []
if S[0] == '0':
    ones.append(0)
for k in range(len(ones_list)):
    if ones_list[k] != '':
        ones.append(len(ones_list[k]))
if S[-1] == '0':
    ones.append(0)

zeros = []
for k in range(len(zeros_list)):
    if zeros_list[k] != '':
        zeros.append(len(zeros_list[k]))

if K >= len(zeros):
    print(len(S))
    sys.exit()

result = []
maximum = 0
for k in range(K):
    maximum += ones[k]
    maximum += zeros[k]
maximum += ones[K]
result.append(maximum)


for j in range(len(ones) - K - 1):
    maximum += zeros[K+j] + ones[K+1+j] - ones[j] - zeros[j]
    result.append(maximum)
print(max(result))
n = int(input())
lst = str(input()).split(' ')

p1 = [0]*10
p2 = [0]*10
for idx in range(n):
	if idx%2 == 0:
		p1[int(lst[idx])] += 1
	else:
		p2[int(lst[idx])] += 1


pp1 = p1.index(max(p1))
pp2 = p2.index(max(p2))
if pp1 == pp2:

	if max(p1) >= max(p2):

		pp1 = p1.index(max(p1))
		pp2 = p2.index(sorted(p2)[-2])
	elif max(p2) > max(p1):
		pp1 = p1.index(sorted(p1)[-2])
		pp2 = p2.index(max(p2))


cnt1 = 0
cnt2 = 0
for idx in range(n):
	if idx%2 == 0:
		if not lst[idx] == str(pp1):
			cnt1 += 1
	else:
		if not lst[idx] == str(pp2):
			cnt2 += 1

print(cnt1 + cnt2)

### FIXED CODE ###

n = int(input())
lst = str(input()).split(' ')

p1 = [0]*(max([int(i) for i in lst])+1)
p2 = [0]*(max([int(i) for i in lst])+1)
for idx in range(n):
	if idx%2 == 0:
		p1[int(lst[idx])] += 1
	else:
		p2[int(lst[idx])] += 1

pp1 = p1.index(max(p1))
pp2 = p2.index(max(p2))
if pp1 == pp2:
	if max(p1)+sorted(p2)[-2] >= sorted(p1)[-2]+max(p2):
		pp2 = p2.index(sorted(p2)[-2])
	else:
		pp1 = p1.index(sorted(p1)[-2])

cnt1 = 0
cnt2 = 0
for idx in range(n):
	if idx%2 == 0:
		if not lst[idx] == str(pp1):
			cnt1 += 1
	else:
		if not lst[idx] == str(pp2):
			cnt2 += 1

print(cnt1 + cnt2)
N = int(input())
H = list(map(str, input().split()))
S = H[0]
T = H[1]
#print(S)
#print(T)
L=S[0]+T[0]+S[1]+T[1]
#L[1]=T[1]
#L[2]=S[2]
#L[3]=T[2]


if N >=3:
    for i in range(2,N):
        L=L+S[i]
        L=L+T[i]
print(L)


### FIXED CODE ###

N = int(input())
H = list(map(str, input().split()))
S = H[0]
T = H[1]
#print(S)
#print(T)
L=S[0]+T[0]
for i in range(1,N):
    L=L+S[i]
    L=L+T[i]
print(L)
def replace(str):
    for i, c in enumerate(command[3], command[1]):
        str[i] = c
    return str

def reverse(str):
    for i, c in enumerate(reversed(str[command[1]: command[2]+1]), command[1]):
        str[i] = c
    str = ''.join(str)
    return str

def str_print(str):
    str = ''.join(str)
    print(str[command[1]: command[2]+1])

str = list(input())
q = int(input())
for i in range(q):
    command = input().split()
    command[1], command[2] = int(command[1]), int(command[2])
    if command[0] == 'replace':
        str = replace(str)
    elif command[0] == 'reverse':
        str = reverse(str)
    else:
        str_print(str)



### FIXED CODE ###

def replace(str):
    for i, c in enumerate(command[3], command[1]):
        str[i] = c
    return str

def reverse(str):
    for i, c in enumerate(reversed(str[command[1]: command[2]+1]), command[1]):
        str[i] = c
    return str

def str_print(str):
    str = ''.join(str)
    print(str[command[1]: command[2]+1])
    str = list(str)
    return str

str = list(input())
q = int(input())
for i in range(q):
    command = input().split()
    command[1], command[2] = int(command[1]), int(command[2])
    if command[0] == 'replace':
        str = replace(str)
    elif command[0] == 'reverse':
        str = reverse(str)
    else:
        str = str_print(str)
#EDPC L
import sys
sts.setrecursionlimit(10**8)

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

#dp[l][r]:=区間[l,r]が残っている時の(直後の人の最終的な得点-そうじゃない方の最終的な得点）

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


#for i in range(N-1):
#    for j in range()
def rec(l,r):
    if dp[l][r]!=-1:
        return dp[l][r]
    
    if l==r:
        dp[l][r]=a[l]
        return dp[l][r]
    
    dp[l][r]=max(a[l]-rec(l+1,r),a[r]-rec(l,r-1))

    return dp[l][r]


print(rec(0,N-1))


### FIXED CODE ###

#EDPC L メモ化再帰じゃTLEで通らないのでやり直し

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

#dp[l][r]:=区間[l,r]が残っている時の(直後の人の最終的な得点-そうじゃない方の最終的な得点）

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

for k in range(N):
    dp[k][k]=a[k]

for r in range(1,N):
    for l in reversed(range(r)):
        dp[l][r]=max(a[l]-dp[l+1][r],a[r]-dp[l][r-1])

print(dp[0][N-1])
n=int(input())
a=list(map(int,input().split()))

for b in a:
    for i in range(60):
        counts[i]+=b%2
        b//=2

ans=0
mod = 10**9+7
for i in range(60):
    c=counts[i]
    comb=c*(n-c)
    ans=(ans+(1<<i)*comb)%mod
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
counts=[0]*60
for b in a:
    for i in range(60):
        counts[i]+=b%2
        b//=2
ans=0
mod = 10**9+7
for i in range(60):
    c=counts[i]
    comb=c*(n-c)
    ans=(ans+(1<<i)*comb)%mod
print(ans)
N, X, T = map(int,input().split())

if N % x == 0:
    print(( N // X ) * T )
else:
    print(( N // X + 1 ) * T )

### FIXED CODE ###

N, X, T = map(int,input().split())

A = N % X

if ( A ) == 0:
    print(( N // X ) * T )
elif ( N % X ) != 0:
    print(( N // X + 1 ) * T )
N = int(input())
T, A = map(int, input().split())
l = list(map(int, input().split()))
deltatemperature = []

for height in l:
  deltatemperature.append(abs(T- height* 0.006- A))
  
m = min(deltatemperature)
mindex = l.index(m)
print(mindex+ 1)

### FIXED CODE ###

N = int(input())
T, A = map(int, input().split())
l = list(map(int, input().split()))
deltatemperature = []

for height in l:
  deltatemperature.append(abs(T- height* 0.006- A))
  
m = min(deltatemperature)
mindex = deltatemperature.index(m)
print(mindex+ 1)
import collections
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
b = collections.Counter(a_list)
d = b.most_common()[:k]
sum = 0
for i in d:
    sum += i
print(n-i)


### FIXED CODE ###

import collections
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
b = collections.Counter(a_list)
d = b.most_common()[k:]
sum = 0
for i in d:
    sum += i[1]
print(sum)
def prim(self):
        gb = GraphBuilder(self.v,self.directed)

        queue = []
        for i,w in self.w_e[0].items(): heapq.heappush(queue,(w,0,i))
        rest = [True]*self.v
        rest[0] = False

        v = 1
        while len(queue)>0:
            w,i,j = heapq.heappop(queue)
            if rest[j]:
                gb.addEdge(i,j,w)
                rest[j] = False
                for k,w in self.w_e[j].items():
                    if rest[k]:heapq.heappush(queue,(w,j,k))

        return gb

### FIXED CODE ###

class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n
    
    def root(self,x):
        if self.par[x] == -1:
            return x 
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x_r = self.root(x)
        y_r = self.root(y)
        
        if self.rank[x_r]>self.rank[y_r]:
            self.par[y_r] = x_r

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

    def isSame(self,x,y):
        return self.root(x) == self.root(y)

    def size(self,x):
        return self.tsize[self.root(x)]

def main():

    n= int(input())
    edge = []
    for i in range(n):
      x,y = list(map(int,input().split()))
      edge.append((x,y,i))
    
    xs = sorted(edge,key=lambda a:a[0])
    ys = sorted(edge,key=lambda a:a[1])

    edge = []
    
    for i in range(n-1):
      x1,y1,p1 = xs[i]
      x2,y2,p2 = xs[i+1]
      edge.append((p1,p2,min(x2-x1,abs(y2-y1))))
      
      x1,y1,p1 = ys[i]
      x2,y2,p2 = ys[i+1]
      edge.append((p1,p2,min(abs(x2-x1),y2-y1)))
    edge.sort(key = lambda a:a[2])  
    uf = UnionFind(n)
    
    ans = 0
    for x,y,w in edge:
      if uf.isSame(x,y):continue
      uf.unite(x,y)
      ans+=w
    print(ans)
      
if __name__ == "__main__":
    main()
Q,E,v,m=input,exec,[],10**9+7;N,K=map(int,Q().split());from collections import Counter as C;E("v+=Q().split();"*(N-1)+"g,v,r=list(C(v).values()),0,K*(K-1);"+"E(\"i=0;\"+\"r=(r*(K-2-i))%m;i+=1;\"*(g[v]-1));v+=1;"*N);print(r)


### FIXED CODE ###

import sys
mod = 1000000007

sys.setrecursionlimit(10**7)
readline = sys.stdin.readline
N, K = map(int, readline().split())

def P(x, y):
    r = 1
    for i in range(y):
        r = (r * (x - i)) % mod
    return r

G = [[] for _ in range(N)]
for v in range(N-1):
    a, b = map(int, readline().split())
    a, b = a-1, b-1
    G[a].append(b)
    G[b].append(a)

def dfs(bb, v):
    cn = 0
    r = 1
    for u in G[v]:
        if u == bb:
            continue
        cn += 1
        r = (r * dfs(v, u)) % mod
    if cn == 0:
        return 1
    else:
        if bb == None:
            return P(K-1, cn) * r % mod
        else:
            return P(K-2, cn) * r % mod

print((K*dfs(None, 0))%mod)
l = map(int,input().split)
print(l[0] * l[1])
print(l[0] * 2 + l[1] * 2)

### FIXED CODE ###

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

s = a * b
shu = a * 2 + b * 2
fmt = "{s} {shu}"
s = fmt.format(s = s,shu = shu)
print(s)
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 10
for i in range(N+1):
    graph[i][i] = 0
LRC.sort(key=lambda x: x[2], reverse=True)
LRC.sort()
dp = [INF] * (N+1) # dp[0]は使わない
visited = 1
dp[1] = 0
for l, r, c in LRC:
    if l > visited:
        print(-1)
        exit()
    if r > visited:
        visited = r
    x = dp[l] + c
    dp[r] = min(dp[r], x)
if dp[N] == INF:
    print(-1)
else:
    print(dp[N])


### FIXED CODE ###

import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def dijkstra(start):
    dist = [INF] * (N+1)
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for cost, next in graph[prev]:
            d1 = d + cost
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

N, M = lr()
INF = 10 ** 15
graph = [[] for _ in range(N+1)] # 1-indexed
for i in range(2, N+1):
    graph[i].append((0, i-1))

for _ in range(M):
    l, r, c = lr()
    graph[l].append((c, r))

dist = dijkstra(1)

if dist[N] == INF:
    print(-1)
else:
    print(dist[N])
# 19