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

import fractions
import sys

input = sys.stdin.readline

mp = 1000000###max prime
mod = 10 ** 9 + 7
def prime_factorize(n):
    a = [0] * mp
    while n % 2 == 0:
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n] += 1
    return a

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

def fact_mul(x,y):
    ret = [0] * mp
    for i in range(mp):
        ret[i] = x[i] + y[i]
    return ret

def fact_div(x,y):
    ret = [0] * mp
    for i in range(mp):
        ret[i] = x[i] - y[i]
    return ret

def cal_mod(x):
    ret = 1
    for i in range(mp):
        ret *= (i**x[i]) % mod
        ret %= mod
    return ret


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

A_fact = [0] * N###Aの各要素の素因数分解
for i in range(N):
    A_fact[i] = prime_factorize(A[i])
#print(A_fact[0][0:12])

l_fact = A_fact[0][:]

for i in range(1,N):
    for j in range(1,mp):
        l_fact[j] = max(A_fact[i][j],l_fact[j])

B0_fact = [0] * mp


for i in range(mp):
    B0_fact[i] = max(0,l_fact[i]-A_fact[0][i])

ans = cal_mod(B0_fact)
#print(A_fact[0][0:12])
#print(B0_fact[0:12])
#print(cal_mod(l_fact))
#print(ans)
#print(A_fact)
#print(B0_fact)
for i in range(1,N):
    Bi = fact_div(fact_mul(A_fact[0],B0_fact),A_fact[i])
    ans += cal_mod(Bi)
    ans %= mod

print(ans)

### FIXED CODE ###

###提出 #10048385

n = int(input())
a = list(map(int, input().split()))
from fractions import gcd
from functools import reduce
def lcm(x,y):
  return (x*y)//gcd(x,y)
mod = 10**9+7
l = reduce(lcm, a) % mod
ans = 0
for i in range(n):
  ans += l * pow(a[i], mod - 2, mod)
  ans %= mod
print(ans)

#頭良すぎて草
### BUGGY CODE ###

n = int(input())
ls = [int(input()) for i in range(n)]
for j in range(n):
    a = ls[0:j] + ls[j+1:]
    print(max(a))

### FIXED CODE ###

import sys
n = int(input())
ls = [int(input()) for _ in range(n)]
mx = max(ls)
c = ls.count(mx)
new = ls[:]
new.remove(mx)
nx = max(new)
if c > 1:
    for _ in range(n):
        print(mx)
    sys.exit()
for i in ls:
    if i == mx:
        print(nx)
    else:
        print(mx)
### BUGGY CODE ###

import sys
import math
sys.setrecursionlimit(1000000)
mod=1000000007
def power_func(a,b,p):
    """a^b mod p を求める"""
    if b==0: 
        return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1

        
    else:
        calc=K-2
        num-=1
    """
    loop=range(calc,calc-(num-diff),-1)
    for i in loop:
        seki*=i%1000000007
    """
    #"""
    if calc-num>=0:
        #fac=math.factorial(calc-(num-diff))%mod
        #seki*=((math.factorial(calc)%mod)*power_func(fac,mod-2,mod))%mod
        seki=(math.factorial(calc)//math.factorial(calc-num))%mod
        """
        print("debug")
        print(tmp)
        print(calc)
        print(calc-num)
        print(seki)
        """
    else:
        seki=0
    #"""
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%mod
    return seki


N,K=list(map(int,input().split()))
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%mod)

### FIXED CODE ###

import sys
import math
sys.setrecursionlimit(1000000)
mod=1000000007
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1
        loop=range(calc,calc-num,-1)
        for i in loop:
            seki*=i%1000000007

        
    else:
        calc=K-2
        num-=1
        if calc>=num:
            seki=cache[num]
        else:
            print(0)
            exit()

            
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%mod
    return seki


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

if K>2:
    cache=[0 for i in range(K-2)]
    cache[0]=1
    for i in range(1,K-2):
        cache[i]=cache[i-1]*(K-1-i)%mod
    cache.append(cache[-1])
else:
    cache=[1,1]
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%mod)
### BUGGY CODE ###

import sys
from math import sqrt

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
bucket_size = int(sqrt(n))
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l // bucket_size, r, l, i))
LR.sort()
# print(LR)

num = 0
count = [0] * (n + 1)


def add_num(idx):
    global num
    c = C[idx]
    if not count[c]:
        num += 1
    count[c] += 1


def del_num(idx):
    global num
    c = C[idx]
    count[c] -= 1
    if not count[c]:
        num -= 1


