Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
S = input().split(" ")
N = int(S[0])
M = int(S[1])


def C(m, n):
    t = m
    s1 = 1
    while t > (m - n):
        s1 = s1 * t
        t = t - 1

    s2 = 1

    t = n
    while t >= 1:
        s2 = s2 * t
        t = t - 1

    return int(s1 / s2)


def A(m, n):
    s = 1
    t = m

    while t > m - n:
        s = s * t
        t = t - 1

    return s


def calculate(maxValue, minValue):
    if maxValue > minValue + 1:
        return 0

    if maxValue == minValue:
        S = A(maxValue,maxValue)
        return  2 * S * S

    return A(maxValue,maxValue) * A(minValue,minValue)

result = calculate(max(N,M),min(N,M))

print(result % 1000000007)

Fixed submission:
S = input().split(" ")
N = int(S[0])
M = int(S[1])


def C(m, n):
    t = m
    s1 = 1
    while t > (m - n):
        s1 = s1 * t
        t = t - 1

    s2 = 1

    t = n
    while t >= 1:
        s2 = s2 * t
        t = t - 1

    return int(s1 / s2)


def A(m, n):
    s = 1
    t = m

    while t > m - n:
        s = (s * t) % 1000000007
        t = t - 1

    return s


def calculate(maxValue, minValue):
    if maxValue > minValue + 1:
        return 0

    if maxValue == minValue:
        S = A(maxValue,maxValue)
        return  2 * S * S

    return A(maxValue,maxValue) * A(minValue,minValue)

result = calculate(max(N,M),min(N,M))

print(result % 1000000007)
Buggy python submission (verdict: Runtime Error):
if b > 0 and d > 0:
    print(max(b*d, a*c))
elif b > 0 and d < 0:
    print(a*d)
elif b < 0 and d > 0:
    print(b*c)
elif b <= 0 and d <= 0:
    print(a*c)

Fixed submission:
a, b, c, d = map(int, input().split())

print(max(a*c, a*d, b*c, b*d))
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(n) for n in input().split()]
ans = 1

A_set = set(A)
A_set = list(A_set)
if len(A_set) == 1:
    print(0)
else:
    for i in range(N):
        for j in range(i):
            if A_set[i] % A_set[j] == 0:
                break
            if j == i-1:
                ans += 1
    print(ans)

Fixed submission:
N = int(input())
A = [int(n) for n in input().split()]
maxA = max(A)

C = {a:0 for a in A}
D = {a:0 for a in A}
for a in A:
    C[a] += 1
for a in A:
    if C[a] > 0:
        t = 2
        while a*t <= maxA:
            D[a*t] = 1
            t += 1
ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(n) for n in input().split()]
ans = 0

for i in range(N):
    for j in range(N):
        if A[i] % A[j] == 0 and i != j:
            break
        if j == N-1:
            ans += 1

print(ans)

Fixed submission:
N = int(input())
A = [int(n) for n in input().split()]
maxA = max(A)

C = {a:0 for a in A}
D = {a:0 for a in A}
for a in A:
    C[a] += 1
for a in A:
    if C[a] > 0:
        t = 2
        while a*t <= maxA:
            D[a*t] = 1
            t += 1
ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = input().split()
for i in range(N):
  count = 0
  for j in range(N-1):
    if i+1 == int(A[j]):
      count += 1
  print(count)


Fixed submission:
import math
R = int(input())
pi = math.pi
print(2*R*pi)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = []
A = input().split()
A = [int(n) for n in A]
for i in range(M):
  N -= A[i]
print(N)
N, M = map(int, input().split())
A = []
A = input().split()
A = [int(n) for n in A]
for i in range(M):
  N -= A[i]
if N >= 0:
  print(N)
else:
  print("-1")


Fixed submission:
N, M = map(int, input().split())
A = []
A = input().split()
A = [int(n) for n in A]
for i in range(M):
  N -= A[i]
if N >= 0:
  print(N)
else:
  print("-1")
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(M, m):
	a = max(M, m)
	b = min(M, m)
	q = b
	r = a % b
	while r != 0:
		p = q
		q = r
		r = p % q
	return q
	
K = int(input())
count = 0
temp = []
for a in range(1, K+1):
	for b in range(1, a):
		temp.append(gcd(a, b))
for c in range(1, K+1):
	for j in range(len(temp)):
		count += gcd(c, temp[j]) * 2
	for k in range(1, K+1):
		count += gcd(c, k)
