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

from itertools import product
import sys

input = sys.stdin.readline

INF = float('inf')

def floyd_warshall(V, E):
    dist = {u: {v: INF for v in V} for u in V}
    for v in V:
        dist[v][v] = 0
        for (i, j) in E[v]: dist[v][(i, j)] = 1
    for k in V:
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    for v in V:
        if dist[v][v] < 0: return None
    return dist

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = {}
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.':
            E.setdefault((i, j), [])
            E.setdefault((x, y), [])
            E[(i, j)].append((x, y))
            E[(x, y)].append((i, j))
dist = floyd_warshall(V, E)
ans = 0
for D in dist.values():
    ans = max(ans, max(D.values()))
print(ans)

### FIXED CODE ###

from collections import deque
from itertools import product

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = {}
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.':
            E.setdefault((i, j), [])
            E.setdefault((x, y), [])
            E[(i, j)].append((x, y))
            E[(x, y)].append((i, j))

def bfs(s):
    q = deque([(s, 0)])
    dist = {v: -1 for v in V}
    while q:
        v, d = q.popleft()
        if dist[v] >= 0: continue
        dist[v] = d
        for u in E[v]:
            if dist[u] < 0:
                q.append((u, d+1))
    return dist

ans = 0
for v in V:
    dist = bfs(v)
    ans = max(ans, max(dist.values()))
print(ans)
### BUGGY CODE ###

