Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
S = [input() for _ in range(H)]
# print(S)
dr = [ 1, 0]
dc = [ 0, 1]
ans = 1001001001

def dfs(r,c,cnt,flg):
    """
    r, c
    cnt: 連続黒の回数
    flg: 1: 現在白（黒に来たらcnt+1）, 0: 現在黒
    """
    global ans
    if S[r][c] == '#':
        if flg:
            cnt += 1
            black_flg = 0
    else:
        flg = 1

    if r==H-1 and c ==W-1:
        ans = min(ans, cnt)
        return

    for dir in range(2):
        nr = r + dr[dir]
        nc = c + dc[dir]
        if nr >= H or nc >= W: continue
        dfs(nr, nc, cnt, flg)
    return

dfs(0,0,0,1)
print(ans)


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
S = [input() for _ in range(H)]
# print(S)
INF = 1001001001

dp = [[INF]*W for _ in range(H)]
if S[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0

for r in range(H):
    for c in range(W):
        if r:
            if S[r][c] == '#' and S[r-1][c] == '.':
                dp[r][c] = min(dp[r][c], dp[r-1][c]+1)
            else:
                dp[r][c] = min(dp[r][c], dp[r-1][c])
        if c:
            if S[r][c] == '#' and S[r][c-1] == '.':
                dp[r][c] = min(dp[r][c], dp[r][c-1]+1)
            else:
                dp[r][c] = min(dp[r][c], dp[r][c-1])

print(dp[H-1][W-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
S = [input() for _ in range(H)]
# print(S)
dr = [ 1, 0]
dc = [ 0, 1]
ans = 1001001001

def dfs(r,c,cnt,flg):
    """
    r, c
    cnt: 連続黒の回数
    flg: 1: 現在白（黒に来たらcnt+1）, 0: 現在黒
    """
    global ans
    if S[r][c] == '#':
        if flg:
            cnt += 1
            black_flg = 0
    else:
        flg = 1

    if r==H-1 and c ==W-1:
        ans = min(ans, cnt)
        return

    for dir in range(2):
        nr = r + dr[dir]
        nc = c + dc[dir]
        if nr >= H or nc >= W: continue
        dfs(nr, nc, cnt, flg)
    return

dfs(0,0,0,1)
print(ans)


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
S = [input() for _ in range(H)]
# print(S)
INF = 1001001001

dp = [[INF]*W for _ in range(H)]
if S[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0

for r in range(H):
    for c in range(W):
        if r:
            if S[r][c] == '#' and S[r-1][c] == '.':
                dp[r][c] = min(dp[r][c], dp[r-1][c]+1)
            else:
                dp[r][c] = min(dp[r][c], dp[r-1][c])
        if c:
            if S[r][c] == '#' and S[r][c-1] == '.':
                dp[r][c] = min(dp[r][c], dp[r][c-1]+1)
            else:
                dp[r][c] = min(dp[r][c], dp[r][c-1])

print(dp[H-1][W-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline
MOD = 10**9+7

MAXN = 2*10**5+5
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

n, k = map(int, (input().split()))
ans = 0
for m in range(min(n-1,k)+1):
    ans += nCr(n,m) * nCr(n-1, n-m-1) % MOD
    ans %= MOD
print(ans)


Fixed submission:
import sys
input = sys.stdin.buffer.readline
MOD = 10**9+7

MAXN = 2*10**5+5
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

n, k = map(int, (input().split()))
ans = 0
for m in range(min(n-1,k)+1):
    ans += nCr(n,m) * nCr(n-1, n-m-1) % MOD
    ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline

k, q = map(int, (input().split()))
d = list(map(int, (input().split())))

for qi in range(q):
    n, x, m = map(int, input().split())
    last = x
    eq = 0
    for i in range(k):
        num = (n-1-i+k-1)//k
        last += (d[i]%m) * num
        if d[i]%m == 0: eq += num
    ans = (n-1) - (last//m - x//m) - eq
    print(ans)

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

k, q = map(int, (input().split()))
d = list(map(int, (input().split())))

for qi in range(q):
    n, x, m = map(int, input().split())
    last = x
    eq = 0
    for i in range(k):
        num = ((n-1-i)+(k-1))//k
        last += (d[i]%m) * num
        if d[i]%m == 0: eq += num
    ans = (n-1) - (last//m - x//m) - eq
    print(ans)

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

k, q = map(int, (input().split()))
d = list(map(int, (input().split())))
sumd = sum(d)

for i in range(q):
    n, x, m = map(int, input().split())
    lcm = sumd * m // fractions.gcd(sumd, m)
    ans = 0
    a = [x]
    for i in range(n-1):
        j = i%k
        a.append(a[-1] + d[j])
        if (a[-2] % m) < (a[-1] % m):
            ans += 1
    print(ans)


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

k, q = map(int, (input().split()))
d = list(map(int, (input().split())))

for qi in range(q):
    n, x, m = map(int, input().split())
    last = x
    eq = 0
    for i in range(k):
        num = ((n-1-i)+(k-1))//k
        last += (d[i]%m) * num
        if d[i]%m == 0: eq += num
    ans = (n-1) - (last//m - x//m) - eq
    print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
ans = 0
for s in S:
    i = int(s)
    ans += min(i, 10-i)

s0, s1 = int(S[0]), int(S[1])
if s1 >= 6:
    ans += 1
elif s1 <=4 and s0 >= 5:
    ans += 1
print(ans)


Fixed submission:
S = input()
dp = [0, 1]
for s in S:
    i = int(s)
    a = min(dp[0] + i,   dp[1] + 10 - i)
    b = min(dp[0] + i+1, dp[1] + 10 - (i+1))
    dp = [a, b]
    # print(dp)
print(dp[0])

Buggy python submission (verdict: Runtime Error):
import os
import sys
input = sys.stdin.buffer.readline
S = input().rstrip().decode()
ans = 0
for s in S:
    i = int(s)
    ans += min(i, 10-i)

s0, s1 = int(S[0]), int(S[1])
if s1 >= 6:
    ans += 1
elif s1 <=4 and s0 >= 5:
    ans += 1
print(ans)


Fixed submission:
S = input()
dp = [0, 1]
for s in S:
    i = int(s)
    a = min(dp[0] + i,   dp[1] + 10 - i)
    b = min(dp[0] + i+1, dp[1] + 10 - (i+1))
    dp = [a, b]
    # print(dp)
print(dp[0])

Buggy python submission (verdict: Runtime Error):
import os
import sys
input = sys.stdin.buffer.readline
S = input().rstrip().decode()
ans = 0
for s in S:
    i = int(s)
    ans += min(i, 10-i)
if S[0] == '9' or int(S[1]) >= 6:
    ans += 1
print(ans)


Fixed submission:
S = input()
dp = [0, 1]
for s in S:
    i = int(s)
    a = min(dp[0] + i,   dp[1] + 10 - i)
    b = min(dp[0] + i+1, dp[1] + 10 - (i+1))
    dp = [a, b]
    # print(dp)
print(dp[0])

Buggy python submission (verdict: Runtime Error):
S = input()
ans = 0
for s in S:
    i = int(s)
    ans += min(i, 10-i)
if S[0] == '9' or int(S[1]) >= 6:
    ans += 1
print(ans)


Fixed submission:
S = input()
dp = [0, 1]
for s in S:
    i = int(s)
    a = min(dp[0] + i,   dp[1] + 10 - i)
    b = min(dp[0] + i+1, dp[1] + 10 - (i+1))
    dp = [a, b]
    # print(dp)
print(dp[0])
Buggy python submission (verdict: Time Limit Exceeded):
INF = 1001001001
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp = [INF] * (20000)
dp[0] = 0
for a,b in ab:
    for j in range(H):
        if dp[j+a] > dp[j] + b:
            dp[j+a] = dp[j] + b
print(min(dp[H:]))

Fixed submission:
INF = 1001001001
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp = [INF] * (20000)
dp[0] = 0
for a,b in ab:
    for j in range(H):
        if dp[j+a] > dp[j] + b:
            dp[j+a] = dp[j] + b
print(min(dp[H:]))

Buggy python submission (verdict: Time Limit Exceeded):
INF = 1001001001
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp = [INF] * (H+1)
dp[0] = 0
for i in range(N):
    for j in range(H+1):
        if j>ab[i][0]:
            dp[j] = min(dp[j], dp[j-ab[i][0]] + ab[i][1])
        else:
            dp[j] = min(dp[j], ab[i][1])
print(dp[H])


Fixed submission:
INF = 1001001001
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp = [INF] * (20000)
dp[0] = 0
for a,b in ab:
    for j in range(H):
        if dp[j+a] > dp[j] + b:
            dp[j+a] = dp[j] + b
print(min(dp[H:]))
Buggy python submission (verdict: Runtime Error):
MOD = 10**9+7
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
# print(A)

factorial = [0] * (N+2)

def fact(n, MOD=MOD):
    global factorial
    if n == 0:
        factorial[n] = 1
        return 1
    res = n * fact(n-1)
    res %= MOD
    factorial[n] = res
    return res

fact(N+1)
# print(fact(N, MOD))
# print(factorial)

def nCr(n, r, mod=10**9+7):
    res = factorial[n]
    res //= factorial[r]
    res //= factorial[n-r]
    res %= MOD
    return res

# # フェルマーの小定理
# def nCr(n, r, mod=10**9+7):
#     r = min(r, n-r)
#     numer = denom = 1
#     for i in range(1, r+1):
#         numer = numer * (n+1-i) % mod
#         denom = denom * i % mod
#     return numer * pow(denom, mod-2, mod) % mod

ans = 0
for i in range(K+1):
    c = nCr(i+K-1, i)
    ans += c * A[N-K-1+i]
    ans -= c * A[K-i]
    ans %= MOD
ans %= MOD
print(ans)


Fixed submission:
mod = 10**9+7
f = [1]
for i in range(10**5+7):
    f.append(f[-1]*(i+1)%mod)

def comb(n, r,mod=mod):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)

ans = 0
for i in range(n-k+1):
    ans += (a[i] - a[-1-i]) * comb(n-1-i, k-1)
    ans %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
N, s, t = map(int, input().split())
s -= 1
t -= 1
# to = [[] for _ in range(N)]
to = [[] for _ in range(100005)]
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

def dfs(dist, v, d=0, p=-1):
    dist[v] = d
    for u in to[v]:
        if u == p:
            continue
        dfs(dist, u, d+1, v)

def calcDist(s):
    dist = [0] * N
    dfs(dist, s)
    return dist

distS = calcDist(s)
distT = calcDist(t)

mx = 0
for i in range(N):
    if distS[i] < distT[i]:
        mx = max(mx, distT[i])
ans = mx - 1
print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(1000000)

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

def dfs(dist, v, d=0, p=-1):
    dist[v] = d
    for u in to[v]:
        if u == p:
            continue
        dfs(dist, u, d+1, v)

def calcDist(s):
    dist = [0] * N
    dfs(dist, s)
    return dist

distS = calcDist(s)
distT = calcDist(t)

mx = 0
for i in range(N):
    if distS[i] < distT[i]:
        mx = max(mx, distT[i])
ans = mx - 1
print(ans)

Buggy python submission (verdict: Runtime Error):
N, s, t = map(int, input().split())
s -= 1
t -= 1
to = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

def dfs(dist, v, d=0, p=-1):
    dist[v] = d
    for u in to[v]:
        if u == p:
            continue
        dfs(dist, u, d+1, v)

def calcDist(s):
    dist = [0] * N
    dfs(dist, s)
    return dist

distS = calcDist(s)
distT = calcDist(t)

mx = 0
for i in range(N):
    if distS[i] < distT[i]:
        mx = max(mx, distT[i])
ans = mx - 1
print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(1000000)

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

def dfs(dist, v, d=0, p=-1):
    dist[v] = d
    for u in to[v]:
        if u == p:
            continue
        dfs(dist, u, d+1, v)

def calcDist(s):
    dist = [0] * N
    dfs(dist, s)
    return dist

distS = calcDist(s)
distT = calcDist(t)

mx = 0
for i in range(N):
    if distS[i] < distT[i]:
        mx = max(mx, distT[i])
ans = mx - 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
# input = sys.stdin.buffer.readline
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

MOD = 10**9+7

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

ans = 0
for i in range(60):
    zero, one = 0, 0
    for j in range(N):
        if A[j]>>i&1:
            one += 1
        else:
            zero += 1
    ans += (one * zero)<<i
    ans %= MOD
print(ans)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7

ans = 0
for i in range(60):
    ones = 0
    for j in range(N):
        if ((A[j] >> i) & 1):
            ones += 1
    ans += 2**i * ones * (N - ones) % MOD
    ans %= MOD

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7

ans = 0
for i in range(60):
    ones = 0
    for j in range(N):
        if ((A[j] >> i) & 1):
            ones += 1
    ans += 2**i * ones * (N - ones) % MOD
    ans %= MOD

print(ans)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7

ans = 0
for i in range(60):
    ones = 0
    for j in range(N):
        if ((A[j] >> i) & 1):
            ones += 1
    ans += 2**i * ones * (N - ones) % MOD
    ans %= MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import fractions
def main():
    T1, T2 = map(int, input().split())
    f = fractions.gcd(T1, T2)
    T1 //= f
    T2 //= f
    A1, A2 = map(int, input().split())
    B1, B2 = map(int, input().split())
    f = fractions.gcd(fractions.gcd(A1, A2), fractions.gcd(B1, B2))
    A1 //= f
    A2 //= f
    B1 //= f
    B2 //= f

    a_half = T1*A1
    a_full = a_half + T2*A2
    b_half = T1*B1
    b_full = b_half + T2*B2

    if a_full == b_full:
        print("infinity")
        return
    elif a_full > b_full:
        flg = 1
    else:
        flg = -1

    if flg == 1 and a_half <= b_half:
        ans = 1
    elif flg == -1 and a_half >= b_half:
        ans = 1
    else:
        ans = 0

    a = a_full
    b = b_full
    while True:
        if flg == 1 and a + a_half < b + b_half:
            ans += 2
        elif flg == -1 and a + a_half > b + b_half:
            ans += 2
        elif a + a_half == b + b_half:
            ans += 1
        else:
            break
        a += a_full
        b += b_full

    print(ans)

main()


Fixed submission:
import fractions
def main():
    T1, T2 = map(int, input().split())
    f = fractions.gcd(T1, T2)
    T1 //= f
    T2 //= f
    A1, A2 = map(int, input().split())
    B1, B2 = map(int, input().split())
    f = fractions.gcd(fractions.gcd(A1, A2), fractions.gcd(B1, B2))
    A1 //= f
    A2 //= f
    B1 //= f
    B2 //= f

    dif_half = T1*A1 - T1*B1
    dif_full = T1*A1 + T2*A2 - T1*B1 - T2*B2

    if dif_full == 0 or A1 == B1:
        print("infinity")
        return
    elif dif_full * dif_half > 0:   # 増減が入れ替わらない場合は会うことはない
        print(0)
        return
    elif dif_full > 0:
        flg = 1
    else:
        flg = -1

    if flg == 1 and dif_half <= 0:
        ans = 1
    elif flg == -1 and dif_half >= 0:
        ans = 1
    else:
        ans = 0

    ans += (- dif_half // dif_full) * 2 - (- dif_half % dif_full == 0)

    print(ans)

main()
Buggy python submission (verdict: Runtime Error):
N = int(input())
g = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append((b, i))
    g[b].append((a, i))

ans = [0] * (N-1)

def dfs(v, c=-1, p=-1):
    global g, ans
    k = 1
    for u, ei in g[v]:
        if u == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u, ans[ei], v)

dfs(0)
mx = 0
for i in range(N):
    mx = max(mx, len(g[i]))
print(mx)
for i in range(N-1):
    print(ans[i])


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

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

ans = [0] * (N-1)

def dfs(v, c=-1, p=-1):
    global g, ans
    k = 1
    for u, ei in g[v]:
        if u == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u, ans[ei], v)

dfs(0)
mx = 0
for i in range(N):
    mx = max(mx, len(g[i]))
print(mx)
for i in range(N-1):
    print(ans[i])

Buggy python submission (verdict: Runtime Error):
N = int(input())
g = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append((b, i))
    g[b].append((a, i))
# print(g)

ans = [0] * (N-1)

def dfs(v, c=-1, p=-1):
    global g, ans
    k = 1
    for i in range(len(g[v])):
        u = g[v][i][0]
        ei = g[v][i][1]
        if u == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u, ans[ei], v)

dfs(0)
mx = 0
for i in range(N):
    mx = max(mx, len(g[i]))
print(mx)
for i in range(N-1):
    print(ans[i])


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

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

ans = [0] * (N-1)

def dfs(v, c=-1, p=-1):
    global g, ans
    k = 1
    for u, ei in g[v]:
        if u == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u, ans[ei], v)

dfs(0)
mx = 0
for i in range(N):
    mx = max(mx, len(g[i]))
print(mx)
for i in range(N-1):
    print(ans[i])
Buggy python submission (verdict: Runtime Error):
M = int(input())
sumd, sumc = 0, 0
for i in range(M):
    d, c = map(int, input().split())
    sumd += d * c
    sumc += c

for i in range(1, len(str(sumd))):
    tmp = sum // (10 ** i)
    sumd += tmp

ans = sumd // 10 + sumc - 1
print(ans)


Fixed submission:
M = int(input())
sumd, sumc = 0, 0
for i in range(M):
    d, c = map(int, input().split())
    sumd += d * c
    sumc += c

tmp = sumd // 10
while tmp > 0:
    pre = sumd
    sumd += tmp
    tmp = sumd // 10 - pre // 10

ans = sumd // 10 + sumc - 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
INF = 10e15
N, M = map(int, input().split())
LRC = [tuple(map(int, input().split())) for _ in range(M)]
LRC.sort()
# print(LRC)

dp = [INF] * N
dp[0] = 0

for i in range(M):
    l, r, c = LRC[i]
    l -= 1
    r -= 1
    # print(l, r, c)
    if dp[l] == INF:
        continue
    for i in range(l+1, r+1):
        dp[i] = min(dp[i], dp[l] + c)

# print(dp)
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])


Fixed submission:
INF = 10e15
N, M = map(int, input().split())
LRC = [tuple(map(int, input().split())) for _ in range(M)]
LRC.sort()
# print(LRC)

dp = [INF] * N
dp[0] = 0

for l, r, c in LRC:
    l -= 1
    r -= 1
    # print(l, r, c)
    if dp[l] == INF:
        continue
    for i in range(r, l, -1):
        if dp[i] > dp[l] + c:
            dp[i] = dp[l] + c
        else:
            break

# print(dp)
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
INF = 10e15
N, M = map(int, input().split())
LRC = [tuple(map(int, input().split())) for _ in range(M)]
LRC.sort()
# print(LRC)

dp = [INF] * N
dp[0] = 0

for i in range(M):
    l, r, c = LRC[i]
    l -= 1
    r -= 1
    # print(l, r, c)
    if dp[l] == INF:
        continue
    for i in range(l+1, r+1):
        dp[i] = min(dp[i], dp[l] + c)

# print(dp)
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])


Fixed submission:
INF = 10e15
N, M = map(int, input().split())
LRC = [tuple(map(int, input().split())) for _ in range(M)]
LRC.sort()
# print(LRC)

dp = [INF] * N
dp[0] = 0

for l, r, c in LRC:
    l -= 1
    r -= 1
    # print(l, r, c)
    if dp[l] == INF:
        continue
    for i in range(r, l, -1):
        if dp[i] > dp[l] + c:
            dp[i] = dp[l] + c
        else:
            break

# print(dp)
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for a in range(N-2):
    for b in range(a+1, N-1):
        minc = L[a] + L[b]
        indc = bisect.bisect_left(L[b+1:], minc)
        ans += max(indc, 0)

print(ans)


Fixed submission:
import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        ans += bisect.bisect_left(L, a+b) - j - 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
INF = 1001001001

N, M, L = map(int, input().split())

fuel = [[INF] * N for _ in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    fuel[A][B] = C
    fuel[B][A] = C
for i in range(N):
    fuel[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            fuel[i][j] = min(fuel[i][j], fuel[i][k] + fuel[k][j])

dist = [[INF] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            dist[i][j] = 0
        elif fuel[i][j] <= L:
            dist[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    if dist[s][t] == INF:
        print(-1)
    else:
        print(dist[s][t] - 1)


Fixed submission:
INF = 1001001001

N, M, L = map(int, input().split())

fuel = [[INF] * N for _ in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    fuel[A][B] = C
    fuel[B][A] = C
for i in range(N):
    fuel[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            fuel[i][j] = min(fuel[i][j], fuel[i][k] + fuel[k][j])

dist = [[INF] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            dist[i][j] = 0
        elif fuel[i][j] <= L:
            dist[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    if dist[s][t] == INF:
        print(-1)
    else:
        print(dist[s][t] - 1)
Buggy python submission (verdict: Time Limit Exceeded):
INF = 1001001001

N, M = map(int, input().split())
key = []
for i in range(M):
    a, b = map(int, input().split())
    s = 0
    c = list(map(int, input().split()))
    for j in range(b):
        c[j] -= 1
        s |= 1<<c[j]
    key.append([s, a])
dp = [INF] * (1<<N)
dp[0] = 0
for s in range(1<<N):
    for i in range(M):
        t = s | key[i][0]
        cost = dp[s] + key[i][1]
        dp[t] = min(dp[t], cost)
ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)

Fixed submission:
INF = 1001001001

N, M = map(int, input().split())
key = []
for i in range(M):
    a, b = map(int, input().split())
    s = 0
    c = list(map(int, input().split()))
    for j in range(b):
        c[j] -= 1
        s |= 1<<c[j]
    key.append([s, a])
dp = [INF] * (1<<N)
dp[0] = 0
for s in range(1<<N):
    for i in range(M):
        t = s | key[i][0]
        cost = dp[s] + key[i][1]
        dp[t] = min(dp[t], cost)
ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)