print(count)

Fixed submission:
def gcd(a, b):
  if a < b:
    a_init = a
    a = b
    b = a_init
  while b != 0:
    r = a % b
    a = b
    b = r
  return a
	
K = int(input())
count = 0
temp = []
for a in range(1, K+1):
	for b in range(1, a):
		temp.append(gcd(a, b))
for c in range(1, K+1):
	for j in range(len(temp)):
		count += gcd(c, temp[j]) * 2
	for k in range(1, K+1):
		count += gcd(c, k)
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
def gcd(M, m):
	q = m
	r = M % m
	while r != 0:
		p = q
		q = r
		r = p % q
	return q
	
K = int(input())
gcd_sum = 0
for a in range(1, K+1):
	for b in range(1, K+1):
		for c in range(1, K+1):
			ab = gcd(b,a)
			gcd_sum += gcd(c, ab)
print(gcd_sum)

Fixed submission:
def gcd(a, b):
  if a < b:
    a_init = a
    a = b
    b = a_init
  while b != 0:
    r = a % b
    a = b
    b = r
  return a
	
K = int(input())
count = 0
temp = []
for a in range(1, K+1):
	for b in range(1, a):
		temp.append(gcd(a, b))
for c in range(1, K+1):
	for j in range(len(temp)):
		count += gcd(c, temp[j]) * 2
	for k in range(1, K+1):
		count += gcd(c, k)
print(count)

Buggy python submission (verdict: Runtime Error):
K = int(input())
gcd_sum = 0
for a in range(1,K+1):
  a_init = a
  for b in range(1, K+1):
	b_init = b
    for c in range(1, K+1):
      a = a_init
	  b = b_init						
	  m = min(a, b, c)
	  gcd = 1
	  for i in range(2, m+1):
	    if a%i == 0 and b%i == 0 and c%i == 0:
	      a /= i
          b /= i
          c /= i
		  gcd *= i
	  gcd_sum += gcd
print(gcd_sum)


Fixed submission:
def gcd(a, b):
  if a < b:
    a_init = a
    a = b
    b = a_init
  while b != 0:
    r = a % b
    a = b
    b = r
  return a
	
K = int(input())
count = 0
temp = []
for a in range(1, K+1):
	for b in range(1, a):
		temp.append(gcd(a, b))
for c in range(1, K+1):
	for j in range(len(temp)):
		count += gcd(c, temp[j]) * 2
	for k in range(1, K+1):
		count += gcd(c, k)
print(count)

Buggy python submission (verdict: Runtime Error):
K = int(input())
gcd_sum = 0
for a in range(1,K+1):
  a_init = a
  for b in range(1, K+1):
	b_init = b
    for c in range(1, K+1):
      a = a_init
	  b = b_init						
	  m = min(a, b, c)
	  gcd = 1
	  for i in range(2, m+1):
	    if a%i == 0 and b%i == 0 and c%i == 0:
	      a /= i
		  b /= i
		  c /= i
		  gcd *= i
	  gcd_sum += gcd
print(gcd_sum)

Fixed submission:
def gcd(a, b):
  if a < b:
    a_init = a
    a = b
    b = a_init
  while b != 0:
    r = a % b
    a = b
    b = r
  return a
	
K = int(input())
count = 0
temp = []
for a in range(1, K+1):
	for b in range(1, a):
		temp.append(gcd(a, b))
for c in range(1, K+1):
	for j in range(len(temp)):
		count += gcd(c, temp[j]) * 2
	for k in range(1, K+1):
		count += gcd(c, k)
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int , input().split()))
b = [0] * (n-k+1)
b0 = 1
for i in range(k):
    b0 = b0 * a[i]
b[0] = b0
for i in range(k, n):
    b[i-k+1] = b[i-k] // a[i-k] * a[i]
    if b[i-k+1] > b[i-k]:
        print('Yes')
    else:
        print('No')
#print(a, b, b0)

Fixed submission:
n, k = map(int, input().split())
a = list(map(int , input().split()))
b = [0] * (n-k+1)
b0 = 1
for i in range(k):
    b0 = b0 + a[i]
b[0] = b0
for i in range(k, n):
    b[i-k+1] = b[i-k] - a[i-k] + a[i]
    if b[i-k+1] > b[i-k]:
        print('Yes')
    else:
        print('No')
