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

import numpy as np
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = np.zeros(max(A) + 5)
for i in range(N):
  if ans[A[i]] == 0:
    for j in range(0, max(A) + 5, A[i]):
      ans[j] += 1
  else:
    ans[A[i]] += 1
cnt = 0
for a in A:
  if ans[a] == 1:
    cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
max_A = A[-1] + 1
ans = [0]*max_A
for i in A:
  ans[i] += 1
  if ans[i] == 1:
    for j in range(i*2, max_A, i):
      ans[j] = 2
print(ans.count(1))
### BUGGY CODE ###

import heapq
def main():
    N, M, S = map(int, input().split())
    money_max = 50*N
    S = min(S, money_max-1)
    dp = [[float("inf")]*(money_max) for _ in range(N)]
    dp[0][S] = 0
    G = [[] for _ in range(N)]
    exchange = [None]*N
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u, v = u-1, v-1
        G[u].append([v, a, b])
        G[v].append([u, a, b])
    for i in range(N):
        c, d = map(int, input().split())
        exchange[i] = [c, d]
    q = []
    heapq.heapify(q)
    heapq.heappush(q, [0, 0])
    time_min = [float("inf")]*N
    time_min[0] = 0
    while 0 < len(q):
        pre_time, p = heapq.heappop(q)
        if time_min[p] < pre_time:
            continue
        for i in range(money_max - exchange[p][0]):
            if dp[p][i] < float("inf"):
                dp[p][i+exchange[p][0]] = min(dp[p][i+exchange[p][0]], dp[p][i] + exchange[p][1])
        for to, money, time in G[p]:
            f = False
            for i in range(money, money_max):
                if dp[p][i] < float("inf") and dp[to][i-money] > dp[p][i] + time:
                    f = True
                    break
            if f:
                for i in range(money, money_max):
                    if dp[p][i] < float("inf") and dp[to][i-money] > dp[p][i] + time:
                        dp[to][i-money] = dp[p][i] + time
                        if dp[to][i-money] < time_min[to]:
                            time_min[to] = dp[to][i-money]
                heapq.heappush(q, [time_min[to], to])
    for i in range(1, N):
        print(time_min[i])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import heapq
def main():
    N, M, S = map(int, input().split())
    money_max = 50*N
    S = min(S, money_max)
    dp = [[float("inf")]*(money_max+1) for _ in range(N)]
    dp[0][S] = 0
    G = [[] for _ in range(N)]
    exchange = [None]*N
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u, v = u-1, v-1
        G[u].append([v, a, b])
        G[v].append([u, a, b])
    for i in range(N):
        c, d = map(int, input().split())
        exchange[i] = [c, d]
    q = []
    heapq.heapify(q)
    heapq.heappush(q, [0, 0, S])
    while 0 < len(q):
        pre_time, idx, s = heapq.heappop(q)
        if dp[idx][s] < pre_time:
            continue
        ex = min(s + exchange[idx][0], money_max)
        if dp[idx][s] + exchange[idx][1] < dp[idx][ex]:
            dp[idx][ex] = dp[idx][s] + exchange[idx][1]
            heapq.heappush(q, [dp[idx][ex], idx, ex])
        for to, money, time in G[idx]:
            if money <= s:
                if dp[idx][s] + time < dp[to][s-money]:
                    dp[to][s-money] = dp[idx][s] + time
                    heapq.heappush(q, [dp[to][s-money], to, s-money])
    for i in range(1, N):
        print(min(dp[i]))

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

while True:
  t = []
  try:
    a = int(input())
    for n in range(2,a+1):
      for x in range(2,n):
        if n % x == 0:
          break
      else:
        t.append(n)

    print len(t[0:])
  except EOFError:
    break

### FIXED CODE ###


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/usr/bin/env python
import sys
 
list=1000000*[1]
 
list[0] = 0
list[1] = 0
for i in range(1,1000000):
    if list[i] == 1:
        for j in range(i*i,1000000,i):
            list[j] = 0
 
for i in range(2,1000000):
    list[i] += list[i-1]
     
for line in sys.stdin:
    a = int(line)
    print list[a]
### BUGGY CODE ###

S = input()
list = []
a = 0
for i in range(len(S)):
    list.append(S[i])

while True:
    b = a
    for i in range(len(S)-1):
        if list[i]=='B' and list[i+1]=='W':
            list[i]='W'
            list[i+1]='B'
            a += 1
    if a == b:break