# 開区間[nl,nr)で考える
nl, nr = 0, 0
ans = [0] * (q)
preb = -1
for i in range(q):
    b, r, l, idx = LR[i]
    l -= 1
    if preb != b:
        nl, nr = 0, 0
        nl += l
        nr += l
        num = 0
        count = [0] * (n + 1)
    # print(nl, nr, l, r)
    # 区間を広げる時
    while nl > l:
        nl -= 1
        add_num(nl)
    while nr < r:
        add_num(nr)
        nr += 1
    # 区間を狭める時
    while nl < l:
        del_num(nl)
        nl += 1
    while nr > r:
        nr -= 1
        del_num(nr)
    # print("a", num, "idx", idx, "LR", (l, r))
    # print("c", count)
    ans[idx] = num


print(*ans, sep="\n")



### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l, r, i))
LR.sort(key=lambda x: x[1])


BIT = [0] * (n + 1)


def update(idx, val):
    while idx <= n:
        BIT[idx] += val
        idx += idx & (-idx)


def query(idx):
    res = 0
    while idx > 0:
        res += BIT[idx]
        idx -= idx & (-idx)
    return res


pos = [-1] * (n + 1)


def func(idx):
    temp = C[idx]
    if pos[temp] == -1:
        pos[temp] = idx + 1
        update(idx + 1, 1)
    else:
        pre = pos[temp]
        pos[temp] = idx + 1
        update(pre, -1)
        update(idx + 1, 1)


ans = [0] * (q)
idx = 0
for i in range(q):
    l, r, ans_num = LR[i]
    # l,rは0-indexに戻す
    l -= 1
    r -= 1
    while idx < r + 1:  # rになるまで増やす
        if idx < n:  # n超えないように注意
            func(idx)
            idx += 1
        else:
            break
    res = 0
    res += query(r + 1)
    if l > 0:
        res -= query(l)
    ans[ans_num] = res

print(*ans, sep="\n")
### BUGGY CODE ###

x,y,a,b,c=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
ans=0

z=x+y

while(z!=0):
    while((x!=0)and(y!=0)):
            a=[]
            a.append(p[0])
            a.append(q[0])
            a.append(r[0])
            if max(a)==p[0]:
                x-=1
                z-=1
                ans+=p[0]
                p=p[1:]
            elif max(a)==q[0]:
                y-=1
                z-=1
                ans+=q[0]
                q=q[1:]
            else:
                z-=1
                ans+=r[0]
                r=r[1:]
        
    if x==0:
        if q[0]>=r[0]:
            y-=1
            z-=1
            ans+=q[0]
            q=q[1:] 
        else:
            z-=1
            ans+=r[0]
            r=r[1:]
    elif y==0:
        if p[0]>=r[0]:
            x-=1
            z-=1
            ans+=p[0]
            p=p[1:] 
        else:
            z-=1
            ans+=r[0]
            r=r[1:]
print(ans)

### FIXED CODE ###

x,y,a,b,c=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))

p.sort()
q.sort()
r.sort()
ans=0

z=x+y

while(z!=0):
    while((x!=0)and(y!=0)):
            a=[]
            a.append(p[-1])
            a.append(q[-1])
            a.append(r[-1])
            if max(a)==p[-1]:
                x-=1
                z-=1
                ans+=p[-1]
                p.pop()
            elif max(a)==q[-1]:
                y-=1
                z-=1
                ans+=q[-1]
                q.pop()
            else:
                z-=1
                ans+=r[-1]
                r.pop()
            if z==0:
                break
            if  len(r)==0:
                break
    if len(r)==0:
        break
    if z==0:
        break
        
    if x==0:
        if q[-1]>=r[-1]:
            y-=1
            z-=1
            ans+=q[-1]
            q.pop() 
        else:
            z-=1
            ans+=r[-1]
            r.pop()
            
            
    elif y==0:
        if p[-1]>=r[-1]:
            x-=1
            z-=1
            ans+=p[-1]
            p.pop()
        else:
            z-=1
            ans+=r[-1]
            r.pop()

            
            
if len(r)==0:
    while(z!=0):
        while((x!=0)and(y!=0)):
            a=[]
            a.append(p[-1])
            a.append(q[-1])
            if max(a)==p[-1]:
                x-=1
                z-=1
                ans+=p[-1]
                p.pop()
            elif max(a)==q[-1]:
                y-=1
                z-=1
                ans+=q[-1]
                q.pop()
            if z==0:
                break
        if z==0:
            break
        if x==0:
            y-=1
            z-=1
            ans+=q[-1]
            q.pop() 
        else: 
            x-=1
            z-=1
            ans+=p[-1]
            p.pop()
        
        
        
        
        
        
        
        
        
        
        
        
        
