Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]

for _ in range(K):
    x = queue.pop(0)
    xmod = x % 10
    if xmod != 0:
        queue.append(10 * x + xmod - 1)
    queue.append(10 * x + xmod)
    if xmod != 9:
        queue.append(10 * x + xmod + 1)
print(x)

Fixed submission:
from collections import deque
K = int(input())

q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

for _ in range(K):
    x = q.popleft()
    xmod = x % 10
    if xmod != 0:
        q.append(10 * x + xmod - 1)
    q.append(10 * x + xmod)
    if xmod != 9:
        q.append(10 * x + xmod + 1)
print(x)

Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]

for _ in range(K):
    x = queue.pop(0)
    if x % 10 != 0:
        queue.append(10 * x + x % 10 - 1)
    queue.append(10 * x + x % 10)
    if x % 10 != 9:
        queue.append(10 * x + x % 10 + 1)

print(x)

Fixed submission:
from collections import deque
K = int(input())

q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

for _ in range(K):
    x = q.popleft()
    xmod = x % 10
    if xmod != 0:
        q.append(10 * x + xmod - 1)
    q.append(10 * x + xmod)
    if xmod != 9:
        q.append(10 * x + xmod + 1)
print(x)

Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]

c = 0
while c < K: 
    x = queue.pop(0)
    if x % 10 != 0:  
        queue.append(10 * x + x % 10 - 1)
    queue.append(10 * x + x % 10) 
    if x % 10 != 9:
        queue.append(10 * x + x % 10 + 1)
    c += 1

print(x)

Fixed submission:
from collections import deque
K = int(input())

q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

for _ in range(K):
    x = q.popleft()
    xmod = x % 10
    if xmod != 0:
        q.append(10 * x + xmod - 1)
    q.append(10 * x + xmod)
    if xmod != 9:
        q.append(10 * x + xmod + 1)
print(x)
Buggy python submission (verdict: Runtime Error):
N, A, B = map(int, input().split())
 
rep = "b" * A + "r" * B
C = N // (A + B)
D = N % (A + B)
 
ans = A * C + min(A, D)
print(ans)

Fixed submission:
N, A, B = map(int, input().split())

C = N // (A + B)
D = N % (A + B)

ans = A * C + min(A, D)
print(ans)

Buggy python submission (verdict: Runtime Error):
N, A, B = map(int, input().split())

rep = "b" * A + "r" * B
C = N // (A + B)
D = N % (A + B)

ans = A * C + min(A, D)
print(ans)

Fixed submission:
N, A, B = map(int, input().split())

C = N // (A + B)
D = N % (A + B)

ans = A * C + min(A, D)
print(ans)

Buggy python submission (verdict: Runtime Error):
N, A, B = map(int, input().split())

rep = "b" * A + "r" * B
C = N // (A + B)
D = N % (A + B)

if D == 0:
    ans = A * C
else:
    ans = A * C + rep[:D].count("b")
print(ans)

Fixed submission:
N, A, B = map(int, input().split())

C = N // (A + B)
D = N % (A + B)

ans = A * C + min(A, D)
print(ans)

Buggy python submission (verdict: Runtime Error):
N, A, B = map(int, input().split())

rep = "b" * A + "r" * B
C = N // (A + B)
D = N % (A + B)

ans = A * C + rep[:D].count("b")
print(ans)

Fixed submission:
N, A, B = map(int, input().split())

C = N // (A + B)
D = N % (A + B)

ans = A * C + min(A, D)
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())

graph = [[] for i in range(N)]

for i in range(N -1):
    a, b = map(int, input().split())
    graph[a-1].append((b, i))
    graph[b-1].append((a, i))

print(graph)
ans = [0] * (N -1)


def dfs(past, now, color):
    new_color = 1
    for future, edge in graph[now - 1]:
        if future == past:
            pass
        else:
            if new_color == color:
                new_color += 1
            ans[edge] = new_color
            dfs(now, future, new_color)
            new_color += 1

dfs(-1, 1, -1)

print(max(ans))
for i in ans:
    print(i)

Fixed submission:
S = input()

days = ["SUN","MON","TUE","WED","THU","FRI","SAT"]