print(a)


### FIXED CODE ###

S = input()
list = []
a,b = 0,0
for i in range(len(S)):
    list.append(S[i])

for i in range(len(list)):
    if list[i]=='W':
        a += i
        a -= b
        b += 1
print(a)
### BUGGY CODE ###

def readinput():
    n,m=list(map(int,input().split()))
    rooms = [
        [[],-1,-1] for _ in range(n)
        ]
    for _ in range(m):
        a,b = list(map(int,input().split()))
        rooms[a-1][0].append(b)
        rooms[b-1][0].append(a)
    return n,m,rooms

def labelNext(target, rooms, nokori, cost):
    oitaList=[]
    idx = list(nokori)
    for ii in idx:
        i = ii-1
        room=rooms[i]
        if (target in room[0]) and (room[1] == -1):
            room[1] = target
            room[2] = cost
            oitaList.append(i+1) # 道しるべをおいた部屋番号のリストにするので+1
    nokori -= set(oitaList)  #　道しるべを置いた部屋番号を削除
    return oitaList

def main(n,m,rooms):
    nokori=set(range(2,n+1))  # 道しるべを置いてない部屋番号の集合 (1を除くすべて)
    target=1
    cost=1
    nextList=labelNext(target,rooms, nokori, cost)
    while(len(nokori)>0):
        cost+=1
        nl=[]
        for n in nextList:
            nl.append(labelNext(n,rooms,nokori,cost))
            if(len(nokori)==0):
                break
        nextList=nl
    labelList=[]
    for room in rooms:
        labelList.append(room[1])   
    labelList.pop(0)     
    return labelList

if __name__=='__main__':
    n,m,rooms=readinput()
    labelList=main(n,m,rooms)
    print('Yes')
    for l in labelList:
        print(l)


### FIXED CODE ###

from collections import deque

WHITE=0
GRAY=1
BLACK=2

nList = []
labelList = []
color = []
Q = deque([])

def readinput():
    global nList
    global color
    global Q
    global labelList

    n,m=list(map(int,input().split()))
    nList = []
    for _ in range(n+1):
        nList.append([])  # 1-オリジンの隣接リスト

    for _ in range(m):
        a,b = list(map(int,input().split()))
        nList[a].append(b)
        nList[b].append(a)

    labelList = [0]*(n+1)
    color = [WHITE]*(n+1)
    Q = deque([])

    #print(nList)

def bfs(p):
    global Q
    global nList
    global color
    global labelList

    Q.append(p)
    color[p]=GRAY
    #print(Q)
    #print(color)
    while(len(Q)>0):
        current=Q.popleft()
        for next in nList[current]:
            if(color[next]==WHITE):
                Q.append(next)
                color[next]=GRAY
                labelList[next]=current
                #print(Q)
                #print(color)
                #print(labelList)
        color[current]=BLACK

def main():

    bfs(1)


if __name__=='__main__':
    readinput()

    main()
    print('Yes')
    for l in labelList[2:]:
        print(l)
### BUGGY CODE ###

N=int(input())
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for i in range(N-1):
    a,b=map(int,input().split())
    branch[a]|={b,}
    branch[b]|={a,}
brack=[float('inf')]*(N+1)
brack[1]=0
check=[(1,{1,}),]
check=deque(check)
while len(check)>0:
    now=check.popleft()
    for i in branch[now[0]]:
        if i in now[1]:
            continue
        if i==N:
            continue
        brack[i]=brack[now[0]]+1
        check.append((i,now[1]|{i,}))
white=[float('inf')]*(N+1)
white[N]=0
check=[(N,{N,}),]
check=deque(check)
while len(check)>0:
    now=check.popleft()
    for i in branch[now[0]]:
        if i in now[1]:
            continue
        if i==1:
            continue
        white[i]=white[now[0]]+1
        check.append((i,now[1]|{i,}))
fennec=0
snuke=0
for i in range(1,N+1):
    if brack[i]<=white[i]:fennec+=1
    elif brack[i]>white[i]:snuke+=1
if fennec>snuke:print('Fennec')
elif fennec<=snuke:print('Snuke')

### FIXED CODE ###

import sys
input=sys.stdin.readline
N=int(input())
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for i in range(N-1):
    a,b=map(int,input().split())
    branch[a]|={b,}
    branch[b]|={a,}
