Harryxun/stf_run huggingface dataset:
prime=[False]*1000000
np=[0]*1000000
for i in range(2,1000):
    if not prime[i]
    for j in range(i*2,1000000,i):
        prime[j]=True

while True:
    try:
        n=int(input())
    except:
        break
    print(sum(prime[2:n+1]))

### FIXED CODE ###

prime=[True]*1000000
for i in range(2,1000):
    if prime[i]:
        for j in range(i*2,1000000,i):
            prime[j]=False

while True:
    try:
        n=int(input())
    except:
        break
    print(sum(prime[2:n+1]))
arg = int(raw_input())

s = str(arg)
if '7' in s:
    print('Yes')
else:
    print('No')




### FIXED CODE ###

s = input()
if '7' in s:
    print('Yes')
else:
    print('No')
N=input()
A=list(map(int,input().split()))
A=sorted(A)
for i in range(N-1):
    if A[i+1]-A[i]!=0:
        print('NO')
        exit()
print('YES')

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
for i in range(N-1):
    if A[i+1]-A[i]==0:
        print('NO')
        exit()
print('YES')
N,X=map(int,input().split())
weight = []
W = sum(weight)
P =(X- W) // weight.min()
print(N+P)
  

### FIXED CODE ###

N,X=map(int,input().split())
weight = [int(input()) for weight in range(N)]
W = sum(weight)
P =(X- W) // min(weight)
print(N+P)
a,b,k = map(int,input().split())

if k > a :
  print("0",b-(k-a))
elif k=<a:
  print(a-k,b)

### FIXED CODE ###

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

if a+b > k:
  if k >a :
     print(0,b-(k-a))
  elif k<=a:
     print(a-k,b)
else:
  print(0,0)
class Dice:
    def _init_ (self,data):
        self.data = data

    def move(self,direction):
        if direction == 'E':
            self.data[0],self.data[3],self.data[5],self.data[2] = \
                    self.data[3].self.data[5],self.data[2],self.data[0]
        elif direction == 'N':
            self.data[0],self.data[4],self.data[5],self.data[1] = \
                    self.data[4].self.data[5],self.data[1],self.data[0]
        elif direction == 'S':
            self.data[0],self.data[1],self.data[5],self.data[4] = \
                    self.data[4].self.data[0],self.data[1],self.data[5]
        elif firection == 'W':
            self.data[0],self.data[2],self.data[5],self.data[3] = \
                    self.data[2].self.data[5],self.data[3],self.data[0]

    def getTop(self):
        return self.data[0]

dice = Dice.Dice(input().split())
cmd = input()
for i in range(len(cmd)):
    dice.move(cmd[i])
    print(dice.getTop())

### FIXED CODE ###

class Dice:
    def __init__ (self,data):
        self.data = data

    def move(self,direction):
        if direction == 'E':
            self.data[0],self.data[3],self.data[5],self.data[2] = \
                    self.data[3],self.data[5],self.data[2],self.data[0]
        elif direction == 'N':
            self.data[0],self.data[4],self.data[5],self.data[1] = \
                    self.data[1],self.data[0],self.data[4],self.data[5]
        elif direction == 'S':
            self.data[0],self.data[1],self.data[5],self.data[4] = \
                    self.data[4],self.data[0],self.data[1],self.data[5]
        elif direction == 'W':
            self.data[0],self.data[2],self.data[5],self.data[3] = \
                    self.data[2],self.data[5],self.data[3],self.data[0]

    def getTop(self):
        return self.data[0]

dice = Dice(input().split())
cmd = input()
for i in range(len(cmd)):
    dice.move(cmd[i])
print(dice.getTop())
A, B = mao(int, input().split())
K = A + B
if K % 2 == 0:
  print(K / 2)
else:
  print('IMPOSSIBLE')

### FIXED CODE ###