for i in range(7):
    if days[i] == S:
        print(7 - i)
        break
Buggy python submission (verdict: Runtime Error):
N = int(input())

graph = [[] for i in range(N)]

for i in range(N -1):
    a, b = map(int, input().split())
    graph[a-1].append((b, i))
    graph[b-1].append((a, i))

ans = [0] * (N -1)


def dfs(past, now, color):
    new_color = 1
    for future, edge in graph[now - 1]:
        if future == past:
            pass
        else:
            if new_color == color:
                new_color += 1
            ans[edge] = new_color
            dfs(now, future, new_color)
            new_color += 1

dfs(-1, 1, -1)

print(max(ans))
for i in ans:
    print(i)

Fixed submission:
import sys
sys.setrecursionlimit(10**9)

N = int(input())

graph = [[] for i in range(N)]

for i in range(N - 1):
    a, b = map(int, input().split())
    graph[a - 1].append((b,i))
    graph[b - 1].append((a,i))

ans = [0] * (N - 1)


def dfs(past, now, color):
    new_color = 1
    for future, edge in graph[now - 1]:
        if future == past:
            pass
        else:
            if new_color == color:
                new_color += 1
            ans[edge] = new_color
            dfs(now, future, new_color)
            new_color += 1


dfs(-1, 1, -1)

print(max(ans))
for i in ans:
    print(i)

Buggy python submission (verdict: Runtime Error):
N = int(input())

graph = [[] for i in range(N)]

for i in range(N -1):
    a, b = map(int, input().split())
    graph[a-1].append((b, i))
    graph[b-1].append((a, i))

print(graph)
ans = [0] * (N -1)


def dfs(past, now, color):
    new_color = 1
    for future, edge in graph[now - 1]:
        if future == past:
            pass
        else:
            if new_color == color:
                new_color += 1
            ans[edge] = new_color
            dfs(now, future, new_color)
            new_color += 1

dfs(-1, 1, -1)

print(max(ans))
for i in ans:
    print(i)

Fixed submission:
import sys
sys.setrecursionlimit(10**9)

N = int(input())

graph = [[] for i in range(N)]

for i in range(N - 1):
    a, b = map(int, input().split())
    graph[a - 1].append((b,i))
    graph[b - 1].append((a,i))

ans = [0] * (N - 1)


def dfs(past, now, color):
    new_color = 1
    for future, edge in graph[now - 1]:
        if future == past:
            pass
        else:
            if new_color == color:
                new_color += 1
            ans[edge] = new_color
            dfs(now, future, new_color)
            new_color += 1


dfs(-1, 1, -1)

print(max(ans))
for i in ans:
    print(i)
Buggy python submission (verdict: Runtime Error):
import re

S = input()

a = [-1] * (len(S) + 1)

zero_pos = []
if S[0] == "<":
    zero_pos.append(0)
    a[0] = 0
if S[-1] == ">":
    zero_pos.append(len(S) + 1)
    a[-1] = 0
for i in range(len(S)):
    if S[i:i+2] == "><":
        zero_pos.append(i + 1)
        a[i + 1] = 0

for j in zero_pos:
    if j == len(S):
        a[j + 1] = 1
    elif j > len(S):
        continue
    elif j == len(S) - 1:
        a[-1] = 1
    elif j == 0:
        v = 0
        while S[j + 1] == "<":
            a[j + 1] = v + 1
            j += 1
            v += 1
    else:
        v = 0
        while S[j + 1] == "<":
            a[j + 1] = v + 1
            j += 1
            v += 1
        a[j + 1] = v + 1

for k in zero_pos:
    if k == 0:
        continue
    elif k == len(S) + 1:
        v = 0
        while S[k - 2] == ">":
            a[k - 2] = v + 1
            k -= 1
            v += 1
    else:
        v = 0
        while a[k - 1] == -1:
            a[k - 1] = v + 1
            k -= 1
            v += 1

sum = 0
for m in a:
    sum += int(m)
print(sum)






Fixed submission:
S = input()

a = [-1] * (len(S) + 1)

# find zero positions
if S[0] == "<":
    a[0] = 0

if S[-1] == ">":
    a[-1] = 0

for i in range(len(S)):
    if S[i:i+2] == "><":
        a[i + 1] = 0