brack=[float('inf')]*(N+1)
brack[1]=0
brack[N]=0
check=deque([1])
while len(check)>0:
    now=check.popleft()
    for i in branch[now]:
        if brack[i]>10**9:
            brack[i]=brack[now]+1
            check.append(i)
white=[float('inf')]*(N+1)
white[N]=0
white[1]=0
check=deque([N])
while len(check)>0:
    now=check.popleft()
    for i in branch[now]:
        if white[i]>10**9:
            white[i]=white[now]+1
            check.append(i)
brack[N]=float('inf')
white[1]=float('inf')
fennec=0
snuke=0
for i in range(1,N+1):
    if brack[i]<=white[i]:fennec+=1
    elif brack[i]>white[i]:snuke+=1
if fennec>snuke:print('Fennec')
elif fennec<=snuke:print('Snuke')
### BUGGY CODE ###

n = int(input())
arr = list(map(int,input().split()))
mul = 1
for i in arr:
    mul *= i
print("-1" if mul > (10**18) else mul)

### FIXED CODE ###

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

if 0 in arr:
    print(0)
else:
    r = 1
    for i in arr:
        if r*i > 10**18:
            print(-1)
            exit()
        r *= i
    print(r)
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    sort_A = sorted(A, reverse=True)


    for _ in range(M):
        sort_A[sort_A.index(max(sort_A))] = max(sort_A) // 2

    print(sum(sort_A))

main()

### FIXED CODE ###

import heapq
def func(n):
    return -n

def main():
    N, M = map(int, input().split())
    A = list(map(func, map(int, input().split())))

    heapq.heapify(A)

    for _ in range(M):
        tmp = -heapq.heappop(A) // 2
        heapq.heappush(A,-tmp)

    print(-sum(A))

main()
### BUGGY CODE ###

def gcd(a, b):
    if b > a:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a


def main():
    from functools import reduce
    from collections import deque

    n, *a = map(int, open(0).read().split())
    p = deque(a)
    edge1 = reduce(gcd, a[1:])
    edge2 = reduce(gcd, a[:-1])
    full = reduce(gcd, a)
    ans = max([edge1, edge2, full])
    gl = p.pop()
    tmp = gl
    for i in range(n - 2):
        tmp2 = p.pop()
        gr = reduce(gcd, p)
        gl = gcd(gl, tmp)
        tmp = tmp2
        g = gcd(gl, gr)
        ans = max(ans, g)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from fractions import gcd

    n, *a = map(int, open(0).read().split())
    a = [0] + a + [0]
    l = [0 for _ in range(n + 1)]
    r = [0 for _ in range(n + 1)]
    tmpl = 0
    tmpr = 0
    for i in range(1,n+1):
        tmpl = gcd(tmpl, a[i-1])
        tmpr = gcd(tmpr, a[-i])
        l[i] = tmpl
        r[-i] = tmpr

    ans = 0
    for i, j in zip(l, r):
        g = gcd(i, j)
        ans = max(ans, g)

    print(ans)


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

import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

S = input()
N = int(S)
num = 2019

d = defaultdict(int)
lenS = len(S)
length = 4
cnt = 0 
for length in range(4, lenS+1):
    for i in range(lenS-length+1):
        subs = int(S[i:i+length])
        if subs%2019==0:
            cnt += 1
#        print('subs:', subs)
#        d[subs] += 1
'''
cnt = 0
i = 1
while 1:
    n = num*i
    if n>N:
        break
    val = d[n]
    cnt += val
    i += 1
'''
print(cnt)



### FIXED CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)

d = defaultdict(int)
d[0] += 1
# nums = [0]*(N+1)
m = 0
last = 0
dd = 1
for i in range(N):
    m += int(S[N-i-1])*dd
    m %= MOD
    # val = (int(S[i])*m + nums[i])%MOD
    # cnt += d[val]
    dd = (dd*10)%MOD
    d[m] += 1

cnt = 0
for i, v in d.items():
    cnt += v*(v-1)//2
print(cnt)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
B = []
for i in range(N):
    temp = A[i]
    A[i] = -999
    print(max(A))
    A[i] = temp


### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
B = sorted(A)

for i in range(N):
    if B[-1] == A[i]:
        print(B[-2])
    else:
        print(B[-1])
### BUGGY CODE ###

n = int(input())

s = {}
for i in range(n):
    temp = input()
    if temp in s:
        s[temp] += 1
    else:
        s[temp] = 1

t = [k for k, v in s.items() if v == max(s.values())]
t.sort()

