Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from fractions import gcd
from functools import reduce

N, M = map(int, input().split())
*a, = map(int, input().split())
lcm = reduce(lambda x,y:x*y//gcd(x,y), a)

m = 10**9
for i in map(lambda x:lcm//x, a):
    if i%2==0:
        print(0)
        break
    m = min(m, i)
else:
    start = int(lcm*0.5)
    print((M-start)//lcm+1)

Fixed submission:
from fractions import gcd
from functools import reduce

N, M = map(int, input().split())
*a, = map(int, input().split())
lcm = reduce(lambda x,y:x*y//gcd(x,y), a)

for i in map(lambda x:lcm//x, a):
    if i%2==0:
        print(0)
        break
else:
    start = lcm//2
    print((M-start)//lcm+1)

Buggy python submission (verdict: Runtime Error):
from fractions import gcd
from functools import reduce

N, M = map(int, input().split())
*a, = map(int, input().split())
lcm = reduce(lambda x,y:x*y//gcd(x,y), a)

m = 10**9
for i in map(lambda x:lcm//x, a):
    if i%2==0:
        print(0)
        break
    m = min(m, i)
else:
    if m==1:
        start = int(lcm*1.5)
    else:
        start = int(lcm*0.5)

    print((M-start)//lcm+1)

Fixed submission:
from fractions import gcd
from functools import reduce

N, M = map(int, input().split())
*a, = map(int, input().split())
lcm = reduce(lambda x,y:x*y//gcd(x,y), a)

for i in map(lambda x:lcm//x, a):
    if i%2==0:
        print(0)
        break
else:
    start = lcm//2
    print((M-start)//lcm+1)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations

N = int(input())
*C, = map(int, input().split())
C.sort()
mod = 10**9+7

ans = 0
for k in range(1, N+1):
    for m in combinations(C, k):
        for j, p in enumerate(m):
            ans += (k-j)*p

ans *= pow(2, N, mod)
ans %= mod
print(ans)

Fixed submission:
N = int(input())
*C, = map(int, input().split())
C.sort(reverse=True)

mod = 10**9+7

ans = 0
for i,c in enumerate(C, start=1):
    ans += (c*(i+1))
ans *= (4**(N-1))
ans %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
*A, = map(int, input().split())
print("bust" if sum(a)>=22 else "win")

Fixed submission:
*A, = map(int, input().split())
print("bust" if sum(A)>=22 else "win")
Buggy python submission (verdict: Runtime Error):
from itertools import product

N = int(input())
c = product(range(2), repeat=N)
d = [[] for _ in range(N)]

for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        d[i].append((x, y))


ans = 0
for l in c:
    o = [None]*N
    is_conflict = False
    for i, j in enumerate(l):
        if j==0:continue
        for x, y in d[i]:
            if (o[x-1]!=None and o[x-1]!=y) or l[x-1]!=y:
                is_conflict = True
                break
            o[x-1] = y
        if is_conflict == True:
            break
    else:
        ans = mas(ans, sum(l))

print(ans)

Fixed submission:
from itertools import product

N = int(input())
c = product(range(2), repeat=N)
d = [[] for _ in range(N)]

for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        d[i].append((x, y))


ans = 0
for l in c:
    o = [None]*N
    is_conflict = False
    for i, j in enumerate(l):
        if j==0:continue
        for x, y in d[i]:
            if (o[x-1]!=None and o[x-1]!=y) or l[x-1]!=y:
                is_conflict = True
                break
            o[x-1] = y
        if is_conflict == True:
            break
    else:
        ans = max(ans, sum(l))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

N = int(input())
S = input()
ans = 0

for i in range(1000):
    s = str(i).zfill(3)
    for i in range(N):
        if S[i]==s[0]:
            p = i
            break
    else:
        continue
    for i in range(p+1, N):
        if S[i]==s[1]:
            p = i
            break
    else:
        continue

    for i in range(p+1, N):
        if S[i]==s[2]:
            p = i
            break
    else:
        continue
    
    ans += 1

print(ans)


Fixed submission:
n = int(input())
s = input()
ans = 0

for i in range(1000):
    t = str(i).zfill(3)
    isExists = [False]*3
    pos = 0
    for (p,j) in enumerate(t):
        while pos<n:
            if s[pos]==j:
                pos += 1
                isExists[p] = True
                break
            pos += 1
    if all(isExists):
        ans += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import Counter

N, K = map(int, input().split())
*A, = map(int, input().split())
MOD = 10**9+7
ac = [0]*(N+1)

for i in range(1, N+1):
    ac[i] = (ac[i-1]+A[i-1])%K
for i in range(N+1):
    ac[i] -= i
    ac[i] %= K

c = Counter()
for i in range(K-1):
    c[ac[i]] += 1
ans = 0
for i in range(N+1):
    if i+K-1<=N:
        c[ac[i+K-1]] += 1
    ans += c[ac[i]]-1
    c[ac[i]] -= 1

print(ans)

Fixed submission:
from collections import Counter

N, K = map(int, input().split())
*A, = map(int, input().split())
MOD = 10**9+7
S = [0]*(N+1)
c = Counter()
c[0] = 1
ans = 0

for i in range(N):
    S[i+1] = (S[i]+A[i]-1)%K
    if i+1-K>=0:
        c[S[i+1-K]] -= 1
    ans += c[S[i+1]]
    c[S[i+1]] += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
X, Y = map(int, input().split())
d = defaultdict(int)
d[1] = 300000
d[2] = 200000
d[3] = 100000
ans = d[X]+d[Y]
if X==1 and Y==1:
  ans += 400000
print(ans

Fixed submission:
from collections import defaultdict
X, Y = map(int, input().split())
d = defaultdict(int)
d[1] = 300000
d[2] = 200000
d[3] = 100000
ans = d[X]+d[Y]
if X==1 and Y==1:
  ans += 400000
print(ans)

Buggy python submission (verdict: Runtime Error):
X, Y = map(int, input().split())
d = {1:300000, 2:200000, 3:100000}
ans = d[X]+d[Y]
if X==1 and Y==1:
  ans += 400000
print(ans)

Fixed submission:
from collections import defaultdict
X, Y = map(int, input().split())
d = defaultdict(int)
d[1] = 300000
d[2] = 200000
d[3] = 100000
ans = d[X]+d[Y]
if X==1 and Y==1:
  ans += 400000
print(ans)

Buggy python submission (verdict: Runtime Error):
X, Y = map(int, input().split())
d = {1:300000, 2:200000, 3:100000}
ans = d[X]+d[Y]
if X==1 and Y==1:
  ans += 400000
print(ans

Fixed submission:
from collections import defaultdict
X, Y = map(int, input().split())
d = defaultdict(int)
d[1] = 300000
d[2] = 200000
d[3] = 100000
ans = d[X]+d[Y]
if X==1 and Y==1:
  ans += 400000
print(ans)
Buggy python submission (verdict: Runtime Error):
X, Y = map(int, input().split())

if (2*X-Y)%3==0 and (2*Y-X)%3==0:
    a = (2*X-Y)//3
    b = X-2*a
    MOD = 10**9+7
    n = a+b+1
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
        fac[i] = i*fac[i-1]%MOD
        rev[i] = pow(fac[i], MOD-2, MOD)
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

    print(comb(a+b, a))
else:
    print(0)


Fixed submission:
X, Y = map(int, input().split())

mod = 10**9+7
N = 1333334
fac = [1]*(N+1)
rev = [1]*(N+1)
 
for i in range(1,N+1):
  fac[i] = i*fac[i-1]%mod
  rev[i] = pow(fac[i], mod-2, mod)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%mod

a, b = (2*X-Y)//3, (2*Y-X)//3
if a<0 or b<0 or (2*X-Y)%3 or (2*Y-X)%3:
    print(0)
else:
    print(comb(a+b, a))

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

if (2*X-Y)%3 or (2*Y-X)%3:
    print(0)
else:
    a, b = (2*X-Y)//3, X-2*a
    MOD = 10**9+7
    n = a+b+1
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
        fac[i] = i*fac[i-1]%MOD
        rev[i] = pow(fac[i], MOD-2, MOD)
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

    print(comb(a+b, a))

Fixed submission:
X, Y = map(int, input().split())

mod = 10**9+7
N = 1333334
fac = [1]*(N+1)
rev = [1]*(N+1)
 
for i in range(1,N+1):
  fac[i] = i*fac[i-1]%mod
  rev[i] = pow(fac[i], mod-2, mod)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%mod

a, b = (2*X-Y)//3, (2*Y-X)//3
if a<0 or b<0 or (2*X-Y)%3 or (2*Y-X)%3:
    print(0)
else:
    print(comb(a+b, a))

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

if (2*X-Y)%3:
    print(0)
else:
    a = (2*X-Y)//3
    b = X-2*a

    MOD = 10**9+7
    n = a+b+1
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
        fac[i] = i*fac[i-1]%MOD
        rev[i] = pow(fac[i], MOD-2, MOD)
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

    print(comb(a+b, a))

Fixed submission:
X, Y = map(int, input().split())

mod = 10**9+7
N = 1333334
fac = [1]*(N+1)
rev = [1]*(N+1)
 
for i in range(1,N+1):
  fac[i] = i*fac[i-1]%mod
  rev[i] = pow(fac[i], mod-2, mod)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%mod

a, b = (2*X-Y)//3, (2*Y-X)//3
if a<0 or b<0 or (2*X-Y)%3 or (2*Y-X)%3:
    print(0)
else:
    print(comb(a+b, a))

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

mod = 10**9+7
N = 670000
fac = [1]*(N+1)
rev = [1]*(N+1)
 
for i in range(1,N+1):
  fac[i] = i*fac[i-1]%mod
  rev[i] = pow(fac[i], mod-2, mod)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%mod

a, b = (2*X-Y)//3, (2*Y-X)//3
if a<0 or b<0:
    print(0)
else:
    print(comb(a+b, a))


Fixed submission:
X, Y = map(int, input().split())

mod = 10**9+7
N = 1333334
fac = [1]*(N+1)
rev = [1]*(N+1)
 
for i in range(1,N+1):
  fac[i] = i*fac[i-1]%mod
  rev[i] = pow(fac[i], mod-2, mod)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%mod

a, b = (2*X-Y)//3, (2*Y-X)//3
if a<0 or b<0 or (2*X-Y)%3 or (2*Y-X)%3:
    print(0)
else:
    print(comb(a+b, a))
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
*A, = map(int, input().split())
*F, = map(int, input().split())
A.sort()
F.sort(reverse=True)

def f(x):
    ans = 0
    for i,j in zip(A, F):
        ans += (i*j-x+j-1)//j if i*j-x>=0 else 0
    return ans<=K

l, r = -1, 10**18+1
while r-l>1:
    mid = (r+l)//2
    if f(mid):
        r = mid
    else:
        l = mid

print(r)

Fixed submission:
N, K = map(int, input().split())
*A, = map(int, input().split())
*F, = map(int, input().split())
A.sort()
F.sort(reverse=True)

def f(x):
    ans = 0
    for i,j in zip(A, F):
        ans += (i*j-x+j-1)//j if i*j-x>=0 else 0
    return ans<=K

l, r = -1, 10**18+1
while r-l>1:
    mid = (r+l)//2
    if f(mid):
        r = mid
    else:
        l = mid

print(r)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
l = []
for _ in range(M):
    a, b = map(int, input().split())
    c = tuple(map(int, input().split()))
    l.append((a, c))

inf = 10**12
dp = [inf]*(2**N)
dp[0] = 0

for i in range(2**N):
    for cost, j in l:
        v=0
        for k in j:
            v+=2**(k-1)
        dp[i|v] = min(dp[i|v], dp[i]+cost)

print(dp[2**N-1] if dp[2**N-1]!=inf else -1)

Fixed submission:
N, M = map(int, input().split())
l = []
for _ in range(M):
    a, b = map(int, input().split())
    c = tuple(map(int, input().split()))
    l.append((a, c))

inf = 10**12
dp = [inf]*(2**N)
dp[0] = 0

for i in range(2**N):
    for cost, j in l:
        v=0
        for k in j:
            v+=2**(k-1)
        dp[i|v] = min(dp[i|v], dp[i]+cost)

print(dp[2**N-1] if dp[2**N-1]!=inf else -1)
Buggy python submission (verdict: Runtime Error):
H, W, A, B = map(int, input().split())
if H==1:
    print("".join(map(str,[1]*A+[0]*(W-A))))
elif W==1:
    for i in [1]*B+[0]*(H-B):
        print(i)
elif W%A==0 and H%B==0 and A*(H//B)==W:
    a, b = 0, 0
    l = [[0]*W for _ in range(H)]
    
    while B*b<H and A*a<W:
        for i in range(B):
            for j in range(A):
                l[B*b+i][A*a+j] = 1
        a += 1
        b += 1
    for i in l:
        print("".join(map(str,i)))
else:
    print("No")

Fixed submission:
H, W, A, B = map(int, input().split())
l = [[0]*W for _ in range(H)]

for i in range(B):
    for j in range(A):
        l[i][j] = 1

for i in range(B, H):
    for j in range(A, W):
        l[i][j] = 1

for i in l:
    print("".join(map(str, i)))

Buggy python submission (verdict: Runtime Error):
H, W, A, B = map(int, input().split())
if H==1:
    print("".join(map(str,[1]*A+[0]*(W-A))))
elif W==1:
    for i in [1]*B+[0]*(H-B):
        print(i)
elif W%A==0 and H%B==0 and A*(H//B)==W:
    a, b = 0, 0
    l = [[0]*W for _ in range(H)]
    while B*b<H and A*a<W:
        for i in range(A):
            for j in range(B):
                l[A*a+i][B*b+j] = 1
        a += 1
        b += 1
    for i in l:
        print("".join(map(str,i)))
else:
    print("No")

Fixed submission:
H, W, A, B = map(int, input().split())
l = [[0]*W for _ in range(H)]

for i in range(B):
    for j in range(A):
        l[i][j] = 1

for i in range(B, H):
    for j in range(A, W):
        l[i][j] = 1

for i in l:
    print("".join(map(str, i)))

Buggy python submission (verdict: Runtime Error):
H, W, A, B = map(int, input().split())
if H==1:
    print("".join(map(str,[1]*A+[0]*(W-A))))
elif W==1:
    for i in [1]*B+[0]*(H-B):
        print(i)
elif W%A==0 and H%B==0:
    a, b = 0, 0
    l = [[0]*W for _ in range(H)]
    while B*b<H and A*a<W:
        for i in range(A):
            for j in range(B):
                l[A*a+i][B*b+j] = 1
        a += 1
        b += 1
    for i in l:
        print("".join(map(str,i)))
else:
    print("No")

Fixed submission:
H, W, A, B = map(int, input().split())
l = [[0]*W for _ in range(H)]

for i in range(B):
    for j in range(A):
        l[i][j] = 1

for i in range(B, H):
    for j in range(A, W):
        l[i][j] = 1

for i in l:
    print("".join(map(str, i)))

Buggy python submission (verdict: Runtime Error):
H, W, A, B = map(int, input().split())
if H==1:
    print("".join(map(str,[1]*A+[0]*(W-A))))
elif W==1:
    for i in [1]*B+[0]*(H-B):
        print(i)
elif W%A==0 and H%B==0:
    a, b = 0, 0
    l = [[0]*W for _ in range(H)]
    while B*b<H and A*a<W:
        for i in range(A):
            for j in range(B):
                l[a+i][b+j] = 1
        a += 1
        b += 1
    for i in l:
        print("".join(map(str,i)))
else:
    print("No")

Fixed submission:
H, W, A, B = map(int, input().split())
l = [[0]*W for _ in range(H)]

for i in range(B):
    for j in range(A):
        l[i][j] = 1

for i in range(B, H):
    for j in range(A, W):
        l[i][j] = 1

for i in l:
    print("".join(map(str, i)))
Buggy python submission (verdict: Runtime Error):
T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())

d1 = T1*(A1-B1)
d2 = T2*(A2-B2)
if d1>d2:
    d1 *= -1
    d2 *= -1

if (d1>0 and d1+d2>0) or (d1<0 and d1+d2<0):
    print(0)
elif d1+d2==0:
    print("infinity")
else:
    v = (abs(d1)//(d1+d2))
    ans = v*2
    pos = d1+v*(d1+d2)
    if pos<0 and pos+d2>=0:
        ans += 1
    print(pos)

Fixed submission:
from operator import add


class SegTree():
    def __init__(self, N, e, operator_func=add):
        self.e = e # 単位元
        self.size = N
        self.node = [self.e] * (2*N)
        self.operator_func = operator_func # 処理(add or xor max minなど)

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.operator_func(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size-1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.operator_func(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        # [l, r) についてqueryを求める
        x = self.e
        l += self.size
        r += self.size

        while l<r:
            if l&1:
                x = self.operator_func(x, self.node[l-1])
                l += 1
            if r&1:
                r -= 1
                x = self.operator_func(x, self.node[r-1])
            l >>= 1
            r >>= 1
        return x


N, K = map(int, input().split())
*P, = map(int, input().split())
INF = 10**12

tree_max = SegTree(N, -INF, operator_func=max)
tree_max.set_list(P)
tree_min = SegTree(N, INF, operator_func=min)
tree_min.set_list(P)
tree_monoinc = SegTree(N, INF, operator_func=min)
for i in range(N):
    tree_monoinc.update(i, P[i]-P[i-1] if i else 0)

def isMonoinc(l, r):
    # [l, r)
    l += 1
    return tree_monoinc.get(l, r)>=0

ans = N-K+1
orig = 0

for i in range(N-K+1):
    if isMonoinc(i, i+K):
        orig = 1
        ans -= 1
    elif i+K<N and tree_max.get(i, i+K+1)==P[i+K] and tree_min.get(i, i+K+1)==P[i]:
        ans -= 1

ans += orig
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# Cumulative Sum Bisect


class SegTree():
    def __init__(self, N, e=0, operator_func=lambda x,y:x+y):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x

    def bisect_left(self, x):
        # O(log^2N)なので遅い
        left, right = 0, self.size
        while right-left>1:
            mid = (left+right)//2
            v = self.get(0, mid)
            if v >= x:
                right = mid
            else:
                left = mid
        return left+1


if __name__ == "__main__":
    # ABC140-E sample
    N = int(input())
    l = [(j, i) for i, j in enumerate(map(int, input().split()))]
    l.sort(key=lambda x:-x[0])
    tree = SegTree(N)

    ans = 0

    for n, (value, idx) in enumerate(l, start=1):
        v = tree.get(0, idx + 1)
        a = tree.bisect_left(v - 1) if v > 1 else 0
        b = tree.bisect_left(v - 0) if v else 0
        c = tree.bisect_left(v + 1) if n-v>1 else N+1
        d = tree.bisect_left(v + 2) if n-v>2 else N+1

        tree.update(idx, 1)
        idx += 1
        ans += ((b-a)*(c-idx)+(d-c)*(idx-b)) * value

    print(ans)

Fixed submission:
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        for i in range(self.depth + 1)[::-1]:
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_


N = int(input())
l = [(j, i) for i, j in enumerate(map(int, input().split()))]
l.sort(key=lambda x:-x[0])
tree = BIT(N)
m = [0]*N
ans = 0

for value, idx in l:
    v = tree.sum(idx + 1)

    a = tree.lower_bound(v - 1)[0] if v>1 else 0
    b = tree.lower_bound(v - 0)[0] if v else 0
    c = tree.lower_bound(v + 1)[0] 
    d = tree.lower_bound(v + 2)[0]

    tree.add(idx + 1, 1)
    idx += 1
    ans += ((b-a)*(c-idx)+(d-c)*(idx-b)) * value

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

N = int(input())
l = [deque([])]+[deque(map(int, input().split())) for _ in range(N)]

v = 0
ans = 0
t = N*(N-1)//2

while v<t and ans<t:
    used = set()
    for n in range(1, N+1):
        if n in used:continue
        if not l[n]:continue
        pair = l[n][0]
        b = l[pair][0]
        if pair in used:continue

        if b==n:
            l[n].popleft()
            l[pair].popleft()
            used|={n,pair}
            v += 1
    ans += 1

if ans==t and ans!=v:
    print(-1)
else:
    print(ans)

Fixed submission:
from collections import deque

N = int(input())
l = [deque([])]+[deque(map(int, input().split())) for _ in range(N)]

v = 0
ans = 0
t = N*(N-1)//2

last_used = set(range(1, N+1))
while v<t and ans<t:
    used = set()
    for n in last_used:
        if n in used:continue
        if not l[n]:continue
        pair = l[n][0]
        b = l[pair][0]
        if pair in used:continue

        if b==n:
            l[n].popleft()
            l[pair].popleft()
            used|={n,pair}
            v += 1
    last_used = used
    ans += 1

if ans==t and ans!=v:
    print(-1)
else:
    print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict, deque
from heapq import heappop, heappush
import sys
input = sys.stdin.readline

N, M, P = map(int, input().split())
d = defaultdict(list)
candidate = []
l = []

for _ in range(M):
    a, b, c = map(int, input().split())
    
    if a==b:
        if P-c<0:
            candidate.append(a)
    else:
        l.append((a, b, P-c))
        d[a].append((P-c, b))

def check():
    if candidate:
        visited = [False]*(N+1)
        visited[1] = True
        q = deque([1])
        while q:
            s = q.popleft()
            for _, t in d[s]:
                if visited[t]:continue
                visited[t] = True
                q.append(t)
        
        candidate2 = [i for i in candidate if visited[i]]
        for i in candidate2:
            visited = [False]*(N+1)
            visited[i] = True
            q = deque([i])
            while q:
                s = q.popleft()
                for _, t in d[s]:
                    if visited[t]:continue
                    visited[t] = True
                    q.append(t)
            if visited[N]:
                return False
    return True

def shortest_path(s):
    INF = 10**18
    dist = [INF]*(N+1)
    dist[s] = 0

    while 1:
        update = False

        for a, b, c in l:
            if dist[a]!=INF and dist[b]>dist[a]+c:
                dist[b] = dist[a]+c
        if not update:
            break
    return dist

if check():
    d1 = shortest_path(1)
    dN = shortest_path(N)
    if dN[1]!=INF and d1[N]+dN[1]<0:
        print(-1)
    elif d1[N]<0:
        print(-d1[N])
    else:
        print(0)
else:
    print(-1)

Fixed submission:
from collections import defaultdict, deque
from heapq import heappop, heappush
import sys
input = sys.stdin.readline

N, M, P = map(int, input().split())
d = defaultdict(list)
e = defaultdict(list)
cd = defaultdict(list)
l = []

for _ in range(M):
    a, b, c = map(int, input().split())
    cd[a].append((b, P-c))
    d[a].append(b)
    e[b].append(a)

def check_visited(d, start):
    visited = [False]*(N+1)
    visited[start] = True
    q = deque([start])
    while q:
        s = q.popleft()
        for t in d[s]:
            if visited[t]:continue
            visited[t] = True
            q.append(t)
    
    s = set()
    for i in range(1, N+1):
        if visited[i]:
            s.add(i)
    return s

def shortest_path(s):
    INF = 10**18
    dist = [float("inf")]*(N+1)
    dist[s] = 0

    for i in range(N):
        for a, b, c in l:
            if dist[b]>dist[a]+c:
                dist[b] = dist[a]+c
                if i==N-1:
                    return dist, True
    return dist, False

add_l = check_visited(d, 1)&check_visited(e, N)
for a in add_l:
    for b, c in cd[a]:
        l.append((a, b, c))
d1, neg = shortest_path(1)
if neg:
    print(-1)
elif d1[N]<0:
    print(-d1[N])
else:
    print(0)