for i in range(len(S)):
    if S[i] == "<":
        a[i + 1] = a[i] + 1

for i in reversed(range(len(S))):
    if S[i] == ">" and a[i + 1] >= 0:
        a[i] = max(a[i], a[i + 1] + 1)

print(sum(a))
Buggy python submission (verdict: Runtime Error):
import math
a,b,x = map(int, input().split())

if x >= (a * a * b) / 2:
	c = 2 * b - (2 * x) / (a * a)
	angle = math.degrees(math.atan(c / a))
else:
	d = x / (a * b)
	angle = math.degrees(math.atan(b / d))
print(angle)


Fixed submission:
a = int(input())

dif = a
half = int(a / 2)
for i in range(1,half+1):
	if i <= a / i:
		if a % i == 0:
			div1 = int(i)
			div2 = int(a / i)
			continue
	else:
		break
print(div1 + div2 -2)
Buggy python submission (verdict: Time Limit Exceeded):
k, s = map(int, input().split())

sum_set = []
for i in range(k + 1):
    for j in range(k + 1):
        m = s - i - j
        if 0 <= m <= k:
            comb = [i, j, m]
            sum_set.append(comb)
        else:
            continue
print(len(sum_set))


Fixed submission:
k, s = map(int, input().split())

count = 0
for i in range(k + 1):
    for j in range(k + 1):
        m = s - i - j
        if 0 <= m <= k:
            count += 1
print(count)

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

sum_set = []
for i in range(k + 1):
    for j in range(k + 1):
        m = s - i - j
        if 0 <= m <= k:
            comb = [i, j, m]
            sum_set.append(comb)
print(len(sum_set))


Fixed submission:
k, s = map(int, input().split())

count = 0
for i in range(k + 1):
    for j in range(k + 1):
        m = s - i - j
        if 0 <= m <= k:
            count += 1
print(count)

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

sum_set = []
for i in range(k + 1):
    for j in range(k + 1):
        for m in range(k + 1):
            if i + j + m == s:
                comb = [i, j, m]
                sum_set.append(comb)
                break
        else:
            continue
print(len(sum_set))

Fixed submission:
k, s = map(int, input().split())

count = 0
for i in range(k + 1):
    for j in range(k + 1):
        m = s - i - j
        if 0 <= m <= k:
            count += 1
print(count)

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

sum_set = []
for i in range(k + 1):
    for j in range(k + 1):
        for m in range(k + 1):
            if i + j + m == s:
                comb = [i, j, m]
                sum_set.append(comb)
                break
print(len(sum_set))


Fixed submission:
k, s = map(int, input().split())

count = 0
for i in range(k + 1):
    for j in range(k + 1):
        m = s - i - j
        if 0 <= m <= k:
            count += 1
print(count)

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

sum_set = []
for i in range(k + 1):
    for j in range(k + 1):
        for m in range(k + 1):
            if i + j + m == s:
                comb = [i, j, m]
                sum_set.append(comb)
print(len(sum_set))

Fixed submission:
k, s = map(int, input().split())

count = 0
for i in range(k + 1):
    for j in range(k + 1):
        m = s - i - j
        if 0 <= m <= k:
            count += 1
print(count)
Buggy python submission (verdict: Runtime Error):
n = input()
print(n*n*n)


Fixed submission:
n = int(input())
print(n*n*n)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, raw_input().split())

ans = 0
for i in range(1, N+1):
    for j in range(1, N+1):
       if i % j >= K:
           ans += 1

print ans


Fixed submission:
import sys

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

if K == 0:
    print N * N
    sys.exit()

ans = 0
for i in range(K + 1, N+1):
    ans += max(N % i - K + 1, 0) + (N / i) * (i - K)


print ans
Buggy python submission (verdict: Runtime Error):
import math
m, n = map(int, input().split())
li = input().split()
res=[]
for i in li:
    res.append(int(i))

res.sort(reverse=True)

while n != 0:
    res.pop(0)
    n -= 1

print(sum(res))


Fixed submission:
m, n = map(int, input().split())
li = list(map(int, input().split()))
if n >= m:
  print(0)
elif n == 0:
  print(sum(li))