N, A, B = map(int, input().split())
ball = []
kaisu = -(-N//(A+B))
for n in range(kaisu):
    for i in range(A):
        ball += [0]
        if len(ball)==N:
            break
    if len(ball)==N:
        break
    for j in range(B):
        ball += [1]
        if len(ball)==N:
            break
    if len(ball)==N:
        break

print(ball.count(0))

### FIXED CODE ###

N, A, B = map(int, input().split())
kaisu = N//(A+B)

n = N-((A+B)*kaisu)
if n >= A:
    print(A*(kaisu+1))
else:
    print(A*kaisu+n)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
 
N = int(input())
aN = list(map(int, input().split()))

ans = 0
for i in range(N):
    sm = xor = 0
    for j in range(i, N):
        sm += aN[j]
        xor ^= aN[j]
        if sm == xor:
            ans += 1
        # 一度合わなくなったら、そこから先で合うことはないはず
        else:
            break
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

"""
しゃくとり法
・前にやったのとか参考にして自力実装
"""
 
N = int(input())
aN = list(map(int, input().split()))

l,r,ans = 0,0,0
sm = xor = 0
# 外ループで左を動かす
while l < N:
    # 内ループは条件を満たす限り右を動かす
    while r < N and sm + aN[r] == xor ^ aN[r]:
        ans += 1
        sm += aN[r]
        xor ^= aN[r]
        r += 1
    # 左右の差分-1
    ans += r - l - 1
    # ※今回はl==rの時whileの条件を確実に満たすので、
    # ここでl==rになることはなく、このif文は本当は必要ない。
    if l == r:
        # 左が右に追いついたら、右も左に合わせて+1する
        r += 1
    else:
        # 左を動かす分の合計を引く
        sm -= aN[l]
        xor ^= aN[l]
    l += 1
print(ans)
### BUGGY CODE ###

n=int(input())

r=[]

for i in range(1,n//2+1):
    if n % i == 0:
        r.append(i + n//i -2)

print(min(r))

### FIXED CODE ###

n=int(input())

r=[]

for i in range(1,int(n**0.5+1)):
    if n % i == 0:
        r.append(i + n//i -2)

print(min(r))
### BUGGY CODE ###

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

N, M = inpl()
A = inpl()
A.sort(reverse = True)
matnum = set([(2, 5, 5, 4, 5, 6, 3, 7, 6)[a-1] for a in A])
maxdig = 1
Dig = [{0}]
for i in range(1,1+N//min(matnum)):
    k = set()
    for v in Dig[-1]:
        for a in matnum:
            k.add(a+v)
    if N in k:
        maxdig = i
    Dig.append(k)
N1 = N
ansli = [0]*maxdig
for i in range(maxdig, 0, -1):
    for a in A:
        if N1-(2, 5, 5, 4, 5, 6, 3, 7, 6)[a-1] in Dig[i-1]:
            ansli[maxdig-i] = a
            N1 -= (2, 5, 5, 4, 5, 6, 3, 7, 6)[a-1]
            break
        
print(''.join(map(str, ansli)))


### FIXED CODE ###

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

N, M = inpl()
A = inpl()
A.sort(reverse = True)

inf = float('inf')
match = (inf, 2, 5, 5, 4, 5, 6, 3, 7, 6)
matnum = set([match[a] for a in A])
dp = [0]+[-inf]*N

for i in range(1, N+1):
    dp[i] = max([10*dp[max(-1,i-match[a])] + a for a in A])

print(''.join(sorted(str(dp[-1]), reverse = True)))
### BUGGY CODE ###

import numpy as np


def solve(string):
    n, m, *py = map(int, string.split())
    p = [[] for _ in range(n)]
    for _p, _y in zip(py[0::2], py[1::2]):
        p[_p - 1].append(_y)
    for i in range(n):
        p[i] = np.argsort(np.argsort(p[i]))
    counter = [0 for _ in range(n)]
    ans = []
    for _p, _y in zip(py[0::2], py[1::2]):
        t = "{:06}{:06}".format(_p, p[_p - 1][counter[_p - 1]] + 1)
        ans.append(t)
        counter[_p - 1] += 1
        p[i] = np.argsort(np.argsort(p[i]))
    return "\n".join(ans)


if __name__ == '__main__':
    n, m = map(int, input().split())

    print(solve("{} {}\n".format(n, m) + "\n".join([input() for _ in range(m)])))


### FIXED CODE ###

import time
import numpy as np

# def solve(n, m, py):
"""
n, m = map(int, input().split())
py = [list(map(int, input().split())) for _ in range(m)]
"""

n, m = map(int, input().split())
py = [list(map(int, input().split())) for _ in range(m)]
p = [[] for _ in range(n)]
start = time.time()
for _p, _y in py:
    p[_p - 1].append(_y)
# print(time.time() - start)
for i in range(n):
    p[i] = np.argsort(np.argsort(p[i]))

# print(time.time() - start)
counter = [0 for _ in range(n)]
for _p, _y in py:
    # print("{:06}{:06}".format(_p, p[_p - 1].index(_y) + 1))
    # t = "{:06}{:06}".format(_p, p[_p - 1].index(_y) + 1)
    # print(counter[_y])
    t = "{:06}{:06}".format(_p, p[_p - 1][counter[_p - 1]] + 1)
    print(t)
    counter[_p - 1] += 1
### BUGGY CODE ###

K = int(input())



i = 0
ai = 0
while True:
    ai = (ai * 10 + 7) % K
    i += 1
    if ai == 0:
        break
print(i)

### FIXED CODE ###

K = int(input())

if K % 2 == 0 or K % 5 == 0:
    print(-1)
    exit()

i = 0
ai = 0
while True:
    ai = (ai * 10 + 7) % K
    i += 1
    if ai == 0:
        break
print(i)
### BUGGY CODE ###

s=input()
K=int(input())

N=len(s)
ln=0
siki_sub=''
result={}

for i in range(N):
    for j in range(N-i):
        if ln<K:
            if s[i:i+j+1] not in result:
                result[s[i:i+j+1]]=1
                siki_sub=max(result)
                ln+=1
        else:
            if siki_sub>s[i:i+j+1] and s[i:i+j+1] not in result:
                del result[siki_sub]
                result[s[i:i+j+1]]=1
                siki_sub=max(result)

print(siki_sub)




        

### FIXED CODE ###

s=input()
K=int(input())

N=len(s)
ln=0
siki_sub=''
result={}

for i in range(N):
    for j in range(min(N-i,K+1)):
        if ln<K:
            if s[i:i+j+1] not in result:
                result[s[i:i+j+1]]=1
                siki_sub=max(result)
                ln+=1
        else:
            if siki_sub>s[i:i+j+1] and s[i:i+j+1] not in result:
                del result[siki_sub]
                result[s[i:i+j+1]]=1
                siki_sub=max(result)

print(siki_sub)
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
H = [0] + H
dp = [0] * (N + 1)
dp[1] = 0
dp[2] = abs(H[2] - H[1])

for i in range(3, N+1):
    dp[i] = 1000000000
    for j in range(1, i):
        if i - K <= j:
            dp[i] = min(dp[i], dp[j] + abs(H[i] - H[j]))
print(dp[N])

### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
H = [0] + H
dp = [0] * (N + 1)
dp[1] = 0
dp[2] = abs(H[2] - H[1])

for i in range(3, N+1):
    dp[i] = dp[i - 1] + abs(H[i] - H[i - 1])
    for j in range(1, K + 1):
        if i - j <= 0:
            break
        dp[i] = min(dp[i], dp[i - j] + abs(H[i] - H[i - j]))
print(dp[N])
### BUGGY CODE ###

A,B,C,D = map(int,(input().split()))
count = 0
for i in range(A,B+1):
    if i%C!=0 and i%D!=0:
        count += 1
print(count)


### FIXED CODE ###

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

def main():
    A,B,C,D = map(int,(input().split()))

    A_num = (A-1)//C + (A-1)//D - (A-1)//lcm(C, D)
    B_num = B//C + B//D - B//lcm(C, D)
    return (B-(A-1))-(B_num - A_num)


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

N, M = map(int, input().split())
X = set(range(1,N+1))
for i in range(M):
    L, R = map(int, input().split())
    Y = set(range(L,R+1))
    X = X & Y
print(len(X))


### FIXED CODE ###

N, M = map(int, input().split())

min, max = map(int, input().split())

for i in range(1, M):
    L, R = map(int, input().split())
    if L > max or R < min:
        print(0)
        exit()
    elif min < L <= max:
        min = L
    elif min <= R < max:
        max = R
print(max-min+1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math

N=int(raw_input())

a_num = 1
b_num = 1

for i in xrange(N):
        ratio_a, ratio_b = map(int,raw_input().split())

        base_n = min(math.floor(a_num / ratio_a), math.floor(b_num / ratio_b))

        while a_num > ratio_a * base_n or b_num > ratio_b * base_n:
                base_n += 1

        a_num = ratio_a * base_n
        b_num = ratio_b * base_n

print int(a_num + b_num)

### FIXED CODE ###

# -*- coding: utf-8 -*-

N=int(raw_input())

a_num = 1
b_num = 1

for i in xrange(N):
        ratio_a, ratio_b = map(int,raw_input().split())

        base_n = max( (a_num - 1) // ratio_a + 1 , (b_num - 1 ) // ratio_b + 1)

        a_num = ratio_a * base_n
        b_num = ratio_b * base_n

print int(a_num + b_num)
### BUGGY CODE ###

import itertools

X, Y, Z, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()] 
B = [int(i) for i in input().split()] 
C = [int(i) for i in input().split()] 

A = sorted(A)[::-1][:K]
B = sorted(B)[::-1][:K]
C = sorted(C)[::-1][:K]

T = [A, B]
score = []
for cand in itertools.product(*T):
  score.append(sum(cand))
  
T = [sorted(score)[::-1][:K], C]
res = []
for cand in itertools.product(*T):
  res.append(sum(cand))

res = sorted(res)[::-1][:K]
for i in range(K):
    print(res[i])

### FIXED CODE ###

import itertools

X, Y, Z, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()] 
B = [int(i) for i in input().split()] 
C = [int(i) for i in input().split()] 

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

D = [a+b for a,b in itertools.product(A[:K], B[:K])]
D.sort(reverse=True)

E = [c+d for c,d in itertools.product(C[:K], D[:K])]
E.sort(reverse=True)

for i in range(K):
    print(E[i])
### BUGGY CODE ###

import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
import numpy as np
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()


end = [n]*n

for i in range(min(k, 41)):
    b = [0]*(n+1)
    for i in range(n):
        b[max(i-a[i], 0)] +=1
        if i+a[i] <n:
            b[i+a[i]+1] -=1
    for i in range(1,n):
        b[i] += b[i-1]
    a = b[:n]

for i in range(n):
    print(str(int(a[i]))+" ",end = "" )

### FIXED CODE ###

import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()


end = [n]*n

for i in range(min(k, 41)):
    b = [0]*(n+1)
    for j in range(n):
        b[max(j-a[j], 0)] +=1
        if j+a[j] <n:
            b[j+a[j]+1] -=1
    for j in range(1,n):
        b[j] += b[j-1]
    a = b[:n]

for i in range(n):
    print(str(int(a[i]))+" ",end = "" )
### BUGGY CODE ###

import itertools

N, M, R = map(int, input().split())
r = map(int, input().split())
d = [[0 for j in range(N)] for i in range(N)]

for i in range(N):
    for j in range(N):
        if i == j:
            d[i][j] = 0
        else:
            d[i][j] = float('inf')

for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if d[a][b] > c:
        d[a][b], d[b][a] = c, c

for i in range(N):
    for j in range(N):
        for k in range(N):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = float('inf')
for i in list(itertools.permutations(r)):
    temp = 0
    flag = False
    for j in i:
        if flag:
            temp += d[prev][j - 1]
        else:
            flag = True
        prev = j - 1
    ans = min(ans, temp)

print(ans)


### FIXED CODE ###

from itertools import permutations

def main():
    N, M, R = map(int, input().split())
    r = map(int, input().split())
    inf = float('inf')
    d = [[inf] * N for i in range(N)]

    for i in range(N):
        d[i][i] = 0

    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        if d[a][b] > c:
            d[a][b], d[b][a] = c, c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                temp = d[i][k] + d[k][j]
                if d[i][j] > temp:
                    d[i][j] = temp

    ans = inf
    for i in permutations(r):
        temp = 0
        for j in range(len(i)-1):
            temp += d[i[j] - 1][i[j + 1] - 1]
            if temp > ans:
                break
        if ans > temp:
            ans = temp

    print(ans)


main()
### BUGGY CODE ###

N = int(input())
total = 0
for i in range(1,N+1):
  total += i-1
print(total)

### FIXED CODE ###

N = int(input())
if N == 1:
    print(0)
elif N == 2:
    print(1)
else:
    print((N * (N-1)) // 2)
### BUGGY CODE ###

N = int(input())
alist = list(input().split())
b = alist[0]
n1 = (N -1) // 2
n2 = (N -1) % 2
for i in range(n1):
    b = b + " " + alist[2*i+1]
    b =  alist[2*i+2] + " " + b
if n2 == 1:
    b = b + " " + alist[-1]
    b = b[::-1]
print(b)

### FIXED CODE ###

N = int(input())
alist = list(input().split())
if N % 2 == 0:
    a1 = alist[1::2]
    a2 = alist[0::2]
    a1.reverse()
    a1.extend(a2)
else:
    a1 = alist[0::2]
    a2 = alist[1::2]
    a1.reverse()
    a1.extend(a2)
c = ' '.join(a1)
print(c)
### BUGGY CODE ###

s=[i for i in input()]
#print(s)

for k in range(len(s)):
  if s[k]=='B':
    s[k]=1
  if s[k]=='W':
    s[k]=0

#print(s)
ans=0
for k in range(len(s)):
  if s[k]==0:
    ans+=sum(s[:k])

print(ans)

### FIXED CODE ###

s=[i for i in input()]
#print(s)

cntb=0
cnta=0
for k in range(len(s)):
  if s[k]=='B':
    cntb+=1
  if s[k]=='W':
    cnta+=cntb

print(cnta)
### BUGGY CODE ###

H, W = map( int, input().split())
S = [ input() for _ in range(H)]
T = [ [1]*W for _ in range(H)]
Y = [ [1]*W for _ in range(H) ]
for i in range(H):
    now = 0
    cnt = 0
    for j in range(W):
        if S[i][j] == ".":
            cnt += 1
        else:
            for k in range(now, j):
                T[i][k] = cnt
            cnt = 0
            now = j+1
        if cnt > 0:
            for k in range(now, W):
                T[i][k] = cnt
            
for i in range(W):
    now = 0
    cnt = 0
    for j in range(H):
        if S[j][i] == ".":
            cnt += 1
        else:
            for k in range(now, j):
                Y[k][i] = cnt
            cnt = 0
            now = j+1
        if cnt > 0:
            for k in range(now, H):
                Y[k][i] = cnt

ans = 0
for i in range(H):
    for j in range(W):
        if ans < T[i][j] + Y[i][j]-1:
            ans = T[i][j] + Y[i][j]-1
print(ans)


### FIXED CODE ###

H, W = map( int, input().split())
S = [["#"]*(W+2)]+[ "#"+input()+"#" for _ in range(H)]+ [["#"]*(W+2)]
H += 2
W += 2
L = [[0]*(W+2) for _ in range(H+2)]
R = [[0]*(W+2) for _ in range(H+2)]
D = [[0]*(W+2) for _ in range(H+2)]
U = [[0]*(W+2) for _ in range(H+2)]
cnt = 0

for i in range(1,H-1):
    for j in range(W):
        if S[i][j] == "#":
            cnt = 0
        else:
            cnt += 1
            R[i][j] = cnt
            
for i in range(1,H-1):
    for j in range(W-1,-1,-1):
        if S[i][j] == "#":
            cnt = 0
        else:
            cnt += 1
            L[i][j] = cnt

for j in range(1,W-1):
    for i in range(H):
        if S[i][j] == "#":
            cnt = 0
        else:
            cnt += 1
            D[i][j] = cnt

for j in range(1,W-1):
    for i in range(H-1,-1,-1):
        if S[i][j] == "#":
            cnt = 0
        else:
            cnt += 1
            U[i][j] = cnt

ans = 0
for i in range(1,H-1):
    for j in range(1,W-1):
        if ans < L[i][j] + R[i][j] + U[i][j] + D[i][j]:
            ans =  L[i][j] + R[i][j] + U[i][j] + D[i][j]
print(ans-3)
### BUGGY CODE ###

MOD = 10**9 + 7
N, M = map(int, input().split())
S = [[N+1]*(N+1) for i in [0,1,2]]
T = [[0]*(N+1) for i in [0,1,2]]

C = [0]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())
    l, r = N-r+1, N-l+1
    S[x-1][r] = min(S[x-1][r], l)
    T[x-1][r] = max(T[x-1][r], l)
    C[r] = 1

S0, S1, S2 = S
T0, T1, T2 = T

ok = 1
for i in range(N+1):
    if not T2[i] < S1[i] or not T1[i] < S0[i]:
        ok = 0
        break

if not ok:
    print(0)
    exit(0)

RM = [N+1]*(N+1); GM = [N+1]*(N+1)
for i in range(N-1, -1, -1):
    RM[i] = min(RM[i+1], S1[i+1])
    GM[i] = min(GM[i+1], S0[i+1])


X = {(0, 0): 3}
R = [0]*(N+1); R[0] = 3
G = [0]*(N+1); G[0] = 3
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]

    if C[b+1]:
        Z = [0]*(N+1)
        if t1 <= b < s0:
            for z in range(t2, s1):
                Z[z] = R[z] + G[z]
        for (r, g), v in X.items():
            if not t2 <= r < s1 or not t1 <= g < s0:
                R[r] -= v
                G[g] -= v
        X = {(r, g): v for (r, g), v in X.items() if t2 <= r < s1 and t1 <= g < s0}
    else:
        Z = [R[z] + G[z] for z in range(N+1)]
    if b < GM[b]:
        rm = RM[b]
        for z, v in enumerate(Z):
            if v and z < rm:
                v %= MOD
                X[z, b] = v
                R[z] += v
                G[b] += v
print(sum(X.values()) % MOD)

### FIXED CODE ###

MOD = 10**9 + 7
N, M = map(int, input().split())
S = [[N]*(N+1) for i in [0,1,2]]
T = [[0]*(N+1) for i in [0,1,2]]

C = [0]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())
    S[x-1][r] = min(S[x-1][r], l)
    T[x-1][r] = max(T[x-1][r], l)
    C[r] = 1

S0, S1, S2 = S
T0, T1, T2 = T

ok = 1
for i in range(N+1):
    if not T2[i] < S1[i] or not T1[i] < S0[i]:
        ok = 0
        break

if not ok:
    print(0)
    exit(0)


X = {(0, 0): 3}
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]
    check = lambda r, g: t2 <= r < s1 and t1 <= g < s0

    Z = [0]*(N+1)
    if C[b+1]:
        if t1 <= b < s0:
            for (r, g), v in X.items():
                if t2 <= g < s1:
                    # r <- b+1
                    Z[g] += v
                if t2 <= r < s1:
                    # g <- b+1
                    Z[r] += v
        X = {(r, g): v for (r, g), v in X.items() if t2 <= r < s1 and t1 <= g < s0}
    else:
        Z = [0]*(N+1)
        for (r, g), v in X.items():
            # r <- b+1
            Z[g] += v
            # g <- b+1
            Z[r] += v;
    for z, v in enumerate(Z):
        if v:
            X[z, b] = v % MOD
print(sum(X.values()) % MOD)
### BUGGY CODE ###

from heapq import heappop, heappush
from collections import defaultdict

INF = 10**20
N,M = map(int,input().split(' '))
g = defaultdict(list)
for i in range(2,N+1):
    g[i].append((i-1,0))
for i in range(1,M+1):
    l,r,c = list(map(int,input().split(' ')))
    g[l].append((r,c))

d = [INF] * (N+1)
d[1] = 0
que = []
heappush(que,(1,0))
while que:
    s, dist = heappop(que)
    if d[s] < dist:
        continue
    for t,c in g[s]:
        if d[t] > d[s] + c:
            d[t] = d[s] + c
            heappush(que,(t,d[t]))
if d[N] == INF:
    print(-1)
    exit()
print(d[N])
        



### FIXED CODE ###

import sys
from heapq import heappop, heappush
from collections import defaultdict
input = sys.stdin.buffer.readline

INF = 10**20
N,M = map(int,input().split())
g = defaultdict(list)
for i in range(2,N+1):
    g[i].append((i-1,0))
for i in range(1,M+1):
    l,r,c = list(map(int,input().split()))
    g[l].append((r,c))

d = [INF] * (N+1)
d[1] = 0
que = []
heappush(que,(1,0))
while que:
    s, dist = heappop(que)
    if d[s] < dist:
        continue
    for t,c in g[s]:
        if d[t] > d[s] + c:
            d[t] = d[s] + c
            heappush(que,(t,d[t]))
if d[N] == INF:
    print(-1)
    exit()
print(d[N])
### BUGGY CODE ###

import numpy as np
import heapq
import sys
sys.setrecursionlimit(10**6)

H,W = map(int,input().split())
INF = 10**18
q = []

d = np.full((H,W),INF,dtype=np.int64) # '#'からの距離

for i in range(H):
  txt = input()
  for j,c in enumerate(txt):
    if c == '#':
      d[i,j] = 0
      heapq.heappush(q,(0,i,j))

while q:
  dv,x,y = heapq.heappop(q)
  for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
    xx = x+dx
    yy = y+dy
    if xx == -1 or xx == H:
      continue
    if yy == -1 or yy == W:
      continue
    if d[xx,yy] > dv+1:
      d[xx,yy] = dv+1
      heapq.heappush(q,(dv+1,xx,yy))

ans = d.max()
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
  
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)]

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
### BUGGY CODE ###

import collections

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

INF = 10 ** 20

dp = collections.defaultdict(lambda : INF)
dp[0] = 0

magic = []

for i in range(n):
    magic.append(list(map(int, input().split())))



que = [0]
cc = [0]
while que:
    next_que = set()
    for i in que:
        now_dam = i
        for a, b in magic:
            dam = now_dam + a
            dp[dam] = min([dp[dam], dp[now_dam] + b])
            if dam < h:
                next_que.add(dam)
    que = list(next_que)

ans = INF

for k, v in dp.items():
    if k >= h:
        ans = min([v, ans])

print(ans)

### FIXED CODE ###

def main():
    inf = 10**9
    H, N = map(int, input().split())
    AB = []
    for n in range(N):
        a, b = map(int, input().split())
        AB.append((a, b))
    AB.sort(reverse=True, key=lambda x: x[0])
    dp = [inf] * (H + 10 ** 4)
    dp[0] = 0
    for a, b in AB:
        for h in range(H):
            if dp[h] != inf:
                tmp = dp[h] + b
                if tmp < dp[h + a]:
                    dp[h + a] = tmp
    print(min(dp[H:]))
 
 
main()