#print(a, b, b0)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int , input().split()))
b = []
for ai in a:
    b.append('{:0=30b}'.format(ai))

cnt = []
for j in range(30):
    tmp = 0
    for i in range(n):
        tmp += int(b[i][j])
    cnt.append(tmp)
ans = []
for bi in b:
    tmp = 0
    for i in range(30):
        idx = 29 + (-i)
        #print(idx)
        x = int(bi[i])
        if cnt[i] == 0:
            continue
        if cnt[i] % 2 == 0:
            tmp += x << idx
        else:
            if x == 0:
                tmp += 1 << idx
    ans.append(tmp)


#print(ans)
print(' '.join(map(str, ans)))

"""
0000010100
0000001011
0000001001
0000011000

0000011010
0000000101
0000000111
0000010110
"""

Fixed submission:
n = int(input())
a = list(map(int , input().split()))
b = []
for ai in a:
    b.append('{:0=30b}'.format(ai))

cnt = []
for j in range(30):
    tmp = 0
    for i in range(n):
        tmp += int(b[i][j])
    cnt.append(tmp)
ans = []
for bi in b:
    tmp = 0
    for i in range(30):
        idx = 29 + (-i)
        #print(idx)
        x = int(bi[i])
        if cnt[i] == 0:
            continue
        if cnt[i] % 2 == 0:
            tmp += x << idx
        else:
            if x == 0:
                tmp += 1 << idx
    ans.append(tmp)


#print(ans)
print(' '.join(map(str, ans)))

"""
0000010100
0000001011
0000001001
0000011000

0000011010
0000000101
0000000111
0000010110
"""
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int , input().split()))
sa = set()
for ai in a:
    if ai in sa:
        sa.discard(ai)
        continue
    sa.add(ai)

if len(sa) == 0:
    print(0)
    exit()

a = list(sa)
a.sort()

#print(a)

import fractions
def lcm(a, b):
    return a * b // fractions.gcd(a, b)

ans = 1
l = 1
for i in range(n):
    if lcm(a[i], l) < a[i] * l:
        continue
    l = lcm(a[i], l)
    ans += 1
print(ans, l)




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

a.sort()

#print(a)
import numpy as np
U=10**6 + 5
is_prime = np.zeros(U,np.bool)
#is_prime[2] = 1
is_prime[1::] = 1
M = int(U**.5)+1
for ai in a:#range(3,M,2):
    if is_prime[ai]:
        is_prime[ai*2::ai] = 0
    #print(is_prime.nonzero()[0])

ans = 0

import collections
cnt = collections.Counter(a)
for ai in a:
    if is_prime[ai] and cnt[ai] == 1:
        ans += 1

print(ans)

"""
sa = set()
for ai in a:
    if ai in sa:
        sa.discard(ai)
        continue
    sa.add(ai)
"""

"""
p = list(range(10**6+10))

a = list(sa)
a.sort()

print(a)

import fractions
def lcm(a, b):
    return a * b // fractions.gcd(a, b)

ans = 1
l = 1
for i in range(n):
    if lcm(a[i], l) < a[i] * l:
        continue
    l = lcm(a[i], l)
    ans += 1
print(ans)

"""
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int , input().split()))

for i in range(k):
    tmp = [0] * n
    for j in range(n):
        for k in range(a[j]*2+1):
            if (j - a[j] + k) >= 0 and (j - a[j] + k) < n:
                tmp[(j - a[j] + k)] += 1
    
    if min(a) == n:
        print(' '.join(map(str, a)))
        exit()
    a = tmp


print(' '.join(map(str, a)))


# 10 5
# 20 8
# 40 10
# 80 12
# 160 15

Fixed submission:
n, k = map(int, input().split())
a = list(map(int , input().split()))

for i in range(k):
    s = [0] * (n + 1)
    for j in range(n):
        l = max(0, j - a[j])
        r = min(n, j + a[j]+1)
        s[l] += 1
        s[r] += -1
    m = s[0]
    for j in range(1,n+1):
        s[j] += s[j-1]
        if j < n:
            m = min(m, s[j])
    a = s[:-1]
    if m == n:
        print(' '.join(map(str, a)))
        exit()
print(' '.join(map(str, a)))

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

