Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):

N,K = map(int,input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

if sum(A) <= K:
  print(0)
  exit()

A.sort()
F.sort(reverse=True)

def check(x):
  k = 0
  for a,f in zip(A, F):
    if a*f > x:
      while a > 0:
        a -= 1
        k += 1
        if a*f <= x: break

  return k <= K

# AをX以下にできるか？?
ng,ok = 0, 10**18+1
while ok-ng > 1:
  x = (ok+ng)//2
  if check(x):
    ok = x
  else:
    ng = x

print(ok)

Fixed submission:
import math

N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
if sum(A) <= K:
  print(0)
  exit()
A.sort()
F.sort(reverse=True)

l,r = -1,10**12+1

while r-l > 1:
  m = (l+r)//2

  k = 0
  for i in range(N):
    a,f = A[i], F[i]
    k += max(0,a-(m//f))

  if k <= K:
    r = m
  else:
    l = m

print(r)
Buggy python submission (verdict: Runtime Error):
from itertools import combinations
A,B = map(int,input().split())

divisors = []
n,m = min(A,B), max(A,B)
for i in range(1,int(n**0.5)+1):
  if n%i==0 and m%i==0:
    divisors.append(i)
    p = n//i
    if m%p==0:
      divisors.append(p)

d = max(divisors)
isPrime = [True] * (d+1)
isPrime[0],isPrime[1] = False,False
for i in range(2, int(d ** 0.5) + 1):
  if isPrime[i]:
    for j in range(i * i, d + 1, i):
      isPrime[j] = False

ans = 1
for d in divisors:
  if isPrime[d]:
    ans += 1
print(ans)


Fixed submission:

from collections import Counter
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table

A,B = map(int,input().split())
p1 = Counter(prime_decomposition(A))
p2 = Counter(prime_decomposition(B))
ans = 1
for p,_ in p1.items():
  if p2[p] > 0:
    ans += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import bisect
s = input()
t = input()

counter = defaultdict(list)
for i,c in enumerate(s):
  counter[c].append(i)

prev = 10**10
cycle = 0
for i,c in enumerate(t):
  if c not in counter:
    print(-1)
    exit()

  idx = counter[c]
  found = -1
  for j in idx:
    if j > prev:
      found = j
      break

  if found == -1:
    cycle += 1
    prev = idx[0]
  else:
    prev = found

print( (cycle-1)*len(s) + prev+1 )

Fixed submission:
from collections import defaultdict
import bisect
s = input()
t = input()

counter = defaultdict(list)
for i,c in enumerate(s):
  counter[c].append(i)

prev = 10**10
cycle = 0
for i,c in enumerate(t):
  if c not in counter:
    print(-1)
    exit()

  idx = counter[c]
  found = bisect.bisect_right(idx, prev)

  if found >= len(idx):
    cycle += 1
    prev = idx[0]
  else:
    prev = idx[found]

print( (cycle-1)*len(s) + prev+1 )
Buggy python submission (verdict: Runtime Error):
import heapq
N,M = map(int,input().split())
jobs = [ [] for _ in range(M+1) ]
for _ in range(N):
  a,b = map(int,input().split())
  jobs[a].append(b)

pq = []
d = 1
res = 0
for _ in range(M-1, -1, -1):
  for b in jobs[d]:
    heapq.heappush(pq, -b)
  if pq:
    res += -heapq.heappop(pq)
  d += 1

print(res)

Fixed submission:
import heapq
N,M = map(int,input().split())
jobs = [ [] for _ in range(M+1) ]
for _ in range(N):
  a,b = map(int,input().split())
  if a <= M:
    jobs[a].append(b)

pq = []
d = 1
res = 0
for _ in range(M-1, -1, -1):
  for b in jobs[d]:
    heapq.heappush(pq, -b)
  if pq:
    res += -heapq.heappop(pq)
  d += 1

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
from collections import deque
N = int(input())
A = deque([])
for i in range(N):
  A.append(int(input()))

ans = 0
while len(A) > 0:
  dp = []
  l = len(A)
  for _ in range(l):
    a = A.popleft()
    if len(dp)==0:
      dp.append(a)
    elif a > dp[-1]:
      dp.append(a)
    else:
      pos = bisect.bisect_left(dp, a)
      A.append(dp[pos])
      dp[pos] = a
  ans += 1

print(ans)

Fixed submission:
import bisect
from collections import deque
N = int(input())
A = deque([])
for i in range(N):
  A.append(int(input()))

dp = deque([])
l = len(A)
for i,a in enumerate(A):
  pos = bisect.bisect_left(dp, a)-1
  if pos<0:
    dp.appendleft(a)
  else:
    dp[pos] = a

print(len(dp))
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
class Combination:
  def __init__(self, n_max, mod=10**9+7):
    self.mod = mod
    self.modinv = self.make_modinv_list(n_max)
    self.fac, self.facinv = self.make_factorial_list(n_max)

  def __call__(self, n, r):
    return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

  def make_factorial_list(self, n):
    # 階乗のリストと階乗のmod逆元のリストを返す O(n)
    # self.make_modinv_list()が先に実行されている必要がある
    fac = [1]
    facinv = [1]
    for i in range(1, n+1):
      fac.append(fac[i-1] * i % self.mod)
      facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
    return fac, facinv

  def make_modinv_list(self, n):
    # 0からnまでのmod逆元のリストを返す O(n)
    modinv = [0] * (n+1)
    modinv[1] = 1
    for i in range(2, n+1):
        modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
    return modinv

N,K = map(int,input().split())
adj = [ [ ]for _ in range(N) ]
comb = Combination(10**5)

def nPr(n,r):
  if n < r: return 0
  return comb(n, r) * comb.fac[r]

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

def dfs(v, p=-1):
  global ans
  c = 0
  for nei in adj[v]:
    if nei == p: continue
    c += 1
    dfs(nei, v)

  nk = K-1 if p==-1 else K-2
  ans *= nPr(nk, c)
  ans %= 10**9+7

ans = K
dfs(0)
print(ans)

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

x1 = 0
for i,a in enumerate(A):
  if (i&1):
    x1 -= a
  else:
    x1 += a
x1 //= 2

res = [0] * N
res[0] = x1
for i in range(N-1):
  res[i+1] = A[i] - res[i]
for i in range(N):
  res[i] *= 2

print(" ".join(map(str, res)))
Buggy python submission (verdict: Runtime Error):
from operator import mul
from functools import reduce

def cmb(n, r):
  if n < r:
    return 0
  r = min(n - r, r)
  if r == 0:
    return 1
  numer = reduce(mul, range(n, n - r, -1))
  denom = reduce(mul, range(1, r + 1))
  return numer // denom % (10 ** 9 + 7)

N,K = map(int,input().split())
MOD = 10**9+7
for i in range(1, K+1):
  print(cmb(K-1,i-1) * cmb(N-K+1, (N-K)-(i-1)))


Fixed submission:
from operator import mul
from functools import reduce

def cmb(n, r):
  if n < r:
    return 0
  r = min(n - r, r)
  if r == 0:
    return 1
  numer = reduce(mul, range(n, n - r, -1))
  denom = reduce(mul, range(1, r + 1))
  return (numer // denom) % (10 ** 9 + 7)

N,K = map(int,input().split())
MOD = 10**9+7
for i in range(1, K+1):
  print(cmb(K-1,i-1)%MOD * cmb(N-K+1, i)%MOD % MOD)
Buggy python submission (verdict: Runtime Error):
def gcd(x,y):
  while y:
    x,y = y,x%y
  return x

A,B,C,D = map(int,input().split())
lcm = C*D // gcd(C,D)
print(B-A-(B//C-A//C)-(B//D-A//D)+(B//lcm-A//lcm))+1


Fixed submission:
def gcd(x,y):
  while y:
    x,y = y,x%y
  return x

def calc(x,a,b,l):
  return x - (x//a) - (x//b) + (x//l)

A,B,C,D = map(int,input().split())
lcm = C*D // gcd(C,D)
print(calc(B,C,D,lcm) - calc(A-1,C,D,lcm))

Buggy python submission (verdict: Runtime Error):
import math
A,B,C,D = map(int,input().split())
lcm = C*D // math.gcd(C,D) 
print(B-A-int(B/C-A/C)-int(B/D-A/D)+int(B/lcm-A/lcm))

Fixed submission:
def gcd(x,y):
  while y:
    x,y = y,x%y
  return x

def calc(x,a,b,l):
  return x - (x//a) - (x//b) + (x//l)

A,B,C,D = map(int,input().split())
lcm = C*D // gcd(C,D)
print(calc(B,C,D,lcm) - calc(A-1,C,D,lcm))
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
MOD = 10**9+7
dp = [0] * (N+1)
dp[1] = 1
dp[2] = 1
for _ in range(M):
  dp[int(input())] = -1

for i in range(N+1):
  if dp[i] == -1: continue
  if i-1>=0 and dp[i-1] != -1:
    dp[i] += dp[i-1]
  if i-2>=0 and dp[i-2] != -1:
    dp[i] += dp[i-2]
  dp[i] %= MOD

print(dp[N])

Fixed submission:
N,M = map(int,input().split())
MOD = 10**9+7
dp = [0] * (N+1)
dp[1] = 1
for _ in range(M):
  dp[int(input())] = -1
if N<2:
  print(dp[N])
  exit()

if dp[2] != -1:
  dp[2] = 1
for i in range(N+1):
  if dp[i] == -1: continue
  if i-1>=0 and dp[i-1] != -1:
    dp[i] += dp[i-1]
  if i-2>=0 and dp[i-2] != -1:
    dp[i] += dp[i-2]
  dp[i] %= MOD

print(dp[N])

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)
N,M = map(int,input().split())
A = []
MOD = 10**9+7
memo = {}
for _ in range(M):
  memo[a] = 0

def step(cur):
  if cur in memo:
    return memo[cur]
  if cur == N:
    memo[cur] = 1
    return memo[cur]
  if cur > N:
    memo[cur] = 0
    return memo[cur]
 
  memo[cur] = (step(cur+1) + step(cur+2))%MOD
  return memo[cur]
 
print(step(0)%MOD)

Fixed submission:
N,M = map(int,input().split())
MOD = 10**9+7
dp = [0] * (N+1)
dp[1] = 1
for _ in range(M):
  dp[int(input())] = -1
if N<2:
  print(dp[N])
  exit()

if dp[2] != -1:
  dp[2] = 1
for i in range(N+1):
  if dp[i] == -1: continue
  if i-1>=0 and dp[i-1] != -1:
    dp[i] += dp[i-1]
  if i-2>=0 and dp[i-2] != -1:
    dp[i] += dp[i-2]
  dp[i] %= MOD

print(dp[N])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)
N,M = map(int,input().split())
A = []
MOD = 10**9+7
memo = {}
for _ in range(M):
  A.append(int(input()))
def step(cur):
  if cur in memo:
    return memo[cur]
  if cur == N:
    memo[cur] = 1
    return memo[cur]
  if cur > N or cur in A:
    memo[cur] = 0
    return memo[cur]

  memo[cur] = (step(cur+1) + step(cur+2))%MOD
  return memo[cur]

print(step(0)%MOD)


Fixed submission:
N,M = map(int,input().split())
MOD = 10**9+7
dp = [0] * (N+1)
dp[1] = 1
for _ in range(M):
  dp[int(input())] = -1
if N<2:
  print(dp[N])
  exit()

if dp[2] != -1:
  dp[2] = 1
for i in range(N+1):
  if dp[i] == -1: continue
  if i-1>=0 and dp[i-1] != -1:
    dp[i] += dp[i-1]
  if i-2>=0 and dp[i-2] != -1:
    dp[i] += dp[i-2]
  dp[i] %= MOD

print(dp[N])

Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
A = []
MOD = 10**9+7
memo = {}
for _ in range(M):
  A.append(int(input()))
def step(cur):
  global res
  if cur in memo:
    return memo[cur]
  if cur == N:
    memo[cur] = 1
    return memo[cur]
  if cur > N or cur in A:
    memo[cur] = 0
    return memo[cur]

  memo[cur] = (step(cur+1) + step(cur+2))%MOD
  return memo[cur]

res = 0
print(step(0)%MOD)


Fixed submission:
N,M = map(int,input().split())
MOD = 10**9+7
dp = [0] * (N+1)
dp[1] = 1
for _ in range(M):
  dp[int(input())] = -1
if N<2:
  print(dp[N])
  exit()

if dp[2] != -1:
  dp[2] = 1
for i in range(N+1):
  if dp[i] == -1: continue
  if i-1>=0 and dp[i-1] != -1:
    dp[i] += dp[i-1]
  if i-2>=0 and dp[i-2] != -1:
    dp[i] += dp[i-2]
  dp[i] %= MOD

print(dp[N])
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
A = [0] * (N+1)
for _ in range(M):
  l,r = map(int,input().split())
  for i in range(l, r+1):
    A[i] += 1

print(A.count(M))

Fixed submission:
N,M = map(int,input().split())
A = [0] * (N+2)
for _ in range(M):
  l,r = map(int,input().split())
  A[l] += 1
  A[r+1] -= 1

for i in range(N):
  A[i+1] += A[i]

print(A.count(M))
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

C = []
for _ in range(M):
  b,c = map(int,input().split())
  for _ in range(b):
    C.append(c)
C.sort(reverse=True)

curj = 0
res = sum(A)
for i,a in enumerate(A):
  while curj+1 < len(C) and C[curj] <= a:
    curj += 1

  if curj < len(C):
    c = C[curj]
    if c > a:
      res = res - a + c
      curj += 1
    else:
      break
  else:
    break

print(res)


Fixed submission:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

cards = []
for _ in range(M):
  b,c = map(int,input().split())
  cards.append([c,b])
cards.sort(key=lambda x: -x[0])

res = 0
idx = 0
left = cards[idx][1]
for i,a in enumerate(A):
  if a > cards[idx][0]:
    res += sum(A[i:])
    break
  else:
    res += cards[idx][0]

    left -= 1
    if left <= 0:
      idx += 1
      if idx >= M:
        if i+1 < N:
          res += sum(A[i+1:])
        break
      else:
        left = cards[idx][1]

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
heapq.heapify(A)
curmin = min(A)

for _ in range(M):
  b,c = map(int,input().split())
  if c <= curmin: continue

  cnt = 0
  while cnt < b and len(A)>0:
    a = heapq.heappop(A)
    if a >= c:
      heapq.heappush(A,a)
      break
    cnt += 1
    heapq.heappush(A,c)

  # for _ in range(cnt):
  #   heapq.heappush(A,c)

  curmin = min(A[0], c)

print(sum(A))

Fixed submission:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

cards = []
for _ in range(M):
  b,c = map(int,input().split())
  cards.append([c,b])
cards.sort(key=lambda x: -x[0])

res = 0
idx = 0
left = cards[idx][1]
for i,a in enumerate(A):
  if a > cards[idx][0]:
    res += sum(A[i:])
    break
  else:
    res += cards[idx][0]

    left -= 1
    if left <= 0:
      idx += 1
      if idx >= M:
        if i+1 < N:
          res += sum(A[i+1:])
        break
      else:
        left = cards[idx][1]

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
heapq.heapify(A)
curmin = min(A)

for _ in range(M):
  b,c = map(int,input().split())
  if c <= curmin: continue

  cnt = 0
  while cnt < b and len(A)>0:
    a = heapq.heappop(A)
    if a >= c:
      heapq.heappush(A,a)
      break
    cnt += 1

  for _ in range(cnt):
    heapq.heappush(A,c)

  curmin = min(A[0], c)

print(sum(A))

Fixed submission:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

cards = []
for _ in range(M):
  b,c = map(int,input().split())
  cards.append([c,b])
cards.sort(key=lambda x: -x[0])

res = 0
idx = 0
left = cards[idx][1]
for i,a in enumerate(A):
  if a > cards[idx][0]:
    res += sum(A[i:])
    break
  else:
    res += cards[idx][0]

    left -= 1
    if left <= 0:
      idx += 1
      if idx >= M:
        if i+1 < N:
          res += sum(A[i+1:])
        break
      else:
        left = cards[idx][1]

print(res)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = [ int(i) for i in input().split(" ")]

INF = 10000000000
dp = [ INF for i in range(len(a))]
dp[0] = 0

def frog(i):
  if dp[i] < INF: return dp[i]
  
  if i == 0: return 0

  res = INF
  res = min(res, frog(i-1) + abs(a[i-1] - a[i]))
  if i > 1: 
    res = min(res, frog(i-2) + abs(a[i-2] - a[i]))

  dp[i] = res
  return res

print(frog(n-1))

Fixed submission:
n = int(input())
a = [ int(i) for i in input().split(" ")]

dp = [ -1 for i in range(len(a))]
dp[0] = 0

for i in range(1, len(a)):
  onestep = dp[i-1] + abs(a[i-1] - a[i])
  if i - 2 < 0:
    twostep = onestep
  else:
    twostep = dp[i-2] + abs(a[i-2] - a[i])
  
  dp[i] = min(onestep, twostep)

print(dp[-1])

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = [ int(i) for i in input().split(" ")]

INF = 10000000000
dp = [ INF for i in range(len(a))]

def frog(i):
  if dp[i] < INF: return dp[i]
  
  if i == 0: return 0

  res = INF
  res = min(res, frog(i-1) + abs(a[i-1] - a[i]))
  if i > 1: 
    res = min(res, frog(i-2) + abs(a[i-2] - a[i]))

  dp[i] = res
  return res

print(frog(n-1))

Fixed submission:
n = int(input())
a = [ int(i) for i in input().split(" ")]

dp = [ -1 for i in range(len(a))]
dp[0] = 0

for i in range(1, len(a)):
  onestep = dp[i-1] + abs(a[i-1] - a[i])
  if i - 2 < 0:
    twostep = onestep
  else:
    twostep = dp[i-2] + abs(a[i-2] - a[i])
  
  dp[i] = min(onestep, twostep)

print(dp[-1])

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = [ int(i) for i in input().split(" ")]

INF = 10000000000
dp = [ INF for i in range(len(a))]
dp[0] = 0

def frog(i):
  if dp[i] < INF: return dp[i]
  
  if i == 0: return 0

  res = INF
  res = min(res, frog(i-1) + abs(a[i-1] - a[i]))
  min(res, frog(i-1) + abs(a[i-2] - a[i]))

  dp[i] = res
  return res

print(frog(n-1))

Fixed submission:
n = int(input())
a = [ int(i) for i in input().split(" ")]

dp = [ -1 for i in range(len(a))]
dp[0] = 0

for i in range(1, len(a)):
  onestep = dp[i-1] + abs(a[i-1] - a[i])
  if i - 2 < 0:
    twostep = onestep
  else:
    twostep = dp[i-2] + abs(a[i-2] - a[i])
  
  dp[i] = min(onestep, twostep)

print(dp[-1])

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = [ int(i) for i in input().split(" ")]

INF = 10000000000
dp = [ INF for i in range(len(a))]
dp[0] = 0

def frog(i):
  if dp[i] < INF: return dp[i]
  
  if i == 0: return 0

  res = INF
  res = min(res, frog(i-1) + abs(a[i-1] - a[i]))
  print("calc i-1", i)
  min(res, frog(i-1) + abs(a[i-2] - a[i]))
  print("calc i-2", i)

  dp[i] = res
  return res

print(frog(n-1))

Fixed submission:
n = int(input())
a = [ int(i) for i in input().split(" ")]

dp = [ -1 for i in range(len(a))]
dp[0] = 0

for i in range(1, len(a)):
  onestep = dp[i-1] + abs(a[i-1] - a[i])
  if i - 2 < 0:
    twostep = onestep
  else:
    twostep = dp[i-2] + abs(a[i-2] - a[i])
  
  dp[i] = min(onestep, twostep)

print(dp[-1])
Buggy python submission (verdict: Runtime Error):
n = int(input())

a = []
for i in range(n):
  arr = list(map(int, input().split()))
  a.append(arr)

for i in range(0, n):
  for j in range(0, 3):
    for k in range(3):
      if (j == k): continue
      dp[i+1][k] = max(dp[i+1][k], dp[i][j] + a[i][k])

print(max(dp[-1]))

Fixed submission:
n = int(input())

a = []
for i in range(n):
  arr = list(map(int, input().split()))
  a.append(arr)

INF = -10 ** 18

dp = [ [INF] * 3 for i in range(0, n+1)]
dp[0] = [0] * 3

for i in range(0, n):
  for j in range(0, 3):
    for k in range(3):
      if (j == k): continue
      dp[i+1][k] = max(dp[i+1][k], dp[i][j] + a[i][k])

print(max(dp[-1]))
Buggy python submission (verdict: Runtime Error):
from collections import Counter
N = int(input())
dic = Counter()
for _ in range(N):
  dic[input()] += 1
M = int(input())
for _ in range(N):
  dic[input()] -= 1
 
if dic.most_common():
  freq = dic.most_common()[0][1]
  print(max(freq, 0))
else:
  print(0)

Fixed submission:
from collections import Counter
N = int(input())
dic = Counter()
for _ in range(N):
  dic[input()] += 1
M = int(input())
for _ in range(M):
  dic[input()] -= 1
 
if dic.most_common():
  freq = dic.most_common()[0][1]
  print(max(freq, 0))
else:
  print(0)

Buggy python submission (verdict: Runtime Error):
from collections import Counter
N = int(input())
dic = Counter()
for _ in range(N):
  dic[input()] += 1
M = int(input())
for _ in range(N):
  dic[input()] -= 1

if c.most_common():
  freq = c.most_common()[0][1]
  print(freq, 0)
else:
  print(0)


Fixed submission:
from collections import Counter
N = int(input())
dic = Counter()
for _ in range(N):
  dic[input()] += 1
M = int(input())
for _ in range(M):
  dic[input()] -= 1
 
if dic.most_common():
  freq = dic.most_common()[0][1]
  print(max(freq, 0))
else:
  print(0)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
mat = []
for _ in range(n):
  mat.append(list(map(int,input().split())))

d = [[False]*n for _ in range(n)]

for k in range(n):
  for i in range(n):
    for j in range(n):
      if mat[i][j] > mat[i][k]+mat[k][j]:
        print(-1)
        exit()

      if mat[i][j] == mat[i][k]+mat[k][j] and mat[i][k]>0 and mat[k][j]>0:
        d[i][j] = True

ans = 0
for i in range(n):
  for j in range(i+1, n):
    if not d[i][j]:
      ans += mat[i][j]

print(ans)

Fixed submission:
import copy
N = int(input())

graph = []
for i in range(N):
  graph.append( list(map(int,input().split())) )

dp = copy.deepcopy(graph)
for k in range(N):
  for i in range(N):
    for j in range(N):
      dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])

res = 0

for i in range(N):
  for j in range(N):
    if dp[i][j] < graph[i][j]:
      print(-1)
      exit()
    elif dp[i][j] == graph[i][j]:
      flg = True
      for k in range(N):
        if k!=i and k!=j and dp[i][j] == dp[i][k]+dp[k][j]:
          flg = False
      if flg:
        res += dp[i][j]

print(res//2)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N = int(input())
a = list(map(int, input().split()))
m = len(a) // 2

cumsumA = []
prefix = [x for x in a[:N]]
heapq.heapify(prefix)
cumsumA.append(sum(prefix))
for k in range(N, 2*N):
  heapq.heappush(prefix, a[k])
  heapq.heappop(prefix)
  cumsumA.append(sum(prefix))

cumsumB = []
suffix = [-x for x in a[2*N:]]
heapq.heapify(suffix)
cumsumB.append(-sum(suffix))
for k in range(2*N-1, N-1, -1):
  heapq.heappush(suffix, -a[k])
  heapq.heappop(suffix)
  cumsumB.append(-sum(suffix))

res = -float('inf')
for i in range(0, len(cumsumA)):
  res = max(res, cumsumA[i] - cumsumB[len(cumsumA)-i-1])

print(res)
  


Fixed submission:
import heapq
N = int(input())
a = list(map(int, input().split()))
m = len(a) // 2

cumsumA = []
prefix = [x for x in a[:N]]
heapq.heapify(prefix)
cumsumA.append(sum(prefix))
cursum = sum(prefix)
for k in range(N, 2*N):
  heapq.heappush(prefix, a[k])
  ele = heapq.heappop(prefix)
  cursum = cursum + a[k] - ele
  cumsumA.append(cursum)
  # cumsumA.append(sum(prefix))

cumsumB = []
suffix = [-x for x in a[2*N:]]
heapq.heapify(suffix)
cumsumB.append(-sum(suffix))
cursum = -sum(suffix)
for k in range(2*N-1, N-1, -1):
  heapq.heappush(suffix, -a[k])
  ele = heapq.heappop(suffix)
  cursum = cursum + a[k] + ele
  cumsumB.append(cursum)

res = -float('inf')
for i in range(0, len(cumsumA)):
  res = max(res, cumsumA[i] - cumsumB[len(cumsumA)-i-1])

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
K, S = list(map(int, input().split()))

res = 0

for x in range(K+1):
  if x > S: continue
  for y in range(K+1):
    if x+y > S: continue
    for z in range(K+1):
      if x+y+z > S: continue
      if x + y + z == S:
        res += 1

print(res)

Fixed submission:
K, S = list(map(int, input().split()))

res = 0

for x in range(K+1):
  for y in range(K+1):
    z = S - x - y
    if z >= 0 and z <= K:
      res += 1

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
K, S = list(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:
K, S = list(map(int, input().split()))

res = 0

for x in range(K+1):
  for y in range(K+1):
    z = S - x - y
    if z >= 0 and z <= K:
      res += 1

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
K, S = list(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:
K, S = list(map(int, input().split()))

res = 0

for x in range(K+1):
  for y in range(K+1):
    z = S - x - y
    if z >= 0 and z <= K:
      res += 1

print(res)