print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    A_list = [A for A in input().split()]
    A_list = list(map(int, A_list))
    #print(A_list)
    A_list.sort()
    #print(A_list)
    ans = 1
    for a in A_list :
        ans = ans * a
        if ans == 0 :
            break
    if ans > 10 ** 18 :
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    A_list = [A for A in input().split()]
    A_list = list(map(int, A_list))
    #print(A_list)
    A_list.sort()
    #print(A_list)
    ans = 1
    for a in A_list :
        ans = ans * a
        if ans == 0 :
            break
        elif ans > 10 ** 18 :
            ans = -1
            break

    print(ans)

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

n, p = map(int, input().split())
out=1
tm = int(pow(p, 1/n))
for i in range(2,tm+1):
    if i==2:
        while p%(i**n)==0:
            p = p//(i**n)
            out *= i
            
    elif i%2==1:
        while p%(i**n)==0:
            p = p//(i**n)
            out *= i
            
        if p < i**n:
            break
print(out)

### FIXED CODE ###

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

if n==1:
    print(p)
else:
    out=1
    tm = int(pow(p, 1/n))
    for i in range(2,tm+1):
        while p%(i**n)==0:
            p = p//(i**n)
            out *= i
        if p < i**n:
            break
    print(out)
### BUGGY CODE ###

s = input()
mod_dict = {}

mod_rev = []
for i in range(len(s)-1, -1, -1):
    current_num = int(s[i:len(s)])
    if (current_num%2019 in mod_dict.keys()):
        mod_dict[current_num%2019].append(i)
    else:
        mod_dict[current_num%2019] = [i]

count = 0
for k in mod_dict.keys():
    n = len(mod_dict[k])
    count += int(n*(n-1)/2)
    if (k == 0):
        count += n
print(count)

### FIXED CODE ###

from math import pow
def get_table():
    table = []
    for i in range(10):
        a = int(pow(10, i))
        table.append(a % 2019)
    return table

table = get_table()
# print(table)

def get_power_2019(idx):
    if (idx < len(table)):
        return table[idx]
    else:
        j = int(idx/2)
        i = idx - j
        return (get_power_2019(i) * get_power_2019(j)) % 2019

for i in range(10, 10000):
    curr = get_power_2019(i)
    table.append(curr)

s = input()
mod_dict = {}

last_mod = 0
for i in range(len(s)-1, -1, -1):
    current_lowest_digit = int(s[i])
    current_mod = ((current_lowest_digit * get_power_2019(len(s)-1-i))% 2019 + last_mod) % 2019
    if (current_mod not in mod_dict.keys()):
        mod_dict[current_mod] = [i]
    else:
        mod_dict[current_mod].append(i)
    last_mod = current_mod

# print(mod_dict)

count = 0
for k in mod_dict.keys():
    n = len(mod_dict[k])
    count += int(n*(n-1)/2)
    if (k == 0):
        count += n
print(count)
### BUGGY CODE ###

import math
import string


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


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


def func(x):
    cnt = 0
    while x % 100 == 0:
        cnt += 1
        x /= 100
    return cnt == d


a = []

for i in range(1, 10000000):
    if func(i):
        a.append(i)
print(a[n-1])


### FIXED CODE ###

import math
import string


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


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


def func(x):
    cnt = 0
    while x % 100 == 0:
        cnt += 1
        x /= 100
    return cnt == d


cntcnt = 0

for i in range(1, 10000000):
    if func(i):
        cntcnt += 1
        if cntcnt == n:
            print(i)
            exit()
### BUGGY CODE ###

X, Y = map(int, input().split())


def checkY(N, count, X):
    if count == X and N == 0:
        print("Yes")
        exit(0)
    elif count == X and N != 0:
        return False

    if checkY(N - 2, count + 1, X):
        return True

    if checkY(N - 4, count + 1, X):
        return True

    return False


if checkY(Y, 0, X):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

X, Y = map(int, input().split())

crane = (4 * X - Y) / 2
turtle = (Y - 2 * X) / 2


def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False


if is_integer_num(crane) and crane >= 0 and is_integer_num(turtle) and turtle >= 0:
    print("Yes")

else:
    print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