for i in range(k):
    tmp = [0] * n
    for j in range(n):
        for k in range(a[j]*2+1):
            if (j - a[j] + k) >= 0 and (j - a[j] + k) < n:
                tmp[(j - a[j] + k)] += 1
    a = tmp

print(' '.join(map(str, a)))


# 10 5
# 20 8
# 40 10
# 80 12
# 160 15

Fixed submission:
n, k = map(int, input().split())
a = list(map(int , input().split()))

for i in range(k):
    s = [0] * (n + 1)
    for j in range(n):
        l = max(0, j - a[j])
        r = min(n, j + a[j]+1)
        s[l] += 1
        s[r] += -1
    m = s[0]
    for j in range(1,n+1):
        s[j] += s[j-1]
        if j < n:
            m = min(m, s[j])
    a = s[:-1]
    if m == n:
        print(' '.join(map(str, a)))
        exit()
print(' '.join(map(str, a)))
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
h = list(map(int , input().split()))

G = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
#print(G)
ans = 0
for i in range(n):
    maxh = 0
    for gi in G[i]:
        maxh = max(h[gi], maxh)
    if maxh < h[i]:
        ans += 1
    #print(maxh, h[i])

print(ans)


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

G = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
#print(G)
ans = 0
for i in range(n):
    maxh = 0
    for gi in G[i]:
        maxh = max(h[gi], maxh)
    if maxh < h[i]:
        ans += 1
    #print(maxh, h[i])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, x, y = map(int, input().split())

import numpy as np
from scipy.sparse.csgraph import floyd_warshall

A = np.zeros((n,n), np.int32)

for i in range(1, n):
    A[i, i-1] = 1
    A[i-1, i] = 1
A[x-1, y-1] = 1
A[y-1, x-1] = 1
dist = floyd_warshall(A, directed = False)

ans = [0] * n
for i in range(n):
    for j in range(i, n):
        ans[int(dist[i][j])] += 1

for i in range(1, n):
    print(ans[i])

Fixed submission:
n, x, y = map(int, input().split())
x = x-1
y = y-1
from collections import deque
que = deque()

INF = 10**5
seen = [[INF] * n for _ in range(n)]
#import numpy as np
for i in range(n):
    que.append(i)
    seen[i][i] = 0
    #print('---', i)
    while len(que) > 0:
        t = que.popleft()
        step = [t-1, t+1]
        if t == x:
            step.append(y)
        if t == y:
            step.append(x)
        for ti in step:
            #print(ti)
            if ti < 0 or ti >= n:
                continue
            if seen[i][ti] == INF:
                que.append(ti)
            seen[i][ti] = min(seen[i][t] + 1, seen[i][ti])
    #print(np.array(seen))
#print(np.array(seen))

ans = [0] * n
for i in range(n):
    for j in range(i, n):
        ans[int(seen[i][j])] += 1

for i in range(1, n):
    print(ans[i])

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

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson

A = np.zeros((n,n), np.int32)

for i in range(1, n):
    A[i, i-1] = 1
    A[i-1, i] = 1
A[x-1, y-1] = 1
A[y-1, x-1] = 1
dist = floyd_warshall(A)
#print(dist)
ans = [0] * n
for i in range(n):
    for j in range(i, n):
        ans[int(dist[i][j])] += 1

for i in range(1, n):
    print(ans[i])

Fixed submission:
n, x, y = map(int, input().split())
x = x-1
y = y-1
from collections import deque
que = deque()

INF = 10**5
seen = [[INF] * n for _ in range(n)]
#import numpy as np
for i in range(n):
    que.append(i)
    seen[i][i] = 0
    #print('---', i)
    while len(que) > 0:
        t = que.popleft()
        step = [t-1, t+1]
        if t == x:
            step.append(y)
        if t == y:
            step.append(x)
        for ti in step:
            #print(ti)
            if ti < 0 or ti >= n:
                continue
            if seen[i][ti] == INF:
                que.append(ti)
            seen[i][ti] = min(seen[i][t] + 1, seen[i][ti])
    #print(np.array(seen))
#print(np.array(seen))

ans = [0] * n
for i in range(n):
    for j in range(i, n):
        ans[int(seen[i][j])] += 1

for i in range(1, n):
    print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
from decimal import *
getcontext().prec = 40000
a, b, c = map(int, input().split())
#print(a **.5, b**.5,c**.5)
#print(a **.5+ b**.5,c**.5)
#print(Decimal(a).sqrt() , Decimal(b).sqrt() , Decimal(c).sqrt())
if Decimal(a).sqrt() + Decimal(b).sqrt() >= Decimal(c).sqrt():
#if a **.5 + b**.5 < c**.5:
    print('No')
