Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n, x = map(int, input().split())
p = set(map(int, input().split()))

ans = 0
for i in range(1, 102):
  if i in p:
    continue
  if i < x:
    ans = i
  elif x - ans > i - x:
  	ans = i
    break
print(ans)

Fixed submission:
x, n = map(int, input().split())
p = set(map(int, input().split()))

ans = 0
diff = x
for i in range(1, 102):
  if i in p:
    continue
  tmp = abs(i - x)
  if tmp < diff:
    diff = tmp
    ans = i
print(ans)

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

ans = 0
for i in range(1, 102):
  if i in p:
    continue
  if i < x:
    ans = i
  elif x - ans > i - x
  	ans = i
    break
print(ans)

Fixed submission:
x, n = map(int, input().split())
p = set(map(int, input().split()))

ans = 0
diff = x
for i in range(1, 102):
  if i in p:
    continue
  tmp = abs(i - x)
  if tmp < diff:
    diff = tmp
    ans = i
print(ans)
Buggy python submission (verdict: Runtime Error):
a, b = input().split()
a = int(a)
bx100 = int(b.repleace('.', ''))
print(a * bx100 // 100)

Fixed submission:
a, b = input().split()
a = int(a)
bx100 = int(b.replace('.', ''))
print(a * bx100 // 100)
Buggy python submission (verdict: Runtime Error):
mod = 998244353
n, s = map(int, input().split())
dp = np.zeros((n+1, s+1), dtype=int)
dp[0, 0] = 1
for i, a in enumerate(map(int, input().split())):
  dp[i+1] = dp[i] * 2 % mod
  dp[i+1][a:] = (dp[i+1][a:] + dp[i][:-a]) % mod
print(dp[-1, -1])

Fixed submission:
import numpy as np

mod = 998244353
n, s = map(int, input().split())
dp = np.zeros((n+1, s+1), dtype=int)
dp[0, 0] = 1
for i, a in enumerate(map(int, input().split())):
  dp[i+1] = dp[i] * 2 % mod
  dp[i+1][a:] = (dp[i+1][a:] + dp[i][:-a]) % mod
print(dp[-1, -1])

Buggy python submission (verdict: Time Limit Exceeded):
mod = 998244353
n, s = map(int, input().split())
dp = [0] * (s + 1)
dp[0] = 1
for a in map(int, input().split()):
  pre_dp = dp[:]
  for j in range(s + 1):
    dp[j] = (pre_dp[j] * 2) % mod
    if j >= a:
      dp[j] = (dp[j] + pre_dp[j-a]) % mod
print(dp[-1])

Fixed submission:
import numpy as np

mod = 998244353
n, s = map(int, input().split())
dp = np.zeros((n+1, s+1), dtype=int)
dp[0, 0] = 1
for i, a in enumerate(map(int, input().split())):
  dp[i+1] = dp[i] * 2 % mod
  dp[i+1][a:] = (dp[i+1][a:] + dp[i][:-a]) % mod
print(dp[-1, -1])

Buggy python submission (verdict: Time Limit Exceeded):
mod = 998244353
n, s = map(int, input().split())
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i, a in enumerate(map(int, input().split())):
  for j in range(s + 1):
    dp[i+1][j] = (dp[i][j] * 2) % mod
    if j >= a:
      dp[i+1][j] = (dp[i+1][j] + dp[i][j-a]) % mod
print(dp[-1][-1])

Fixed submission:
import numpy as np

mod = 998244353
n, s = map(int, input().split())
dp = np.zeros((n+1, s+1), dtype=int)
dp[0, 0] = 1
for i, a in enumerate(map(int, input().split())):
  dp[i+1] = dp[i] * 2 % mod
  dp[i+1][a:] = (dp[i+1][a:] + dp[i][:-a]) % mod
print(dp[-1, -1])
Buggy python submission (verdict: Time Limit Exceeded):
def zero_index(i: str) -> int:
  return int(i) - 1

n, k = map(int, input().split())
transition = list(map(zero_index, input().split()))
places = [0]
next_place = transition[0]
while next_place not in places:
  places.append(next_place)
  next_place = transition[next_place]
start = places.index(next_place)
period = len(places) - start
if k < start:
  t = k
else:
  t = (k - start) % period + start
print(places[t] + 1)

Fixed submission:
def zero_index(i: str) -> int:
  return int(i) - 1

n, k = map(int, input().split())
transition = list(map(zero_index, input().split()))
places = [0]
next_place = transition[0]
virgin = [True] * n
virgin[0] = False
while virgin[next_place]:
  virgin[next_place] = False
  places.append(next_place)
  next_place = transition[next_place]
start = places.index(next_place)
period = len(places) - start
if k < start:
  t = k
else:
  t = (k - start) % period + start
print(places[t] + 1)

Buggy python submission (verdict: Runtime Error):
def zero_index(i: str) -> int:
  return int(i) - 1

n, k = map(int, input().split())
transition = map(zero_index, input().split())
places = [0]
next_place = transition[0]
while next_place not in places:
  places.append(next_place)
  next_place = transition[next_place]
start = places.index(next_place)
period = len(places) - start
if k < start:
  t = k
else:
  t = (k - start) % priod + start
print(place[t] + 1)

Fixed submission:
def zero_index(i: str) -> int:
  return int(i) - 1

n, k = map(int, input().split())
transition = list(map(zero_index, input().split()))
places = [0]
next_place = transition[0]
virgin = [True] * n
virgin[0] = False
while virgin[next_place]:
  virgin[next_place] = False
  places.append(next_place)
  next_place = transition[next_place]
start = places.index(next_place)
period = len(places) - start
if k < start:
  t = k
else:
  t = (k - start) % period + start
print(places[t] + 1)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
plus_bracket = []
minus_bracket = []
zero_bracket = 0
for _ in range(n):
  mini = 0
  cur = 0
  for bracket in input():
    if bracket == '(':
      cur += 1
    else:
      cur -= 1
    if cur < mini:
      mini = cur
  if cur > 0:
    plus_bracket.append([mini, cur])
  elif cur < 0:
    minus_bracket.append([mini - cur, -cur])
  elif mini < zero_bracket:
    zero_bracket = mini

success = True
cur = 0
plus_bracket.sort(reverse=True)
minus_bracket.sort(reverse=True)
for bracket in plus_bracket:
  if cur + bracket[0] < 0:
    success = False
    break
  cur += bracket[1]
if cur + zero_bracket < 0:
  success = False
back_cur = 0
for bracket in minus_bracket:
  if back_cur + bracket[0] < 0:
    success = False
    break
  back_cur += bracket[1]
if cur != back_cur:
  success = False

if success:
  print('Yes')
else:
  print('No')

Fixed submission:
n = int(input())
plus_bracket = []
minus_bracket = []

for _ in range(n):
  mini = 0
  cur = 0
  for bracket in input():
    if bracket == '(':
      cur += 1
    else:
      cur -= 1
    if cur < mini:
      mini = cur
  if cur > 0:
    plus_bracket.append([-mini, cur])
  else:
    minus_bracket.append([cur - mini, -cur])

success = True
cur = 0
plus_bracket.sort()
minus_bracket.sort()
for bracket in plus_bracket:
  if cur < bracket[0]:
    success = False
    break
  cur += bracket[1]
back_cur = 0
for bracket in minus_bracket:
  if back_cur < bracket[0]:
    success = False
    break
  back_cur += bracket[1]
if cur != back_cur:
  success = False

if success:
  print('Yes')
else:
  print('No')
Buggy python submission (verdict: Time Limit Exceeded):
def f(a: int, b: int) -> int:
  return a ** 5 - b ** 5

x = int(input())
factor = []
fact = 1
while fact * fact < x:
  if x % fact == 0:
    factor.append(fact)
    factor.append(x // fact)
  fact += 1
if fact * fact == x:
  factor.append(fact)
for d in factor:
  if x // d % 5 > 1:
    continue
  a = d // 2
  while f(a, a - d) < x:
    a *= 2
  if f(a, a - d) == x:
    print(a, a - d)
    break
  upper = a
  lower = a // 2
  while upper - lower > 1:
    a = (upper + lower) // 2
    value = f(a, a - d)
    if value < x:
      lower = a
    elif value > x:
      upper = a
    else:
      print(a, a - d)
      break
  else:
    if f(lower, lower - d) == x:
      print(lower, lower - d)
    continue
  break

Fixed submission:
x = int(input())
for a in range(-200, 200):
  for b in range(-200, 200):
    if a ** 5 - b ** 5 == x:
      print(a, b)
      break
  else:
    continue
  break

Buggy python submission (verdict: Time Limit Exceeded):
x = int(input())
root5x = int(pow(x, 0.2)) + 1
factor = []
fact = 1
while fact * fact < x:
  if x % fact == 0:
    factor.append(fact)
    factor.append(x // fact)
  fact += 1
if fact * fact == x:
  factor.append(fact)
for d in factor:
  rest = x // d
  if rest % 5 > 1:
    continue
  for a in range(d):
    b = a - d
    if x == a ** 5 - b ** 5:
      print(a, b)
      break
  else:
    continue
  break

Fixed submission:
x = int(input())
for a in range(-200, 200):
  for b in range(-200, 200):
    if a ** 5 - b ** 5 == x:
      print(a, b)
      break
  else:
    continue
  break
Buggy python submission (verdict: Runtime Error):
k = int(input())

count = [pow(k // max(i, 1), 3, mod) for i in range(k + 1)]

for i in range(k, 0, -1):
  for j in range(2 * i, k + 1, i):
    count[i] -= count[j]

sum_ = 0
for i in range(k + 1):
  sum_ += i * count[i]

print(sum_)

Fixed submission:
from math import gcd

k = int(input())
sum_ = 0
for a in range(1, k + 1):
  for b in range(1, k + 1):
    gcd_ab = gcd(a, b)
    for c in range(1, k + 1):
      sum_ += gcd(c, gcd_ab)
print(sum_)
Buggy python submission (verdict: Runtime Error):
import numpy as np

n = int(input())
a = np.array(input().split(), dtype=np.int)

if n % 2 == 0:
  print(max(a[::2].sum(), a[1::2].sum()))
else:
  dp = a[:3]
  for i in range(1, n // 2):
    dp = dp[0] + a[2*i], dp[:2].max() + a[2*i+1], dp.max() + a[2*i+2]
  print(dp.max())

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

if n % 2 == 0:
  dp = a[:2]
  for i in range(1, n // 2):
    dp = dp[0] + a[2*i], max(dp) + a[2*i+1]
else:
  dp = a[:3]
  for i in range(1, n // 2):
    dp = dp[0] + a[2*i], max(dp[:2]) + a[2*i+1], max(dp) + a[2*i+2]

print(max(dp))
Buggy python submission (verdict: Runtime Error):
k = int(input())
num = 0
for _ in range(k):
  num += 1
  digit = [int(digit) for digit in str(num)]
  len_digit = len(digit)
  for i in range(1, len_digit):
    if digit[-i] > min(digit[-i-1] + 1, 9):
      digit[-i-1] += 1
      digit[-i] = -1
    elif digit[-i] < digit[-i-1] - 1:
      digit[-i] = -1
  for i in range(1, len_digit):
    if digit[i] == -1:
      for j in range(i, len_digit):
        digit[j] = max(digit[j-1] - 1, 0)
      break
  num = d[0]
  for d in digit[1:]:
    num = num * 10 + d
print(num)

Fixed submission:
k = int(input())
num = 0
for _ in range(k):
  num += 1
  digit = [int(digit) for digit in str(num)]
  len_digit = len(digit)
  flag = False
  for i in range(1, len_digit):
    # current_digit = digit[-i]
    # upper_digit = digit[-i-1]
    if digit[-i] == 10:
      digit[-i-1] += 1
      digit[-i] = -1
    elif digit[-i] > digit[-i-1] + 1:
      digit[-i-1] += 1
      digit[-i] = -1
    elif digit[-i] < digit[-i-1] - 1:
      digit[-i] = -1
  if digit[0] == 10:
    num = 10 ** len_digit
  else:
    for i in range(1, len_digit):
      if digit[i] == -1:
        for j in range(i, len_digit):
          digit[j] = max(digit[j-1] - 1, 0)
        break
    num = 0
    for d in digit:
      num = num * 10 + d
print(num)
Buggy python submission (verdict: Runtime Error):
from heapq import heappop, heappush

x, y, a, b, c = map(int, input().split())
apple = []
for p in map(int, input().split()):
  heappush(apple, (-p, True))
for q in map(int, input().split()):
  heappush(apple, (-q, False))
for r in map(int, input().split()):
  heappush(apple, (-r, None))
delicious = 0
colorless = 0
while x + y > colorless:
  minus_taste, color = heappop(apple)
  if color is True:
    if x > 0:
      delicious -= minus_taste
      x -= 1
  elif color is False:
    if y > 0:
      delicious -= minus_taste
      y -= 1
  else:
    delicious -= minus_taste
    colorless += 1
print(delicious)

Fixed submission:
from heapq import heappop, heappush

x, y, a, b, c = map(int, input().split())
apple = []
# Red is 0, Green is 1, Colorless is 2
for p in map(int, input().split()):
  heappush(apple, (-p, 0))
for q in map(int, input().split()):
  heappush(apple, (-q, 1))
for r in map(int, input().split()):
  heappush(apple, (-r, 2))
delicious = 0
colorless = 0
while x + y > colorless:
  minus_taste, color = heappop(apple)
  if color == 0:
    if x > 0:
      delicious -= minus_taste
      x -= 1
  elif color == 1:
    if y > 0:
      delicious -= minus_taste
      y -= 1
  else:
    delicious -= minus_taste
    colorless += 1
print(delicious)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7
MAX_N = 2 * 10 ** 5

fact = [1] * (MAX_N + 1)
inverse = [1] * (MAX_N + 1)
inv_fact = [1] * (MAX_N + 1)
for i in range(2, MAX_N + 1):
  fact[i] = fact[i-1] * i % MOD
  inverse[i] = -inverse[MOD % i] * (MOD // i) % MOD
  inv_fact[i] = inv_fact[i-1] * inverse[i] % MOD

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

for root in range(n):
  stack = [root]
  parent = [root] * n
  route = []
  while stack:
    vertex = stack.pop()
    route.append(vertex)
    for child in edge[vertex]:
      if parent[vertex] != child:
        parent[child] = vertex
        stack.append(child)

  dp = [1] * n
  size = [1] * n
  for vertex in route[:0:-1]:
    pa = parent[vertex]
    sz = size[vertex]
    dp[vertex] = dp[vertex] * fact[sz-1] % MOD
    dp[pa] = dp[pa] * dp[vertex] * inv_fact[sz] % MOD
    size[pa] += sz
  print(dp[root] * fact[size[root] - 1] % MOD)

Fixed submission:
MOD = 10 ** 9 + 7
MAX_N = 2 * 10 ** 5

fact = [1] * MAX_N
inverse = [1] * MAX_N
inv_fact = [1] * MAX_N
for i in range(2, MAX_N):
  fact[i] = fact[i-1] * i % MOD
  inverse[i] = -inverse[MOD % i] * (MOD // i) % MOD
  inv_fact[i] = inv_fact[i-1] * inverse[i] % MOD

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

stack = [0]
parent = [0] * n
route = []
while stack:
  vertex = stack.pop()
  route.append(vertex)
  for child in edge[vertex]:
    if parent[vertex] != child:
      parent[child] = vertex
      stack.append(child)

dp = [1] * n
size = [1] * n
for vertex in route[:0:-1]:
  pa = parent[vertex]
  sz = size[vertex]
  dp[vertex] = dp[vertex] * fact[sz-1] % MOD
  dp[pa] = dp[pa] * dp[vertex] * inv_fact[sz] % MOD
  size[pa] += sz
dp[0] = dp[0] * fact[n-1] % MOD

for vertex in route[1:]:
  pa = parent[vertex]
  sz = size[vertex]
  tmp = dp[pa] * pow(dp[vertex], MOD - 2, MOD) * sz * inverse[n-sz] % MOD
  dp[vertex] = dp[vertex] * tmp % MOD

for value in dp:
  print(value)
Buggy python submission (verdict: Runtime Error):
h, w = map(int, input().split())
h_evan = h // 2
h_odd = h_even + (h % 2)
w_evan = w // 2
w_odd = w_even + (w % 2)
print(h_even * w_even + h_odd * w_odd)

Fixed submission:
h, w = map(int, input().split())
if h > 1 and w > 1:
  print((h // 2) * (w // 2) + (h // 2 + h % 2) * (w // 2 + w % 2))
else:
  print(1)

Buggy python submission (verdict: Runtime Error):
h, 2 = map(int, input().split())
if (h * w) & 1:
  print(h * (w + 1) // 2 - h // 2)
else:
  print(h * w)

Fixed submission:
h, w = map(int, input().split())
if h > 1 and w > 1:
  print((h // 2) * (w // 2) + (h // 2 + h % 2) * (w // 2 + w % 2))
else:
  print(1)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = ord('a')

def f(x: int) -> str:
  return chr(x + a)

for i in range(2 * 10 ** (n-2)):
  x = list(map(int, str(i).zfill(n)))
  maximum = 0
  flag = True
  for j, digit in enumerate(x):
    if digit > maximum + 1:
      flag = False
      break
    elif digit == maximum + 1:
      maximum = digit
  if flag:
    print(''.join(map(f, x)))
  else:
    d = 10 ** (n - j)
    i = (i // d + 1) * d

Fixed submission:
n = int(input())
a = ord('a')

def f(x: str) -> str:
  return chr(int(x) + a)

i = 0
while i < 10 ** (n-1):
  x = str(i).zfill(n)
  maximum = 0
  flag = True
  for j, digit in enumerate(map(int, x)):
    if digit > maximum + 1:
      flag = False
      break
    elif digit == maximum + 1:
      maximum = digit
  if flag:
    print(''.join(map(f, x)))
    i += 1
  else:
    d = 10 ** (n - j)
    i = (i // d + 1) * d

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = ord('a')

def f(x: int) -> str:
  return chr(x + a)

for i in range(2 * 10 ** (n-2)):
  x = list(map(int, str(i).zfill(n)))
  maximum = 0
  flag = True
  for y in x[1:]:
    if y > maximum + 1:
      flag = False
      break
    elif y == maximum + 1:
      maximum = y
  if flag:
    print(''.join(map(f, x)))

Fixed submission:
n = int(input())
a = ord('a')

def f(x: str) -> str:
  return chr(int(x) + a)

i = 0
while i < 10 ** (n-1):
  x = str(i).zfill(n)
  maximum = 0
  flag = True
  for j, digit in enumerate(map(int, x)):
    if digit > maximum + 1:
      flag = False
      break
    elif digit == maximum + 1:
      maximum = digit
  if flag:
    print(''.join(map(f, x)))
    i += 1
  else:
    d = 10 ** (n - j)
    i = (i // d + 1) * d
Buggy python submission (verdict: Runtime Error):
x = []
for i in range(1000):
  x.append([0] * 10000000000000)

Fixed submission:
s = input()
if s == 'AAA' or s == 'BBB':
  print('No')
else:
  print('Yes')
Buggy python submission (verdict: Runtime Error):
s = input()
q = int(input())
appendix = [[], []]
reverse = False
for _ in range(q):
  query = input().split()
  if query[0] == '1':
    reverse ^= True
  else:
    f = bool(int(query[1]) - 1)
    appendix[int(f ^ reverse)].append(query[2])
print(''.join(appendix[int(reverse)][::-1]) + s + ''.join(appendix[int(not reverse)])

Fixed submission:
s = input()
q = int(input())
appendix = [[], []]
reverse = False
for _ in range(q):
  query = input().split()
  if query[0] == '1':
    reverse ^= True
  else:
    f = bool(int(query[1]) - 1)
    appendix[int(f ^ reverse)].append(query[2])
if reverse:
  print(''.join(appendix[1][::-1]) + s[::-1] + ''.join(appendix[0]))
else:
  print(''.join(appendix[0][::-1]) + s + ''.join(appendix[1]))
Buggy python submission (verdict: Runtime Error):
n, m, k = map(int, input().split())

friend = [[] for _ in range(n)]
block = [[] for _ in range(n)]

for _ in range(m):
  a, b = map(int, input().split())
  friend[a-1].append(b-1)
  friend[b-1].append(a-1)
  
for _ in range(k):
  c, d = map(int, input().split())
  block[c-1].append(d-1)
  block[d-1].append(c-1)
  
groups = []
active = [True] * n
belong = [0] * n
g_index = 0
while any(active):
  idx = active.index(True)
  g = [idx]
  active[idx] = False
  belong[idx] = g_index
  stack = [idx]
  while stack:
    v = stack.pop()
    for i in friend[v]:
      if active[i]:
        stack.append(i)
        active[i] = False
        belong[i] = g_index
        g.append(i)
  groups.append(g)
  g_index += 1
  
for i in range(n):
  size = len(groups[belong[i]]) - 1
  for j in groups[belong[i]]:
    if j in friend[i] or j in block[i]:
      size -= 1
  print(size, end=' ')

Fixed submission:
n = int(input())
print((n+1) // 2)
Buggy python submission (verdict: Runtime Error):
k, q = map(int, input().split())
d = list(map(int, input().split()))
for _ in range(q):
  n, x, m = map(int, input().split())
  dmod = [di % m for di in d]
  same = dmod.count(0) * ((n-1) // k) + dmod[: (n-1) % k].count(0)
  a_last = x + sum(dmod) * ((n-1) // k) + sum(dmod[: (n-1) % k])
  beyond = a_last // m - x // m
  print(n - 1 - same - beyond)

Fixed submission:
n, r = map(int, input().split())
print(r + 100 * (10 - min(n, 10)))
Buggy python submission (verdict: Runtime Error):
n, d, a = map(int, input().split())
monster = []
for _ in range(n):
  x, h = map(int, input().split())
  monster.append([x, h])
monster.sort()
bomb = 0
j = 0
for i in range(n):
  while j < n and monster[j][0] - monster[i][0] <= 2 * d:
    j += 1
  if monster[i][1] <= 0:
    continue
  b = (monster[i][1] - 1) // a + 1
  atk = a * b
  bomb += b
  for k in range(i+1, j):
    monster[k][1] -= atk
print(bomb)

Fixed submission:
h, a = map(int, input().split())
print((h-1)//a + 1)
Buggy python submission (verdict: Runtime Error):
h = int(input().split())
print(2 ** (len(bin(h)) - 2) - 1)

Fixed submission:
h = int(input())
print(2 ** (len(bin(h)) - 2) - 1)
Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
a = []
b = []
for _ in range(n):
  ai, bi = map(int, input().split())
  a.append(ai)
  b.append(bi)
dp = [0] * (h+1)
for c in range(1, h+1):
  dp[c] = min([dp[max(0, c-a[i])] + b[i] for i in range(n)])
print(dp[-1])

Fixed submission:
h, n = map(int, input().split())
dp = [[0] * (h+1) for i in range(n)]
a, b = map(int, input().split())
for c in range(1, h+1):
  dp[0][c] = b * ((c-1) // a + 1)
for i in range(1, n):
  a, b = map(int, input().split())
  for c in range(1, h+1):
    opt1 = dp[i-1][c]
    opt2 = dp[i-1][max(0, c-a)] + b
    opt3 = dp[i][max(0, c-a)] + b
    dp[i][c] = min(opt1, opt2, opt3)
print(dp[-1][-1])

Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
ab = []
for _ in range(n):
  a, b = map(int, input().split())
  ab.append((a, b))
dp = [0] * (h+1)
for c in range(1, h+1):
  dp[c] = min([dp[max(0, c-a)] + b for a, b in ab])
print(dp[-1])

Fixed submission:
h, n = map(int, input().split())
dp = [[0] * (h+1) for i in range(n)]
a, b = map(int, input().split())
for c in range(1, h+1):
  dp[0][c] = b * ((c-1) // a + 1)
for i in range(1, n):
  a, b = map(int, input().split())
  for c in range(1, h+1):
    opt1 = dp[i-1][c]
    opt2 = dp[i-1][max(0, c-a)] + b
    opt3 = dp[i][max(0, c-a)] + b
    dp[i][c] = min(opt1, opt2, opt3)
print(dp[-1][-1])

Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
dp = [[0] * (h+1) for i in range(n)]
a, b = map(int, input().split())
for c in range(1, h+1):
  dp[0][c] = b * ((c-1) // a + 1)
for i in range(1, n):
  a, b = map(int, input().split())
  for c in range(1, h+1):
    opt1 = dp[i-1][c]
    opt2 = dp[i-1][max(0, c-a)] + b
    opt3 = dp[i][max(0, c-a)] + b
    dp[i][c] = min(opt1, opt2, opt3)
print(dp[-1][-1])

Fixed submission:
h, n = map(int, input().split())
dp = [[0] * (h+1) for i in range(n)]
a, b = map(int, input().split())
for c in range(1, h+1):
  dp[0][c] = b * ((c-1) // a + 1)
for i in range(1, n):
  a, b = map(int, input().split())
  for c in range(1, h+1):
    opt1 = dp[i-1][c]
    opt2 = dp[i-1][max(0, c-a)] + b
    opt3 = dp[i][max(0, c-a)] + b
    dp[i][c] = min(opt1, opt2, opt3)
print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

h, w = map(int, input().split())
maze = [input() for _ in range(h)]

max_move = 0
for start_i in range(h):
  for start_j in range(w):
    if maze[start_i][start_j] == '.':
      queue = deque([(0, start_i, start_j)])
      yet = [[True] * w for _ in range(h)]
      while queue:
        move, i, j = queue.popleft()
        yet[i][j] = False
        if i != 0 and maze[i-1][j] == '.' and yet[i-1][j]:
          queue.append((move + 1, i - 1, j))
        if i != h - 1 and maze[i+1][j] == '.' and yet[i+1][j]:
          queue.append((move + 1, i + 1, j))
        if j != 0 and maze[i][j-1] == '.' and yet[i][j-1]:
          queue.append((move + 1, i, j - 1))
        if j != w - 1 and maze[i][j+1] == '.' and yet[i][j+1]:
          queue.append((move + 1, i, j + 1))
      if move > max_move:
        max_move = move

print(max_move)

Fixed submission:
from collections import deque

h, w = map(int, input().split())
maze = [input() for _ in range(h)]

max_move = 0
for start_i in range(h):
  for start_j in range(w):
    if maze[start_i][start_j] == '.':
      queue = deque([(0, start_i, start_j)])
      yet = [[True] * w for _ in range(h)]
      yet[start_i][start_j] = False
      while queue:
        move, i, j = queue.popleft()
        if i != 0 and maze[i-1][j] == '.' and yet[i-1][j]:
          queue.append((move + 1, i - 1, j))
          yet[i-1][j] = False
        if i != h - 1 and maze[i+1][j] == '.' and yet[i+1][j]:
          queue.append((move + 1, i + 1, j))
          yet[i+1][j] = False
        if j != 0 and maze[i][j-1] == '.' and yet[i][j-1]:
          queue.append((move + 1, i, j - 1))
          yet[i][j-1] = False
        if j != w - 1 and maze[i][j+1] == '.' and yet[i][j+1]:
          queue.append((move + 1, i, j + 1))
          yet[i][j+1] = False
      if move > max_move:
        max_move = move

print(max_move)