A, B = map(int, input().split())
K = A + B
if K % 2 == 0:
  print(K // 2)
else:
  print("IMPOSSIBLE")
from math import log10

    class Mod:
        fac = []
        inv = []
        finv = []
        mod = 0
        def __init__(self,maxi:int ,mod:int):
            self.mod = mod
            self.fac = [1]*maxi
            self.inv = [1]*maxi
            self.finv = [1]*maxi
            for i in range(2,maxi):
                self.fac[i] = self.fac[i - 1]*i%mod
                self.inv[i] = mod - self.inv[mod%i]*(mod//i)%mod
                self.finv[i] = self.finv[i-1]*self.inv[i]%mod


        def com(self,n:int, k:int)->int:
            #return nCk
            if n < k:
                return 0
            if n < 0 or k < 0:
                return 0
            return self.fac[n]*(self.finv[k]*self.finv[n-k]%self.mod)%self.mod


    def main():
        s = int(input())
        m =  Mod(s,10**9 + 7)
        ans = 0
        for n in range(1,s // 3 + 1):
            if 3*n == s:
                ans = (ans+1)%(10**9 + 7)
                break
            ans = (ans + m.com(-2*n + s - 1,s - 3*n))%(10**9 + 7)
        print(ans)
        return

    if __name__ == "__main__":
        main()

### FIXED CODE ###

from math import log10

class Mod:
    fac = []
    inv = []
    finv = []
    mod = 0
    def __init__(self,maxi:int ,mod:int):
        self.mod = mod
        self.fac = [1]*maxi
        self.inv = [1]*maxi
        self.finv = [1]*maxi
        for i in range(2,maxi):
            self.fac[i] = self.fac[i - 1]*i%mod
            self.inv[i] = mod - self.inv[mod%i]*(mod//i)%mod
            self.finv[i] = self.finv[i-1]*self.inv[i]%mod


    def com(self,n:int, k:int)->int:
        #return nCk
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return self.fac[n]*(self.finv[k]*self.finv[n-k]%self.mod)%self.mod


def main():
    s = int(input())
    m =  Mod(s,10**9 + 7)
    ans = 0
    for n in range(1,s // 3 + 1):
        if 3*n == s:
            ans = (ans+1)%(10**9 + 7)
            break
        ans = (ans + m.com(-2*n + s - 1,s - 3*n))%(10**9 + 7)
    print(ans)
    return

if __name__ == "__main__":
    main()
n,m=[int(_) for _ in input()]
m1=n//2
for i in range(min(m1//2,m)):
  print(i+1,m1-i)
if m>m1:
  for i in range(m-m1):
    print(m1+i+1,m1*2-i-1)
    

### FIXED CODE ###

n,m=[int(_) for _ in input().split()]

n=2*m+1
if m%2==0:
  for i in range(m//2):
    print(i+1,m-i)
  for i in range(m//2):
    print(m+1+i,n-i)
else:
  for i in range(m//2):
    print(i+1,m-i)
  for i in range(m//2+1):
    print(m+1+i,n-i)
n, c = list(map(int, input().split()))
sushi1 = []
sushi2 = []
c1 = []
c2 = []
c3 = []
c4 = []
k1 = 0
k2 = 0
for i in range(n):
    x, v = list(map(int, input().split()))
    sushi1.append((x, v))
    sushi2.append((c-x, v))
sushi1.sort()
sushi2.sort()
for j in range(n):
    k1 += sushi1[j][1]
    k2 += sushi2[j][1]
    c1.append(k1-sushi1[j][0])
    c2.append(k2-sushi2[j][0])
for k in range(n):
    c3.append(c1[k]+max(c2[:n-k-1])-sushi1[k][0])
    c4.append(c2[k]+max(c1[:n-k-1])-sushi2[k][0])
print(max(c1+c2+c3+c4+[0]))

### FIXED CODE ###

import numpy as np
n, c = list(map(int, input().split()))
xv = list(list(map(int, input().split())) for i in range(n))
sushi1, max1, sushi2, max2 = [0], [0], [0], [0]
sum1, sum2 = 0, 0
for x, v in xv:
    sum1 += v
    sushi1.append(max(sum1 - x, sushi1[-1]))
    max1.append(max(sum1 - 2*x, max1[-1]))
for x, v in xv[::-1]:
    sum2 += v
    sushi2.append(max(sum2 - (c-x), sushi2[-1]))
    max2.append(max(sum2 - 2*(c-x), max2[-1]))
ans1 = max(np.array(sushi1) + np.array(max2[::-1]))
ans2 = max(np.array(sushi2) + np.array(max1[::-1]))
print(max(0, ans1, ans2))
N = int(input())
s = [input() for i in range(N)]
M = int(input())
t = [input() for j in range(M)]

count = 0
for word in (s):
    counter = max(counter,s.count(word) - t.count(word))
print(counter)

### FIXED CODE ###

n = int(input())
s = list()
counter = 0

for i in range(n):
    s.append(input())
    
m = int(input())
t = list()

for i in range(m):
    t.append(input())

for word in s:
    counter = max(counter,s.count(word) -t.count(word))
print(counter)
N = int(input())
A = list(map(int,input().split()))
import numpy as np
B = np.array(A,dtype='float64')
ans = np.cumprod(B)
if ans[N-1] > 10**18:
    print(-1)
else:
    print(int(ans[N-1]))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
U = 10 ** 18
p = 1
for x in A:
    p *= x
    if p > U:
        p = U + 1
 
if p > U:
    print(-1)
else:
    print(p)
from math import gcd
A,B,C,D = map(int,input().split())
ans = 0
N = 1
E = C*D//gcd(C,D)
ans += B-B//C-B//D+B//E
ans -= A-A//C-A//D+A//E
print(ans)

### FIXED CODE ###

from fractions import gcd
A,B,C,D = map(int,input().split())
E = C*D//gcd(C,D)
ans = 0
ans += B-B//C-B//D+B//E
ans -= A-1-(A-1)//C-(A-1)//D+(A-1)//E
print(ans)
H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]
ans = 0


def change(x, y):
    if x < 0 or x >= W:
        return False
    if y < 0 or y >= H:
        return False

    if G[x][y] == ".":
        G[x][y] = "@"
        return False
    elif G[x][y] == "#":
        return True


def search(x, y):
    global ans
    count = 0
    sharp = 0

    while sharp == 0:
        if count == 0:
            G[x][y] = "@"
        else:
            for i in range(count+1):
                if change(x+count-i, y+1) or change(x-i, y+count-i) or \
                    change(x-count+i, y-i) or change(x+i, y-count+i):
                    sharp += 1

        if count > ans:
            ans = count

        count += 1


for i in range(H):
    for j in range(W):
        if G[i][j] == ".":
            search(j, i)

print(ans)



### FIXED CODE ###

from collections import deque

dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
H, W = map(int, input().split())
edge = ['#']*(W+2)
field = [edge]
q = deque()

for i in range(H):
    field.append(['#'] + list(input()) + ['#'])
    for j in range(W):
        if field[i+1][j+1] == '#':
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    res = max(lv, res)

    for dy, dx in dyx:
        if field[y+dy][x+dx] == '.':
            field[y+dy][x+dx] = '#'
            q.append((y+dy, x+dx, lv+1))

print(res)
N = int(input())
N1 = N%100//5
N2 == 0
if N%100%5 == 0:
    N2 = 0
else:
    N2 = 1
S =N1+N2
if 100*S > N:
    print(0)
else:
    print(1)

### FIXED CODE ###

N = int(input())
N1 = N%100//5
N2 = 0
if N%100%5 == 0:
    N2 = 0
else:
    N2 = 1
S =N1+N2
if 100*S > N:
    print("0")
else:
    print("1")
n = int(input())
d,x = map(int(), input().split())
times = [int(input()) for i in range(n)]

count = 0
for k in range(n):
    count += int(d/times[k]) + 1

print(count + x)

### FIXED CODE ###

N=int(input())
D,X=map(int,input().split())
ans=0
for _ in[0]*N:
    A=int(input())
    ans+=(D+A-1)//A
print(ans+X)
num = int(input())
i = 1
while True:
    bef = range(1,i)
    i += 1
    aft = range(1,i)
    if bef < num <= aft:
        print(i-1)
        break


### FIXED CODE ###

num = int(input())
i = 1
bef = 0
while True:
    bef += i-1
    aft = bef + i
    if bef < num <= aft:
        print(i)
        break
    i += 1
from sys import stdin
n = int(stdin.readline())
d,s = map(int,stdin.readline().split())
for _ in xrange(n):
 x = int(stdin.readline())
 st = 1
 while st <= d:
  s+=1
  st += x
print s

### FIXED CODE ###

from sys import stdin
a = int(stdin.readline())
b = int(stdin.readline())
c = int(stdin.readline())
d = int(stdin.readline())
print min(a,b) + min(c,d)
import sys
A, B = map(int, input().split())
tmp = A
ans = 1
if B == 1:
    print(0)
    sys.exit()

while True:
    if A < B:
        A += tmp - 1
        ans += 1
    else:
        break

print(ans)w

### FIXED CODE ###

import sys
A, B = map(int, input().split())
tmp = A
ans = 1
if B == 1:
    print(0)
    sys.exit()

while True:
    if A < B:
        A += tmp - 1
        ans += 1
    else:
        break

print(ans)
import functools
import operator

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

result = functools.reduce(operator.mul, A)

if result > 10^18:
  print("-1")
else:
  print(ANS)

### FIXED CODE ###

def main():
	N = int(input())
	A = list(map(int, input().split()))
	if 0 in A:
		print(0)
		return
	prod = 1
	for a in A:
		prod *= a
		if prod > 1000000000000000000:
			print(-1)
			return
	print(prod)
main()
import bisect

n = int(input())
d = list(int(x) for x in input().split())
d.sort()

ans = 0

for k in range(min(d), d[(n // 2) + 1]):
    idx = bisect.bisect_left(d, k)
    abc_num = idx
    arc_num = n - abc_num
    if arc_num == abc_num:
        ans += 1

print(ans)

### FIXED CODE ###

import bisect

n = int(input())
d = list(int(x) for x in input().split())
d.sort()

print(d[(n // 2)] - d[(n // 2) - 1])

"""
for k in range(d[n // 2], d[(n // 2) + 1]):
    if bisect.bisect_left(d, k) == n // 2:
        ans += 1
"""
W,H,x,y,r,=map(int,input().split())
if x-r<0 (or) x+r>W and() y-r<0 (or) y+r>H:
    print ("No")
elif x-r>=0 (and) x+r<=W and() y-r>=0 (and) y+r<=H:
    print ("Yes")


### FIXED CODE ###

W,H,x,y,r,=map(int,input().split())
if (x-r<0 or x+r>W) or (y-r<0 or y+r>H):
    print ("No")
elif (x-r>=0 and x+r<=W) or (y-r>=0 and y+r<=H):
    print ("Yes")
s = str(input('曜日を入力：'))
  
elif s == 'SAT':
  print('1')
  
elif s == 'FRI':
  print('2')
  
elif s == 'THU':
  print('3')
  
elif s == 'WED':
  print('4')

elif s == 'TUE':
  print('5')
  
elif s == 'MON':
  print('6')

else:
  print('7')

### FIXED CODE ###

s = str(input())
  
if s == 'SAT':
  print('1')
  
elif s == 'FRI':
  print('2')
  
elif s == 'THU':
  print('3')
  
elif s == 'WED':
  print('4')

elif s == 'TUE':
  print('5')
  
elif s == 'MON':
  print('6')

else:
  print('7')
from math import gcd
N = int(input())
A = list(map(int, input().split()))
L = [0]
R = [0]
M = []
maximum = 0
for n in range(N):
    L.append(gcd(A[n], L[-1]))
    R.append(gcd(A[-n-1], R[-1]))
R.reverse()
for n in range(N):
    M.append(gcd(L[n], R[n+1]))
for n in range(N):
    maximum = max(maximum, M[n])
print(maximum)

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
L = [0]
R = [0]
M = []
maximum = 0
for n in range(N):
    L.append(gcd(A[n], L[-1]))
    R.append(gcd(A[-n-1], R[-1]))
R.reverse()
for n in range(N):
    M.append(gcd(L[n], R[n+1]))
for n in range(N):
    maximum = max(maximum, M[n])
print(maximum)
A = input()
if A[0] != A[2] == A[4] or A[2] != A[4] == A[0] or A[0] != A[4] == A[2]:
    input('Yes')
else:
    input('No') 

### FIXED CODE ###

A = input()
if A[0] != A[2] == A[4] or A[2] != A[4] == A[0] or A[4] != A[0] == A[2]:
    print('Yes')
else:
    print('No')
a,b = map(int,input().split())
  if (a*b % 2):
    print("Even") 
  else:
    print("Odd")                                                             
 

### FIXED CODE ###

a,b = map(int,input().split())
if (a*b % 2 == 0):
  print("Even") 
else:
  print("Odd")
N = int(input())
a = list(map(int, input().split()))

b = [0]*(10**5)
for i in a:
    if i == 10**5:
        b[i-1] += 1
        b[i] += 1
    elif i == 0:
        b[i] += 1
        b[i+1] += 1
    else:
        b[i-1] += 1
        b[i] += 1
        b[i+1] += 1

print(max(b))

### FIXED CODE ###

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

b = [0]*(10**5+1)
for i in a:
    if i == 10**5:
        b[i-1] += 1
        b[i] += 1
    elif i == 0:
        b[i] += 1
        b[i+1] += 1
    else:
        b[i-1] += 1
        b[i] += 1
        b[i+1] += 1

print(max(b))
s = input().rstrip()
l = len(s)
half_len = int(l/2)

if l%2 != 0:
	s = s.replace(s[half_len], "")
	fst_half = s[:half_len]
	snd_half = s[half_len:]
else:
	fst_half = s[:half_len]
	snd_half = s[half_len:]

snd_half = snd_half[::-1]

count = 0
for i in range(half_len):
	if(snd_half[i] != fst_half[i]):
		count += 1

print(count)

### FIXED CODE ###

s = input()
res = 0
for i in range(len(s)//2):
    res += int(s[i] != s[len(s)-i-1])
print(res)
N, Q = map(int, input().split())
a=input()

list=[0]*N+1

for i in range(N):
    list[i+1]=list[i]+1 if a[i:i+2]=="AC" else list[i]
    
for i in range(N):
    l,r = map(int, input().split())
    print(list[r-1]-list[l-1])
    

### FIXED CODE ###

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

list=[0]*(N+1)

for i in range(N):
    list[i+1]=list[i]+1 if a[i:i+2]=="AC" else list[i]
    
for i in range(Q):
    l,r = map(int, input().split())
    print(list[r-1]-list[l-1])
def maxim(i,char):
    if i<0:
        return 0

    if char=='C':
        return max(c[i]+maxim(i-1,'B'),c[i]+maxim(i-1,'A'))
    if char=='B':
        return max(b[i] + maxim(i - 1, 'A'), b[i] + maxim(i - 1, 'C'))
    if char=='A':
        return max(a[i] + maxim(i - 1, 'B'), a[i] + maxim(i - 1, 'C'))
n=int(input())
a, b, c = [], [], []
for _ in range(n):
    ##a,b,c=[],[],[]
    x,y,z=map(int,input().split())
    a.append(x)
    b.append(y)
    c.append(z)
##print(a,b,c)
print(max(maxim(n-1,'C'),maxim(n-1,'B'),maxim(n-1,'A')))



### FIXED CODE ###

import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()


n=int(input())
a, b, c = [], [], []
for _ in range(n):
    x,y,z=get_ints()
    
    a.append(x)
    b.append(y)
    c.append(z)
li=[[-1 for i in range(3)]for j in range(n)]
li[0][0],li[0][1],li[0][2]=a[0],b[0],c[0]
for i in range(1,n):


        li[i][0] = max(a[i] + li[i-1][1] ,a[i] + li[i - 1][2])

        li[i][1] = max(b[i] + li[i - 1][0], b[i] +li[i - 1][2])

        li[i][2] = max(c[i] + li[i - 1][1], c[i] + li[i - 1][0])
print(max(li[n-1]))
a,v,b,w,t=int(input().split())
 
if a<b:
  if b+w*t<=a+v*t:
    print('YES')
  else:
    print('NO')
if a>b:
  if a-v*t<=b-w*t:
    print('YES')
  else:
    print('NO')

### FIXED CODE ###

a,v=map(int, input().split())
b,w=map(int, input().split())
t=int(input())
 
if a<b:
  if b+w*t<=a+v*t:
    print('YES')
  else:
    print('NO')
if a>b:
  if a-v*t<=b-w*t:
    print('YES')
  else:
    print('NO')
L = input()
memo = {}
def dp(index,tight):
    if index == -1:
        return tight == 1
    if not (index,tight) in memo:
        if L[index] == "1" and tight:
            memo[(index,tight)] = 2*dp(index-1,1)
        elif L[index] == "1" and not tight:
            memo[(index,tight)] = 3*dp(index-1,0) + dp(index-1,1)
        elif L[index] == "0" and tight:
            memo[(index,tight)] = dp(index-1,1)
        else:
            memo[(index,tight)] = 3*dp(index-1,0)
    return memo[(index,tight)]
print(dp(len(L)-1,0)+dp(len(L)-1,1))

### FIXED CODE ###

L = input()
n = len(L)
mod = 10**9+7
dp1 = [0]*(n+1)
dp2 = [0]*(n+1)
dp1[0] = 1
for i in range(n):
    if L[i] == "1":
        dp1[i+1] = (dp1[i]*2)%mod
        dp2[i+1] = (dp1[i] + dp2[i]*3)%mod
    else:
        dp1[i+1] = dp1[i]
        dp2[i+1] = (dp2[i]*3)%mod
print((dp1[n]+dp2[n])%mod)
/* ex4_1
  bonbonc */

#include<stdio.h>
int main(void){
	int tree, range;
	int assigned;//一人が割り当てられる木の本数の最大値

	scanf("%d %d",&tree,&range);
	assigned = 2*range+1; //自分のいる位置と左右にrange本

	if (tree%assigned==0){//木の本数がassignedで割り切れるとき
		printf("%d\n",tree/assigned);//木の本数をassignedで割った商を出力
	}else{
		printf("%d\n",tree/assigned +1);//木の本数をassignedで切り捨て除算し、1を加えて出力
	}

	
	return 0;
}

### FIXED CODE ###

N,D=map(int,input().split())
assined = 2*D+1
if N%assined==0:
  print(N//assined)
else:
  print(N//assined+1)
N=int(input())
A=int(input())
if (N%500)==0:
  print("Yes")
elif (N%500)%A==0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N=int(input())
A=int(input())
if (N%500)==0:
  print("Yes")
elif ((N%500)-A)<=0:
  print("Yes")
elif ((N%500)-A) >0:
  print("No")
def main():
    N = int(input())
    l = list(map(int, input().split()))
    ans = []
    X = sum(l)
    for i in range(N-1):
      	X = abs(X-2*l[i])
        ans.append(X)
    print(min(ans))
if __name__ == '__main__':
    main()


### FIXED CODE ###

a , b = map(int, input().split())
if a%3==0 or b%3==0 or (a+b)%3==0:
    print('Possible')
else:
    print('Impossible')
import sys
import time
import math
import itertools as it
def inpl():
    return list(map(int, input().split()))
st = time.perf_counter()
# ------------------------------

N, M = inpl()
dp = [-1] * N
for _ in range(M):
    s, c = inpl()
    s -= 1
    if dp[s] not in [-1, c]:
        print(-1)
        sys.exit()
    dp[s] = c
for i in range(N):
    if N == 1:
        if dp[i] == -1:
            print(0, end='')
        else:
            print(dp[i], end='')
    else:
        if i == 0:
            if dp[i] == -1:
                print(1, end='')
            elif dp[i] == 0
                print(-1)
                sys.exit()
            else:
                print(dp[i], end='')
        else:
            if dp[i] == -1:
                print(0, end='')
            else:
                print(dp[i], end='')
                
print()
# ------------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)


### FIXED CODE ###

import sys
import time
import math
import itertools as it
def inpl():
    return list(map(int, input().split()))
st = time.perf_counter()
# ------------------------------

N, M = inpl()
dp = [-1] * N
for _ in range(M):
    s, c = inpl()
    s -= 1
    if dp[s] not in [-1, c]:
        print(-1)
        sys.exit()
    dp[s] = c
for i in range(N):
    if N == 1:
        if dp[i] == -1:
            print(0, end='')
        else:
            print(dp[i], end='')
    else:
        if i == 0:
            if dp[i] == -1:
                print(1, end='')
            elif dp[i] == 0:
                print(-1)
                sys.exit()
            else:
                print(dp[i], end='')
        else:
            if dp[i] == -1:
                print(0, end='')
            else:
                print(dp[i], end='')
                
print()
# ------------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)
import sys,queue,math,copy,itertools,bisect,collections,heapq

S = set()
curmin = 10 ** 10  # 現時点での最小値
flag = False  # 更新が必要か

def insert(x):
    global curmin, flag
    S.add(x)
    if x <= curmin:
        curmin = x
        flag = False
    return


def erase(x):
    global curmin, flag
    S.remove(x)
    if x == curmin:
        flag = True
    return


def minimum():
    global curmin, flag
    if flag:
        curmin = min(S)
        flag = False
    return curmin

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]



    N,M = LI()
    p = [LI() for _ in range(M)]

    p.sort()

    r = [[] for _ in range(N+1)]
    d = 0
    j = 0
    for i in range(1,N+1):
        while j < M and p[j][0] == i:
            insert(d + p[j][2])
            r[p[j][1]].append(d + p[j][2])
            j += 1
        for z in r[i]:
            erase(z)
        if i == N: break
        if len(S) == 0:
            print(-1)
            return

        d = minimum()
    print(d)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

class Node:
    def __init__(self,x):
        self.data = x
        self.left = None
        self.right = None

def insert(node,x):
    if node is None: return Node(x)
    elif x < node.data:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node

def search_min(node):
    if node.left is None: return node.data
    return search_min(node.left)

def delete_min(node):
    if node.left is None: return node.right
    node.left = delete_min(node.left)
    return node

def delete(node,x):
    if node:
        if x == node.data:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data:
            node.left = delete(node.left,x)
        else:
            node.right = delete(node.right,x)
    return node


def main():
    sys.setrecursionlimit(10**7)
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    p = [LI() for _ in range(M)]

    p.sort()

    r = [[] for _ in range(N+1)]
    d = 0
    j = 0
    root = None
    for i in range(1,N):
        update = False
        while j < M and p[j][0] == i:
            root = insert(root,d + p[j][2])
            update = True
            r[p[j][1]].append(d + p[j][2])
            j += 1
        for z in r[i]:
            root = delete(root,z)
            update = True
        if root == None:
            print(-1)
            return
        if update:
            d = search_min(root)
    print(d)

if __name__ == '__main__':
    main()