for i in range(len(t)):
    print(t[i])



### FIXED CODE ###

n = int(input())

s = {}
for i in range(n):
    temp = input()
    if temp in s:
        s[temp] += 1
    else:
        s[temp] = 1



max_s_val = max(s.values())
t = [k for k, v in s.items() if v == max_s_val]
t.sort()

for i in range(len(t)):
    print(t[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

N,K = map(int,input().split())
c = [[0 for _ in range(N)] for _ in range(N)]
c[0][0] = 1
for i in range(N-1):
    for j in range(N):
        if j > 0: c[i+1][j] += c[i][j-1]
        c[i+1][j] += c[i][j]
def f2(n,k):
    return c[n+k-1][k-1]%1000000007
def f(n,k):
    if n-k<0: return 0
    if n==k: return 1
    if k<1: return 0
    return f2(n-k,k)%1000000007

for i in range(1,K+1):
    blue = f(K,i)
    red = f(N-K,i-1)+2*f(N-K,i)+f(N-K,i+1)
    ans=blue*red
    print(int(ans%1000000007))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

N,K = map(int,input().split())
c = [[0 for _ in range(N)] for _ in range(N)]
c[0][0] = 1
for i in range(N-1):
    for j in range(N):
        if j > 0: c[i+1][j] += c[i][j-1]
        c[i+1][j] += c[i][j]
def f2(n,k):
    return c[n+k-1][k-1]%1000000007
def f(n,k):
    if n-k<0: return 0
    if n==k: return 1
    if k<1: return 0
    return f2(n-k,k)%1000000007

for i in range(1,K+1):
    blue = f(K,i)
    red = f(N-K,i-1)+2*f(N-K,i)+f(N-K,i+1)
    ans=blue*red
    print(int(ans%1000000007))
### BUGGY CODE ###

n, k = map(int, input().split())
wlist = []
for i in range(n):
    wlist.append(int(input()))

ma = sum(wlist)
mi = max(wlist)
while (ma - mi > 1 or gobigger != 1):
    mid = (ma + mi)//2
    truck = [0for i in range(k)] ## k개
    i = 0
    gobigger = 0
    for w in wlist:
        if(truck[i] + w <= mid):
            truck[i] = truck[i] + w
        else:
            i = i+1
            if (i == k):
                gobigger = 1
                break
            truck[i] = truck[i] + w
    if (gobigger == 1):
        mi = mid
    else:
        ma = mid
    
print(ma)


### FIXED CODE ###

n, k = map(int, input().split())
wlist = []
for i in range(n):
    wlist.append(int(input()))

ma = sum(wlist) + 1
mi = max(wlist) - 1
while (ma - mi > 1):
    mid = (ma + mi)//2
    truck = [0for i in range(k)] ## k개
    i = 0
    gobigger = 0
    for w in wlist:
        if(truck[i] + w <= mid):
            truck[i] = truck[i] + w
        else:
            i = i+1
            if (i == k):
                gobigger = 1
                break
            truck[i] = truck[i] + w
    if (gobigger == 1):
        mi = mid
    else:
        ma = mid
    
print(ma)
### BUGGY CODE ###

from bisect import bisect_left
a,b,q=map(int,input().split())
s=[]
t=[]
x=[]
s.append(-float("inf"))
t.append(-float("inf"))
for i in range(a):
    s.append(int(input()))
for i in range(b):
    t.append(int(input()))
s.append(float("inf"))
t.append(float("inf"))
for i in range(q):
    x=int(input())
    ans=float("inf")
    tmp_s_1=bisect_left(s,x)-1
    tmp_s_2=tmp_s_1+1
    tmp_s_1_t=bisect_left(t,s[tmp_s_1])
    tmp_s_2_t=bisect_left(t,s[tmp_s_2])
    ans=min(abs(x-s[tmp_s_1])+abs(s[tmp_s_1]-t[tmp_s_1_t-1]), abs(x-s[tmp_s_1])+abs(s[tmp_s_1]-t[tmp_s_1_t]), abs(x-s[tmp_s_2])+abs(s[tmp_s_2]-t[tmp_s_2_t-1]), abs(x-s[tmp_s_2])+abs(s[tmp_s_2]-t[tmp_s_2_t]))
    tmp_t_1=bisect_left(t,x)-1
    tmp_t_2=tmp_t_1+1
    tmp_t_1_s=bisect_left(s,t[tmp_t_1])
    tmp_t_2_s=bisect_left(s,t[tmp_t_2])
    ans=min(ans, abs(x-t[tmp_t_1])+abs(t[tmp_t_1]-s[tmp_t_1_s-1]), abs(x-t[tmp_t_1])+abs(t[tmp_t_1]-s[tmp_t_1_s]), abs(x-t[tmp_t_2])+abs(t[tmp_t_2]-s[tmp_t_2_s-1]), abs(x-t[tmp_t_2])+abs(t[tmp_t_2]-s[tmp_t_2_s]))
    print(ans)

### FIXED CODE ###

from bisect import bisect_left
a,b,q=map(int,input().split())
s=[]
t=[]
x=[]
s.append(-10**12)
t.append(-10**12)
for i in range(a):
    s.append(int(input()))
for i in range(b):
    t.append(int(input()))
s.append(10**12)
t.append(10**12)
for i in range(q):
    x=int(input())
    tmp_s=bisect_left(s,x)-1
    tmp_s_1=s[tmp_s]
    tmp_s_2=s[tmp_s+1]
    tmp_t=bisect_left(t,x)-1
    tmp_t_1=t[tmp_t]
    tmp_t_2=t[tmp_t+1]
    print(min(abs(x-tmp_s_1)+abs(tmp_s_1-tmp_t_1),
    abs(x-tmp_s_1)+abs(tmp_s_1-tmp_t_2),
    abs(x-tmp_s_2)+abs(tmp_s_2-tmp_t_1),
    abs(x-tmp_s_2)+abs(tmp_s_2-tmp_t_2),
    abs(x-tmp_t_1)+abs(tmp_t_1-tmp_s_1),
    abs(x-tmp_t_1)+abs(tmp_t_1-tmp_s_2),
    abs(x-tmp_t_2)+abs(tmp_t_2-tmp_s_1),
    abs(x-tmp_t_2)+abs(tmp_t_2-tmp_s_2)))
### BUGGY CODE ###

N,M,Q = list(map(int,input().split()))
LR = [[] for i in range(N)]
for i in range(M):
    l,r = list(map(int,input().split()))
    LR[l-1].append(["L",i])
    LR[r-1].append(["R",i])

Map = [[0 for j in range(N)] for i in range(N)]

for i in range(N):
    count = 0
    flag = [False for i in range(M)]
    for j in range(i,N):
        for a in LR[j]:
            b,c = a
            if b=="L":
                flag[c]=True
            else:
                if flag[c]:
                    flag[c]=False
                    count+=1
        Map[i][j]=count

for i in range(Q):
    p,q = list(map(int,input().split()))
    print(Map[p-1][q-1])

### FIXED CODE ###

N,M,Q=list(map(int,input().split()))
Map = [[0]*500 for i in range(500)]
for i in range(M):
    l,r=list(map(int,input().split()))
    l,r=l-1,r-1
    Map[r][l]+=1

S = [[0]*501 for i in range(501)]

for i in range(500):
    s=0
    for j in range(500):
        s+=Map[i][j]
        S[i+1][j+1]=S[i][j+1]+s

for i in range(Q):
    p,q = list(map(int,input().split()))
    print(S[q][500]-S[q][p-1])
### BUGGY CODE ###

# setting
from collections import deque

#------------------
# input part
n, m, q = map(int, input().split())

LR = deque()
for i in range(m):
    LR.append(list(map(int, input().split())))

pq = deque()
for i in range(q):
    pq.append(list(map(int, input().split())))
#------------------

#------------------
# proccess part
res = [sum([1 for l,r in LR if l >= p and r <= q]) for p, q in pq]
#------------------

#------------------
# print part
for r in res:
    print(r)
#------------------

### FIXED CODE ###

# setting
from itertools import accumulate

#------------------
n, m, q = map(int, input().split())

LR = [[0 for _ in range(n-i)] for i in range(n)]
for i in range(m):
    l, r = map(int, input().split())
    LR[l-1][r-l] += 1

for i in range(n-2, -1, -1):
    for j, acc in enumerate(accumulate(LR[i])):
        LR[i][j] = acc  + (0 if j == 0 else LR[i+1][j-1])

res = list()
for i in range(q):
    p,q = map(int, input().split())
    res.append(LR[p-1][q-p])

for r in res:
    print(r)
### BUGGY CODE ###

N,M = map(int,input().split())
X = []
for i in range(M):
  L,R = map(int,input().split())
  for j in range (R-L+1):
    A = L + j
    X.append(A)
X_duplicate = [x for x in set(X) if X.count(x) > M-1]
print(len(X_duplicate))

### FIXED CODE ###

N,M = map(int,input().split())
L= 0
R = 10 ** 5
for i in range(M):
  Lm,Rm = map(int,input().split())
  L = max(L,Lm)
  R = min(R,Rm)
if R - L < 0:
  print(0)
else:
  print(R - L + 1)
### BUGGY CODE ###

s = input()
t = input()
ls = len(s)
lt = len(t)

if not set(list(t)) <= set(list(s)):
  print(-1)

else:
  i = 0
  j = 0
  while True:
    if s[i % ls] == t[j]:
      j += 1
    
    if j >= lt:
      break
    
    i += 1

  print(i + 1)



### FIXED CODE ###

import bisect

S = input()
T = input()

ls = len(S)
d = {}
for i, s in enumerate(S):
  if s in d:
    d[s].append(i+1)
  else:
    d[s] = [i+1]


now = 0
ans = 0
pre_t = ''
for t in T:
  if not t in d:
    ans = -1
    break
    
  if t == pre_t:
    idx = bisect.bisect_left(d[t], now+1)
  else:
    idx = bisect.bisect_left(d[t], now)

  if idx == len(d[t]):
    idx = 0
  
  if d[t][idx] > now:
    ans += d[t][idx] - now
  else:
    ans += ls + d[t][idx] - now
  
  now = d[t][idx]
  pre_t = t

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

# https://atcoder.jp/contests/abc153/tasks/abc153_e
# コイン問題の応用で解けそう
# ナップサック解法をあとでちゃんと確認

# INFで初期化したdpテーブルでコイン問題を解いて、ピッタリ勝てないときは最小コストにmin(B)を足す
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, N = read_ints()
A, B = read_col(N, 2)
minb = min(B)
maxa = max(A)
INF = 10**10 + 1

dp = [INF] * (H + 1 + maxa)
dp[0] = 0

for i in range(1, H + 1 + maxa):
    for a, b in zip(A, B):
        if i - a < 0:
            continue
        dp[i] = min(dp[i], dp[i - a] + b)

# if dp[H] < INF:
#     print(dp[H])
#     exit()

print(min(dp[H:]))


### FIXED CODE ###

# https://atcoder.jp/contests/abc153/tasks/abc153_e
# コイン問題の応用で解けそう
# ナップサック解法をあとでちゃんと確認

# INFで初期化したdpテーブルでコイン問題を解いて、ピッタリ勝てないときは最小コストにmin(B)を足す
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, N = read_ints()
A, B = read_col(N, 2)
minb = min(B)
maxa = max(A)
INF = 10**10 + 1

dp = [INF] * (H + 1 + maxa)
dp[0] = 0

for i in range(1, H + 1 + maxa):
    for a, b in zip(A, B):
        if i - a < 0:
            continue
        dp[i] = min(dp[i], dp[i - a] + b)

# if dp[H] < INF:
#     print(dp[H])
#     exit()

print(min(dp[H:]))
### BUGGY CODE ###

import sys
N,K=map(int,sys.stdin.readline().split())
A=sorted([int(e) for e in sys.stdin.readline().split()] for _ in range(N))
x,y=zip(*A)
Y=sorted(y)
r=(x[-1]-x[0])*(Y[-1]-Y[0])
for i in range(N):
 for j in range(i+1,N):
  for k in range(N):
   for l in range(k+1,N):
    ly=Y[k];ry=Y[l];q=(x[j]-x[i])*(ry-ly)
    if r>q and K<=(j-i+1) and K<=sum(ly<=y[z]<=ry for z in range(i,j+1)): r=q
print(r)

### FIXED CODE ###

import sys
N,K=map(int,sys.stdin.readline().split())
A=sorted([int(e) for e in sys.stdin.readline().split()] for _ in range(N))
x,y=zip(*A)
Y=sorted(y)
r=(x[-1]-x[0])*(Y[-1]-Y[0])
for i in range(N):
 for j in range(i+1,N):
  for k in range(N):
   for l in range(k+1,N):
    ly=Y[k];ry=Y[l];q=(x[j]-x[i])*(ry-ly)
    if r>q and K<=(j-i+1) and K<=sum(ly<=y[z]<=ry for z in range(i,j+1)): r=q
print(r)