Buggy python submission (verdict: Time Limit Exceeded):
h,n=map(int,input().split())

a=[]
b=[]
INF=10**9
dp=[INF for i in range(h+10**4)]

for i in range(n):
  p,q=map(int,input().split())
  a.append(p)
  b.append(q)

dp[0]=0
for i in range(h):
  if dp[i]==INF:
    continue
  for j in range(n):
    if dp[i+a[j]]>=dp[i]+b[j]:
      dp[i+a[j]]=dp[i]+b[j]
print(min(dp[h:]))

Fixed submission:
h,n=map(int,input().split())

a=[]
b=[]
INF=10**9
dp=[INF for i in range(h+10**4)]

for i in range(n):
  p,q=map(int,input().split())
  a.append(p)
  b.append(q)

dp[0]=0
for i in range(h):
  if dp[i]==INF:
    continue
  for j in range(n):
    if dp[i+a[j]]>=dp[i]+b[j]:
      dp[i+a[j]]=dp[i]+b[j]
print(min(dp[h:]))

Buggy python submission (verdict: Runtime Error):
h,n=map(int,input().split())

a=[]
b=[]
INF=10**9
dp=[INF for i in range(h+1)]

for i in range(n):
  p,q=map(int,input().split())
  a.append(p)
  b.append(q)


for i in range(n):
  if a[i]<=h:
    dp[a[i]]=b[i]
  else:
    dp[h]=min(dp[h],b[i])
    flag=1

if flag==0:
  for i in range(1,h+1):
    if dp[i]==INF:
      #dp[i]=min(dp[i],dp[i-1])
      #print(dp)
      continue
    for j in range(n):
      if i+a[j]<=h:
        dp[i+a[j]]=min(dp[i+a[j]],dp[i]+b[j])
        #print(dp)
      else:
        dp[h]=min(dp[h],dp[i]+b[j])
        #print(dp)
    #dp[i]=min(dp[i],dp[i-1])
    #print(dp)
print(dp[h])

Fixed submission:
h,n=map(int,input().split())

a=[]
b=[]
INF=10**9
dp=[INF for i in range(h+10**4)]

for i in range(n):
  p,q=map(int,input().split())
  a.append(p)
  b.append(q)

dp[0]=0
for i in range(h):
  if dp[i]==INF:
    continue
  for j in range(n):
    if dp[i+a[j]]>=dp[i]+b[j]:
      dp[i+a[j]]=dp[i]+b[j]
print(min(dp[h:]))

Buggy python submission (verdict: Runtime Error):
h,n=map(int,input().split())
hp=h
a=[]
b=[]
INF=10**9
dp=[INF for i in range(h+1)]

for i in range(n):
  p,q=map(int,input().split())
  a.append(p)
  b.append(q)

for i in range(n):
  dp[a[i]]=b[i]
  #print(dp)
for i in range(1,h+1):
  if dp[i]==INF:
    #dp[i]=min(dp[i],dp[i-1])
    #print(dp)
    continue
  for j in range(n):
    if i+a[j]<=h:
      dp[i+a[j]]=min(dp[i+a[j]],dp[i]+b[j])
      #print(dp)
    else:
      dp[h]=min(dp[h],dp[i]+b[j])
      #print(dp)
  #dp[i]=min(dp[i],dp[i-1])
  #print(dp)
print(dp[h])
    

Fixed submission:
h,n=map(int,input().split())

a=[]
b=[]
INF=10**9
dp=[INF for i in range(h+10**4)]

for i in range(n):
  p,q=map(int,input().split())
  a.append(p)
  b.append(q)

dp[0]=0
for i in range(h):
  if dp[i]==INF:
    continue
  for j in range(n):
    if dp[i+a[j]]>=dp[i]+b[j]:
      dp[i+a[j]]=dp[i]+b[j]
print(min(dp[h:]))

Buggy python submission (verdict: Runtime Error):
h,n=map(int,input().split())
hp=h
a=[]
b=[]
INF=10**9
dp=[INF for i in range(h+1)]

for i in range(n):
  p,q=map(int,input().split())
  a.append(p)
  b.append(q)

for i in range(n):
  dp[a[i]]=b[i]
  #print(dp)
for i in range(1,h+1):
  if dp[i]==INF:
    #dp[i]=min(dp[i],dp[i-1])
    #print(dp)
    continue
  for j in range(n):
    if i+a[j]<=h:
      dp[i+a[j]]=min(dp[i+a[j]],dp[i]+b[j])
      #print(dp)
    else:
      dp[h]=min(dp[h],dp[i]+b[j])
      #print(dp)
  #dp[i]=min(dp[i],dp[i-1])
  #print(dp)
print(dp[h])
    

Fixed submission:
h,n=map(int,input().split())

a=[]
b=[]
INF=10**9
dp=[INF for i in range(h+10**4)]

for i in range(n):
  p,q=map(int,input().split())
  a.append(p)
  b.append(q)

dp[0]=0
for i in range(h):
  if dp[i]==INF:
    continue
  for j in range(n):
    if dp[i+a[j]]>=dp[i]+b[j]:
      dp[i+a[j]]=dp[i]+b[j]
print(min(dp[h:]))