dp = [float("inf")] * ((1<<n) + 1)
dp[0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c_list = list(map(int, input().split()))
    c = 0
    for j in range(b):
        c += 1 << (c_list[j]-1)

    for j in range(1<<n):
        dp[j | c] = min(dp[j] + a, dp[j | c])


if dp[(1<<n) - 1] == float("inf"):
    ans = -1
else:
    ans = dp[(1<<n) - 1]

print(ans)


### FIXED CODE ###

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

dp = [float("inf")] * ((1<<n) + 1)
dp[0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c_list = list(map(int, input().split()))
    c = 0
    for j in range(b):
        c += 1 << (c_list[j]-1)

    for j in range(1<<n):
        dp[j | c] = min(dp[j] + a, dp[j | c])

if dp[(1<<n) - 1] == float("inf"):
    ans = -1
else:
    ans = dp[(1<<n) - 1]

print(ans)
### BUGGY CODE ###

import bisect
import heapq
N,Q = list(map(int,input().split(" ")))

hitos = []
ans = [-1] * Q
queries =[]
jump = [-1] * Q


for i in range(N):
    S,T,X =list(map(int,input().split(" ")))
    lt = S -X -0.5
    rt = T -X -0.5
    queries.append((lt,rt,X)) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所


queries.sort(key=lambda x:x[2])



for i in range(Q):
    t = int(input())
    hitos.append(t)
for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l)
     rind  = bisect.bisect_left(hitos,r)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:
             temp = jump[lind]
             jump[lind] = rind
             lind = temp

for i  in ans:
    print(i)


### FIXED CODE ###

import bisect
import heapq
import sys
N,Q = [int(x) for x in sys.stdin.readline().split()]

hitos = []
ans = [-1] * Q
queries =[]
jump = [-1] * Q



queries = [[int(x) for x in sys.stdin.readline().split()] for i in range(N)]
hitos = [int(sys.stdin.readline()) for i in range(Q)]


# for i in range(N):
    # S,T,X =list(map(int,input().split(" ")))
    # lt = S -X -0.5
    # rt = T -X -0.5
    # queries.append([lt,rt,X]) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所


queries.sort(key=lambda x:x[2])





for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l-x - 0.5)
     rind  = bisect.bisect_left(hitos,r -x - 0.5)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:
             temp = jump[lind]
             jump[lind] = rind
             lind = temp

for i  in ans:
    print(i)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0]*n
for i in a:
    ans[i-1] += 1
for i in ans:
    print(i)
### BUGGY CODE ###

s = input()
cnt = 0
while cnt < 100000:
    n = len(s)
    s = ''.join(s.split('ST'))
    if len(s) != n:
        cnt += (len(s) - n) // 2
    else:
        break
print(len(s))

### FIXED CODE ###

s = input()
cnt = 0
while cnt < 100000:
    n = len(s)
    s = ''.join(s.split('ST'))
    if len(s) != n:
        cnt += (len(s) - n) // 2
    else:
        break
    i = s.find('ST')
    
    stlen = 0
    if i > 0:
        for j in range(min(i, len(s)-2-i)):
            if s[i-j-1] == 'S' and s[i+j+2] == 'T':
                stlen += 1
            else:
                break
        s = s[:i-stlen] + s[i+stlen+2:]
        cnt += 1 + stlen
print(len(s))
### BUGGY CODE ###

n,m=map(int,input().split())
l = [input().split(" ") for _ in range(m)]
#print(l)

temp=0
wa=0
ac=0
for i in range(n):
    for j in range(m):
        if l[j][0] == str(i+1):
            #print(l[j][0], str(i+1))
            if l[j][1]=='WA':
                temp+=1
            else:
                ac+=1
                wa+=temp
                temp=0
                break

    
print(ac,wa)

### FIXED CODE ###

n, m = map(int, input().split())
l = [tuple(input().split()) for _ in range(m)]
subs = [[] for _ in range(n)]

for i in range(m):
    subs[int(l[i][0])-1].append(l[i][1])

ac, p = 0, 0

for j in range(n):
    if 'AC' in subs[j]:
        ac += 1
        for k in range(len(subs[j])):
                if subs[j][k] == 'WA':
                    p += 1
                else:
                    break

print(ac, p)
### BUGGY CODE ###

n, m, k = map(int, input().split())

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

A, B = [0], [0]

for i in range(n):
    A.append(a[i]+A[i])

for i in range(m):
    B.append(b[i]+B[i])

ans = 0

for i in range(n+1):
    for j in range(m, -1, -1):
        time = A[i]+B[j]
        count = i+j
        if time <= k and count > ans:
            ans = count
            break

print(ans)

### FIXED CODE ###

n, m, k = map(int, input().split())

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