else:
  print(sum(sorted(li)[:-n]))
Buggy python submission (verdict: Runtime Error):
a, b = map(int,input.split())
if a == b:
  print("Yes")
  else:
    print("No")

Fixed submission:
a, b = map(int, input().split())
if a == b:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())

tmp_dict = {} # 作業辞書
result_dict = {} # 結果辞書
for i in range(M):
  quiz, res = input().split()	
  
  if quiz not in tmp_dict: # 作業辞書になければ作成
    if quiz not in result_dict: # 結果辞書にもなければ作成
      tmp_dict[quiz] = 0
    
  if res == "AC": # 正解
    wa_count = tmp_dict.pop(quiz)
    result_dict[quiz] = wa_count
    tmp_dict[quiz] = "ok"

  if res == "WA": # 間違い
    if tmp_dict[quiz] != "ok":
      tmp_dict[quiz] += 1


print(len(result_dict), sum(result_dict.values()))

Fixed submission:
def main():
    N, M = map(int, input().split())
    ans = [False for _ in range(N)]
    wa_list = [0 for _ in range(N)]
    ac = 0
    wa = 0
    for _ in range(M):
        i, result = input().split()
        i = int(i)
        if result == "AC":
            if ans[i-1] == False:
                ac += 1
                ans[i - 1] = True
                wa += wa_list[i-1]
        else:
            if ans[i - 1] == False:
                wa_list[i - 1] += 1
    if sum(ans) == 0:
        wa = 0
    print(ac, wa)
    return 0
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
tmp = input().split()
N = int(tmp[0])
M = int(tmp[1])

quiz_dict = {}
wa_dict = {}
 
for i in range(M):
  tmp = input().split()
  
  quiz = tmp[0]
  res = tmp[1]
  
  if quiz not in quiz_dict:
    quiz_dict[quiz] = 0
  
  if quiz not in wa_dict: 
    wa_dict[quiz] = 0
  
  if res == "AC":
    quiz_dict[quiz] = 1
  if res == "WA":
    if quiz_dict[quiz] == 0:
      wa_dict[quiz] += 1



tmp_list = [k for k, v in quiz_dict.items() if v > 0] 


def filter_dict(f, d):
  return {k:v for k,v in d.items() if f(k,v)}

a = len(filter_dict(lambda k,v: v==1, quiz_dict))
tmp = filter_dict(lambda k,v: k in tmp_list, wa_dict)
wa_n = sum(tmp.values())

print(a, wa_n)

Fixed submission:
def main():
    N, M = map(int, input().split())
    ans = [False for _ in range(N)]
    wa_list = [0 for _ in range(N)]
    ac = 0
    wa = 0
    for _ in range(M):
        i, result = input().split()
        i = int(i)
        if result == "AC":
            if ans[i-1] == False:
                ac += 1
                ans[i - 1] = True
                wa += wa_list[i-1]
        else:
            if ans[i - 1] == False:
                wa_list[i - 1] += 1
    if sum(ans) == 0:
        wa = 0
    print(ac, wa)
    return 0
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
a,b = map(int, input().sprit())
if a < b:
  print(0)
else:
  print(10)

Fixed submission:
a,b = map(int, input().split())
if a < b:
  print(0)
else:
  print(10)
Buggy python submission (verdict: Time Limit Exceeded):
times = int(input())
nums = list(map(int, input().split()))

re = 10**100000000
for i in range(times):
    sum_left = sum(nums[:i+1])
    sum_right = sum(nums[i+1:])
    re = min(re, abs(sum_left - sum_right))
print(re)

Fixed submission:
times = int(input())
nums = list(map(int, input().split()))

re = 10**100000
for i in range(times):
    sum_left = sum(nums[:i+1])
    sum_right = sum(nums[i+1:])
    re = min(re, abs(sum_left - sum_right))
print(re)
Buggy python submission (verdict: Time Limit Exceeded):
# ABC 051 B Sum of Three Integers

k, s = map(int, input().split())

res = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                res += 1

print(res)

Fixed submission:
# ABC 051 B Sum of Three Integers

k, s = map(int, input().split())

res = 0

for x in range(k+1):
    for y in range(k+1):
        if 0 <= s-x-y <= k:
            res += 1
    
    