else:
    print('Yes')
    

Fixed submission:
from decimal import *
getcontext().prec = 30000
a, b, c = map(int, input().split())
#print(a **.5, b**.5,c**.5)
#print(a **.5+ b**.5,c**.5)
#print(Decimal(a).sqrt() , Decimal(b).sqrt() , Decimal(c).sqrt())
#if Decimal(a).sqrt() + Decimal(b).sqrt() < Decimal(c).sqrt():
if 2 * Decimal(a * b).sqrt() + Decimal(b) + Decimal(a) < Decimal(c):
#if a **.5 + b**.5 < c**.5:
    print('Yes')
else:
    print('No')

Buggy python submission (verdict: Time Limit Exceeded):
from decimal import *
getcontext().prec = 100000
a, b, c = map(int, input().split())
#print(a **.5, b**.5,c**.5)
#print(a **.5+ b**.5,c**.5)
#print(Decimal(a).sqrt() , Decimal(b).sqrt() , Decimal(c).sqrt())
if Decimal(a).sqrt() + Decimal(b).sqrt() < Decimal(c).sqrt():
#if a **.5 + b**.5 < c**.5:
    print('Yes')
else:
    print('No')

Fixed submission:
from decimal import *
getcontext().prec = 30000
a, b, c = map(int, input().split())
#print(a **.5, b**.5,c**.5)
#print(a **.5+ b**.5,c**.5)
#print(Decimal(a).sqrt() , Decimal(b).sqrt() , Decimal(c).sqrt())
#if Decimal(a).sqrt() + Decimal(b).sqrt() < Decimal(c).sqrt():
if 2 * Decimal(a * b).sqrt() + Decimal(b) + Decimal(a) < Decimal(c):
#if a **.5 + b**.5 < c**.5:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
n = int(input())
ans = [[] for _ in range(2**(n-1))]

ans[0].append([1])
ans[1].append([1,1])
ans[1].append([1,2])
#ans[2].append([1,1,1])
#ans[2].append([1,1,2])
#ans[2].append([1,2,2])
#ans[2].append([1,2,3])
import numpy as np

for i in range(2, n):
    for j in range(2):
        for ai in ans[i-1]:
            x = np.array(ai)
            y = list(x+j)
            ans[i].append([1] + y)

r = ['a','b','c','d','e','f','g','h','i','j','k']
for ai in ans[n-1]:
    print(''.join(map(lambda x: str(r[x-1]), ai)))




Fixed submission:
n = int(input())

ans = []
def dfs(x):
    if len(x) == n:
        ans.append(x)
        return
    for i in range(0, max(x)+1):
        y = x.copy()
        y.append(i+1)
        dfs(y)
dfs([1])
#print(ans)

r = ['a','b','c','d','e','f','g','h','i','j']
for ai in ans:
    print(''.join(map(lambda x: str(r[x-1]), ai)))
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
sc = [tuple(map(int, input().split())) for _ in range(m)]
sc = sorted(sc, reverse=True, key=lambda x:x[0])
if sc[0][0] != n:
    print(-1)
    exit()

ans = [0] * n
ans[0] = 1
prev = sc[0]

for i in range(1, m):
    if prev[0] == sc[i][0] and prev[1] != sc[i][1]:
        print(-1)
        exit()
    ans[sc[i][0]-1] = sc[i][1]
    prev = sc[i]
print(ans)
print(''.join(map(lambda x: str(x), ans)))

Fixed submission:
n, m = map(int, input().split())
sc = [tuple(map(int, input().split())) for _ in range(m)]
sc = sorted(sc, key=lambda x:x[0])

if m != 0 and n != 1 and sc[0][0] == 1 and sc[0][1] == 0:
    print(-1)
    exit()
if m == 0 and n == 1:
    print(0)
    exit()

ans = [0] * n
ans[0] = 1
prev = (0, 0)
if m != 0:
    prev = sc[0]
for i in range(m):
    if prev[0] == sc[i][0] and prev[1] != sc[i][1]:
        print(-1)
        exit()
    ans[sc[i][0]-1] = sc[i][1]
    prev = sc[i]
print(''.join(map(lambda x: str(x), ans)))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())