A, B = [0], [0]

for i in range(n):
    A.append(a[i]+A[i])

for i in range(m):
    B.append(b[i]+B[i])

ans = 0
j = m

for i in range(n+1):
    if A[i] > k:
        break
    while (A[i]+B[j]) > k:
        j -= 1
    ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

import itertools

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

# 2a = xk, 2b = ykのとき a+b = (x+y)k/2
# x+yが偶数、すなわちx,yの偶奇が一致するならばa+bはkの倍数となる。他の組合せでも同様
# a,b,cの候補リストを用意して重複順列計算

abc_list = []
for a in range(1, N+1):
    if (2*a)%K == 0:
        abc_list.append(a)

abc_list_even = []
abc_list_odd = []

for a in abc_list:
    if ((2*a)//K)%2 == 0:
        abc_list_even.append(a)
    else:
        abc_list_odd.append(a)


print(len(list(itertools.product(abc_list_even, repeat=3))) + len(list(itertools.product(abc_list_odd, repeat=3))))

### FIXED CODE ###

import itertools

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

# 2a = xk, 2b = ykのとき a+b = (x+y)k/2
# x+yが偶数、すなわちx,yの偶奇が一致するならばa+bはkの倍数となる。他の組合せでも同様
# a,b,cの候補リストを用意して重複順列計算

abc_list_even = []
abc_list_odd = []

for a in range(1, N+1):
    if (2*a)%K == 0:
        if ((2*a)//K)%2 == 0:
            abc_list_even.append(a)
        else:
            abc_list_odd.append(a)

print(len(abc_list_even)**3 + len(abc_list_odd)**3)
### BUGGY CODE ###

from queue import Queue

N, M = [int(n) for n in input().split()]
graph = {n: [] for n in range(1, N+1)}
for m in range(M):
    A, B = [int(n) for n in input().split()]
    graph[A].append(B)
    graph[B].append(A)

starts_ = sorted(graph.keys(), key=lambda x: len(graph[x]))
starts = iter(starts_)

result_path = []
for start in starts:
    q = Queue()
    needs_start = graph[start]
    q.put([start])
    while not q.empty():
        path = q.get()
        for t in graph[path[-1]]:
            if t in path:
                continue
            if len(set(needs_start + graph[t]) - set(path + [t])) == 0:
                result_path = path + [t]
                q = Queue()
                break
            else:
                q.put(path+[t])
                
    if len(result_path) > 0:
        break
print(len(result_path))
result = ""
for r in result_path:
    result += " {}".format(r)
print(result[1:])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
def inpl(): return map(int, input().split())

N, M = inpl()
G = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = inpl()
    G[a].append(b)
    G[b].append(a)

searched = [False] * (N+1)

m = 1
searched[m] = True

ans = []
def dfs(c):
    global ans
    searched[c] = True
    for d in G[c]:
        if not searched[d]:
            ans.append(c)
            dfs(d)
            break 
    else:
        ans.append(c)
    
dfs(1)
ans = ans[:0:-1]
dfs(1)

print(len(ans))
print(*ans)
### BUGGY CODE ###

#!/usr/bin/env python3
#n,p = map(int,input().split())
s=input()
p = 2019
ans = 0
l = [0 for i in range(p)]
l[0] = 1
z = 0
ten = 1
tmp = 0
for i in s[::-1]:
    i = int(i)
    tmp=(tmp+i*ten)%p
    ten = ten*10
    l[tmp]+=1
for i in l:
    ans+= i*(i-1)//2
print(ans)


### FIXED CODE ###

p = 2019
s = input()
n = len(s)
l = [0 for i in range(p)]
l[0] = 1
ten = 1
cnt = 0
 
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    for i in range(n):
        cnt = (cnt + int(s[-i-1]) * ten) % p
        l[cnt] += 1
        ten = (ten * 10) % p
    for i in l:
        if i > 1:
            ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

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

inf = 2**30
dp = [inf] * (H + 1)
dp[0] = 0
for i in range(N):
    A, B = list(map(int, input().split()))
    for j in range(H + 1):
        if dp[j] != inf:
            next = min(H, j + A)
            dp[next] = min(dp[next], dp[j] + B)

print(dp[H])


### FIXED CODE ###

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

inf = 2**30
dp = [inf] * (H + 1)
dp[0] = 0
for i in range(N):
    A, B = list(map(int, input().split()))
    for j in range(H + 1):
        if dp[j] != inf:
            next = min(H, j + A)
            dp[next] = min(dp[next], dp[j] + B)

print(dp[H])