print(res)
Buggy python submission (verdict: Runtime Error):
import math
a, b, x = map(int, input().split())

half = a * a * b / 2
theta = 0.
if half < x:
    temp = a*a*b-x
    temp = temp * 2 / (a*a*a)
    theta = math.atan(temp)
else:
    temp = a*b*b/2/x
    theta = math.atan(temp)

res = theta * 180 / math.acos(-1)
print(f'{res:.10f}')


Fixed submission:
import math

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

half = a * a * b / 2
theta = 0.
if half < x:
    temp = a*a*b-x
    temp = temp * 2 / (a*a*a)
    theta = math.atan(temp)
else:
    temp = a*b*b/2/x
    theta = math.atan(temp)

res = theta * 180 / math.acos(-1)
print('{:.10f}'.format(res))
Buggy python submission (verdict: Runtime Error):
// Last Change: 08/18/2019 21:25:06.
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

int main() {
  ll N;
  cin >> N;
  vector<double> v(N);
  for (auto &&e : v) {
    cin >> e;
  }
  sort(v.begin(), v.end());
  double ans = v[0];
  for (ll i = 1; i < N; ++i) {
    ans = (ans + v[i]) / 2;
  }
  cout << ans << endl;
}



Fixed submission:
N=int(input())
v = list(map(float,input().split(' ')))
v.sort()

ans = v[0]
for i in range(N-1):
   ans = (ans+v[i+1])/2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = map(int, input().split())
mp = {}

def ipt():
    for x in range(H):
        A = list(map(int, input().split()))
        for y in range(W):
            mp[A[y]] = (x, y)


ipt()
Q = int(input())

def get_dist(prev, x):
    dx = mp[x][0] - mp[prev][0]
    dy = mp[x][1] - mp[prev][1]
    return abs(dx) + abs(dy)


for i in range(Q):
    L, R = map(int, input().split())
    ans = 0
    for x in range(L, R, D):
        ans += get_dist(x, x+D)
    print(ans)

Fixed submission:
H, W, D = map(int, input().split())
mp = {}

def ipt():
    for x in range(H):
        A = list(map(int, input().split()))
        for y in range(W):
            mp[A[y]] = (x, y)


ipt()
Q = int(input())

def get_dist(prev, x):
    dx = mp[x][0] - mp[prev][0]
    dy = mp[x][1] - mp[prev][1]
    return abs(dx) + abs(dy)


dist = [0 for i in range(H*W+1)]
for i in range(0, D):
    tmp = 0
    for x in range(1+i, H*W-D+1, D):
        tmp += get_dist(x, x+D)
        dist[x+D] = tmp


for i in range(Q):
    L, R = map(int, input().split())
    print(dist[R]-dist[L])
Buggy python submission (verdict: Time Limit Exceeded):
k=int(input())
num=0

while k>0:
  num+=1
  snum=str(num)
  flg=0
  for i in range(0,len(snum)-1):
    if abs(int(snum[-1-i])-int(snum[-2-i]))>1:  
      flg=1
      break
  if flg==0:
    k-=1
print(num)

Fixed submission:
k=int(input())
num=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]
keta=0
for i in range(0,k):
  for j in range(0,len(num)-1):
    if num[j]==-1:
      num[j]=1
      keta=j
      break
    elif num[j]!=9 and (num[j+1]==-1 or (num[j]-num[j+1])<1):
      num[j]+=1
      break
  for x in range(j-1,-1,-1):
    num[x]=max(0,num[x+1]-1)

for i in range(keta,-1,-1):
  print(num[i],end='')
print()

Buggy python submission (verdict: Runtime Error):
k=int(input())
num=0

while k>0:
  num+=1
  snum=str(num)
  flg=0
  for i in range(0,len(snum)-1):
    if abs(int(snum[i])-int(snum[i+i]))>1:
      flg=1
      break
  if flg==0:
    k-=1
print(num)

Fixed submission:
k=int(input())
num=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]
keta=0
for i in range(0,k):
  for j in range(0,len(num)-1):
    if num[j]==-1:
      num[j]=1
      keta=j
      break
    elif num[j]!=9 and (num[j+1]==-1 or (num[j]-num[j+1])<1):
      num[j]+=1
      break
  for x in range(j-1,-1,-1):
    num[x]=max(0,num[x+1]-1)