p = list(map(lambda x: int(x) * (int(x)+1) // 2 / int(x), input().split()))


sum_max = 0
for i in range(n-k+1):
    sum_max = max(sum_max, sum(p[i:i+k]))
print(sum_max)

Fixed submission:
n, k = map(int, input().split())
p = list(map(lambda x: int(x) * (int(x)+1) // 2 / int(x), input().split()))

prev = sum(p[0:k])
sum_max = prev
for i in range(n-k+1):
    if i == 0:
        tmp = prev
    else:
        tmp = prev - p[i-1] + p[i+k-1]

    sum_max = max(sum_max, tmp)
    prev = tmp

print(sum_max)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]

inf = 10 ** 9
max_h = 2 * 10**4 + 10
dp = [inf] * max_h
dp[0] = 0
for a, b in ab:
    for i in range(max_h - a + 1):
        dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[h:]))

Fixed submission:
import sys
input = sys.stdin.readline

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]

inf = 10 ** 9
max_h = 2 * 10**4 + 10
dp = [inf] * max_h
dp[0] = 0
for a, b in ab:
    for i in range(max_h - a + 1):
        dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[h:]))

Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]

inf = 10 ** 9
max_h = 2 * 10**4 + 10
dp = [inf] * max_h
dp[0] = 0
for a, b in ab:
    for i in range(max_h - a + 1):
        dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[h:]))

Fixed submission:
import sys
input = sys.stdin.readline

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]

inf = 10 ** 9
max_h = 2 * 10**4 + 10
dp = [inf] * max_h
dp[0] = 0
for a, b in ab:
    for i in range(max_h - a + 1):
        dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[h:]))

Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]

INF = 10 ** 9
dp = [INF] * (h+1)
dp[h] = 0
for a, b in ab:
    for hi in range(h, 0, -1):
        if hi - a <= 0:
            dp[0] = min(dp[0], dp[hi]+b)
            #print('x', dp)
        else:
            dp[hi-a] = min(dp[hi-a], dp[hi]+b)
            #print(' ', dp)
print(dp[0])


Fixed submission:
import sys
input = sys.stdin.readline

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]

inf = 10 ** 9
max_h = 2 * 10**4 + 10
dp = [inf] * max_h
dp[0] = 0
for a, b in ab:
    for i in range(max_h - a + 1):
        dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[h:]))
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
lcm = a[0]
for i in range(1,n):
  lcm = lcm*a[i] // gcd(lcm,a[i])
mod=pow(10,9)+7
ans=0
for x in a:
  ans+=lcm//x
print(ans%mod)

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

import fractions
lcm = 1
prevlcm = 1
ans = 0
for i in range(n):
    ai = a[i]
    lcm = ai * lcm // fractions.gcd(ai, lcm)
    if prevlcm == lcm:
        ans = ans + (lcm // ai)
    else:
        ans = ans * (lcm // prevlcm) + (lcm // ai)
    #print(i, lcm, ans)
    prevlcm = lcm

print(ans % (10**9 + 7))

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

import fractions
lcm = 1
for ai in set(a):
    lcm = ai * lcm // fractions.gcd(ai, lcm)

ans = 0
for ai in a:
    ans += (lcm // ai)

print(ans % (10**9 + 7))

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

import fractions
lcm = 1
prevlcm = 1
ans = 0
for i in range(n):
    ai = a[i]
    lcm = ai * lcm // fractions.gcd(ai, lcm)
    if prevlcm == lcm:
        ans = ans + (lcm // ai)
    else:
        ans = ans * (lcm // prevlcm) + (lcm // ai)
    #print(i, lcm, ans)
    prevlcm = lcm

print(ans % (10**9 + 7))

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

import fractions
lcm = 1
for ai in a:
    lcm = ai * lcm // fractions.gcd(ai, lcm)

ans = 0
for ai in a:
    ans += (lcm // ai)

print(ans % (10**9 + 7))

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

import fractions
lcm = 1
prevlcm = 1
ans = 0
for i in range(n):
    ai = a[i]
    lcm = ai * lcm // fractions.gcd(ai, lcm)
    if prevlcm == lcm:
        ans = ans + (lcm // ai)
    else:
        ans = ans * (lcm // prevlcm) + (lcm // ai)
    #print(i, lcm, ans)
    prevlcm = lcm

print(ans % (10**9 + 7))