for i in range(keta,-1,-1):
  print(num[i],end='')
print()
Buggy python submission (verdict: Runtime Error):
lis = list(map(int,input().split()))
if lis[0]+lis[1]>lis[2]+lis[3]:
  print("Left")
else if lis[0]+lis[1]<lis[2]+lis[3]:
  print("Right")
else:
  print("Balanced")

Fixed submission:
lis = list(map(int,input().split()))
if lis[0]+lis[1]>lis[2]+lis[3]:
  print("Left")
elif lis[0]+lis[1]<lis[2]+lis[3]:
  print("Right")
else:
  print("Balanced")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(20000)

H,N = map(int,input().split())
magic = []
for i in range(N):
    a,b = map(int,input().split())
    magic.append([a,b])

INF = 100000000000
DP_list = [INF]*(20010)
def DP(h):
    ans = INF
    if h <= 0:
        return 0
    elif DP_list[h] != INF:
        return DP_list[h]
    else:
        for i in range(N):
            k = magic[i][1] + DP(h - magic[i][0])
            ans = min(ans,k)
        DP_list[h] = ans
        return ans

print(DP(H))

Fixed submission:
H,N = map(int,input().split())
magic = []
for i in range(N):
    a,b = map(int,input().split())
    magic.append([a,b])

INF = 10**9
DP = [INF]*(20005); DP[0] = 0

for i in range(1,20005):
    h = INF
    for j in range(N):
        if i - magic[j][0] >= 0:
            k = magic[j][1] + DP[i - magic[j][0]]
        else:
            k = magic[j][1]
        h = min(h,k)
    DP[i] = h

ans = DP[H]
for i in DP[H+1:]:
    ans = min(ans,i)
print(ans)

Buggy python submission (verdict: Runtime Error):
H,N = map(int,input().split())
magic = []
for i in range(N):
    a,b = map(int,input().split())
    magic.append([a,b])

INF = 100000000000
DP_list = [INF]*(H+20001)
def DP(h):
    ans = INF
    if h <= 0:
        return 0
    elif DP_list[h] != INF:
        return DP_list[h]
    else:
        for i in range(N):
            k = magic[i][1] + DP(h - magic[i][0])
            ans = min(ans,k)
        DP_list[h] = ans
        return ans

print(DP(H))

Fixed submission:
H,N = map(int,input().split())
magic = []
for i in range(N):
    a,b = map(int,input().split())
    magic.append([a,b])

INF = 10**9
DP = [INF]*(20005); DP[0] = 0

for i in range(1,20005):
    h = INF
    for j in range(N):
        if i - magic[j][0] >= 0:
            k = magic[j][1] + DP[i - magic[j][0]]
        else:
            k = magic[j][1]
        h = min(h,k)
    DP[i] = h

ans = DP[H]
for i in DP[H+1:]:
    ans = min(ans,i)
print(ans)

Buggy python submission (verdict: Runtime Error):
H,N = map(int,input().split())
magic = []
for i in range(N):
    a,b = map(int,input().split())
    magic.append([a,b])

INF = 100000000000
DP_list = [INF]*(H+20001)
def DP(h):
    ans = INF
    if h <= 0:
        return 0
    elif DP_list[h] != INF:
        return DP_list[h]
    else:
        for i in range(N):
            k = magic[i][1] + DP(h - magic[i][0])
            ans = min(ans,k)
        DP_list[h] = ans
        return ans

print(DP(H))

Fixed submission:
H,N = map(int,input().split())
magic = []
for i in range(N):
    a,b = map(int,input().split())
    magic.append([a,b])

INF = 10**9
DP = [INF]*(20005); DP[0] = 0

for i in range(1,20005):
    h = INF
    for j in range(N):
        if i - magic[j][0] >= 0:
            k = magic[j][1] + DP[i - magic[j][0]]
        else:
            k = magic[j][1]
        h = min(h,k)
    DP[i] = h

ans = DP[H]
for i in DP[H+1:]:
    ans = min(ans,i)
print(ans)