Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def mod_inv(a, m):
    return pow(a, m - 2, m)


def combination(a, b):
    if b > a - b:
        return combination(a, a - b)
    if b < 0:
        return 0
    ans_mul = 1
    ans_div = 1
    for i in range(b):
        ans_mul *= a - i
        ans_div *= i + 1
        ans_mul %= MOD
        ans_div %= MOD
    ans = ans_mul * mod_inv(ans_div, MOD)
    return ans


N, K = map(int, input().split())
A = sorted(map(int, input().split()))
MOD = 10 ** 9 + 7
# max
mx = 0
mn = 0
for i in range(N):
    mx += A[i] * combination(i, K - 1)
    mn += A[i] * combination(N - i - 1, K - 1)
    mx %= MOD
    mn %= MOD
print((mx - mn) % MOD)


Fixed submission:
from collections import defaultdict


def combination(a, b):
    if b > a - b:
        return combination(a, a - b)
    return fact[a] * ifact[b] * ifact[a-b]


N, K = map(int, input().split())
A = sorted(map(int, input().split()))
MOD = 10 ** 9 + 7
# 階乗を前処理
fact = defaultdict(int)
fact[0] = 1
for i in range(1, N+1):
    fact[i] = fact[i-1] * i
    fact[i] %= MOD
# 階乗の逆元を前処理
ifact = defaultdict(int)
ifact[N] = pow(fact[N], MOD-2, MOD)
for i in reversed(range(1, N + 1)):
    ifact[i-1] = ifact[i] * i
    ifact[i-1] %= MOD

mx = 0
mn = 0
for i in range(N):
    mx += A[i] * combination(i, K - 1)
    mn += A[i] * combination(N - i - 1, K - 1)
    mx %= MOD
    mn %= MOD
print((mx - mn) % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
def mod_inv(a, m):
    return pow(a, m - 2, m)


def combination(a, b):
    if b > a - b:
        return combination(a, a - b)
    if b < 0:
        return 0
    ans_mul = 1
    ans_div = 1
    for i in range(b):
        ans_mul *= a - i
        ans_div *= i + 1
        ans_mul %= MOD
        ans_div %= MOD
    ans = ans_mul * mod_inv(ans_div, MOD)
    return ans


N, K = map(int, input().split())
A = sorted(map(int, input().split()))
MOD = 10 ** 9 + 7
# max
mx = 0
mn = 0
for i in range(N):
    mx += A[i] * combination(i, K - 1)
    mn += A[i] * combination(N - i - 1, K - 1)
    mx %= MOD
    mn %= MOD
print((mx - mn) % MOD)


Fixed submission:
from collections import defaultdict


def combination(a, b):
    if b > a - b:
        return combination(a, a - b)
    return fact[a] * ifact[b] * ifact[a-b]


N, K = map(int, input().split())
A = sorted(map(int, input().split()))
MOD = 10 ** 9 + 7
# 階乗を前処理
fact = defaultdict(int)
fact[0] = 1
for i in range(1, N+1):
    fact[i] = fact[i-1] * i
    fact[i] %= MOD
# 階乗の逆元を前処理
ifact = defaultdict(int)
ifact[N] = pow(fact[N], MOD-2, MOD)
for i in reversed(range(1, N + 1)):
    ifact[i-1] = ifact[i] * i
    ifact[i-1] %= MOD

mx = 0
mn = 0
for i in range(N):
    mx += A[i] * combination(i, K - 1)
    mn += A[i] * combination(N - i - 1, K - 1)
    mx %= MOD
    mn %= MOD
print((mx - mn) % MOD)
Buggy python submission (verdict: Runtime Error):
C010_scrambled

Fixed submission:
N = int(input())
S = input().strip()
ans = 0
for i in range(N-2):
    if S[i:i+3] == 'ABC':
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
def dfs(v, d=0, p=-1):
    global dist
    dist[v] = d
    for u in to[v]:
        if u == p:
            continue
        dfs(u, d+1, v)


def calcDist(s):
    global dist
    dist = [0 for _ in range(N)]
    dfs(s)
    return dist


N, s, t = map(int, input().split())
s -= 1
t -= 1
to = [[] for _ in range(N)]
dist = [0 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)

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(10**7)

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


def calcDist(s):
    global dist
    dist = [0 for _ in range(N)]
    dfs(s)
    return dist


N, s, t = map(int, input().split())
s -= 1
t -= 1
to = [[] for _ in range(N)]
dist = [0 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)

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):
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))

ans = 0
for i in range(60):
    x = 0
    for a in A:
        if a >> i & 1:
            x += 1
    ans += x * (N-x) * (2**i)
    ans %= MOD

print(ans)


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

ans = 0
for i in range(60):
    x = 0
    for a in A:
        if a >> i & 1:
            x += 1
    ans += x * (N-x) * (2**i)
    ans %= MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
X = int(input())

if X < 100:
    print(0)
    exit()


def dfs(zan):
    if zan <= 0:
        if zan == 0:
            print(1)
            exit()
        else:
            return

    dfs(zan - 100)
    dfs(zan - 101)
    dfs(zan - 102)
    dfs(zan - 103)
    dfs(zan - 104)
    dfs(zan - 105)


dfs(X)
print(0)

Fixed submission:
X = int(input())

if X < 100:
    print(0)
    exit()

if X % 100 == 0:
    print(1)
    exit()

cnt = X // 100
zan = X % 100

if zan > cnt * 5:
    print(0)
else:
    print(1)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = list(map(int, list(input().strip())))

cnt = 0
for d1 in range(10):
    for d2 in range(10):
        for d3 in range(10):
            find1 = False
            find2 = False
            for i, n in enumerate(L):
                if not find1 and L[i] == d1:
                    find1 = True
                    continue
                if find1 and not find2 and L[i] == d2:
                    find2 = True
                    continue
                if find1 and find2 and L[i] == d3:
                    cnt += 1
                    break
print(cnt)


Fixed submission:
N = int(input())
L = list(map(int, list(input().strip())))

cnt = 0
for d1 in range(10):
    for d2 in range(10):
        for d3 in range(10):
            find1 = False
            find2 = False
            for i, n in enumerate(L):
                if not find1 and L[i] == d1:
                    find1 = True
                    continue
                if find1 and not find2 and L[i] == d2:
                    find2 = True
                    continue
                if find1 and find2 and L[i] == d3:
                    cnt += 1
                    break
print(cnt)
Buggy python submission (verdict: Runtime Error):
from numpy import cumsum

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

all = sum(L)
cum = list(cumsum(L))

ans = float('inf')
for i in range(N-1):
    tmp = abs(cum[i]-(all-cum[i]))
    ans = min(ans, tmp)
print(ans)

Fixed submission:
from numpy import cumsum

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

all = sum(L)
cum = list(cumsum(L))

ans = float('inf')
for i in range(N-1):
    tmp = abs(cum[i]-(all-cum[i]))
    ans = min(ans, tmp)
print(ans)

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

ans = float('inf')
for i in range(N-1):
    tmp = abs(sum(L[:i+1])-sum(L[i+1:]))
    ans = min(ans, tmp)
print(ans)

Fixed submission:
from numpy import cumsum

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

all = sum(L)
cum = list(cumsum(L))

ans = float('inf')
for i in range(N-1):
    tmp = abs(cum[i]-(all-cum[i]))
    ans = min(ans, tmp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def mod_inv(a, m):
    return pow(a,m-2,m)


X, Y = map(int, input().split())
MOD = 10 ** 9 + 7

if (X + Y) % 3:
    print(0)
    exit()

n = (X + Y) // 3
nx, ny = X - n, Y - n

if nx < 0 or ny < 0:
    print(0)
    exit()

ans = 1
for i in range(1, nx + ny + 1):
    ans = ans * i % MOD
for i in range(1, nx + 1):
    ans = ans * mod_inv(i, MOD) % MOD
for i in range(1, ny + 1):
    ans = ans * mod_inv(i, MOD) % MOD

print(ans)

Fixed submission:
def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    return [w[0], w[1]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m


X, Y = map(int, input().split())
MOD = 10 ** 9 + 7

if (X + Y) % 3:
    print(0)
    exit()

n = (X + Y) // 3
nx, ny = X - n, Y - n

if nx < 0 or ny < 0:
    print(0)
    exit()

ans = 1
for i in range(1, nx + ny + 1):
    ans = ans * i % MOD
for i in range(1, nx + 1):
    ans = ans * mod_inv(i, MOD) % MOD
for i in range(1, ny + 1):
    ans = ans * mod_inv(i, MOD) % MOD

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.misc import comb

X, Y = map(int, input().split())
MOD = 10**9+7

if (X+Y) % 3:
    print(0)
    exit()

N = (X+Y) // 3

A = X - N
B = Y - N

ans = comb(A+B, A, exact=True) % MOD
print(ans)



Fixed submission:
def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    return [w[0], w[1]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m


X, Y = map(int, input().split())
MOD = 10 ** 9 + 7

if (X + Y) % 3:
    print(0)
    exit()

n = (X + Y) // 3
nx, ny = X - n, Y - n

if nx < 0 or ny < 0:
    print(0)
    exit()

ans = 1
for i in range(1, nx + ny + 1):
    ans = ans * i % MOD
for i in range(1, nx + 1):
    ans = ans * mod_inv(i, MOD) % MOD
for i in range(1, ny + 1):
    ans = ans * mod_inv(i, MOD) % MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = sorted(map(int, input().split()))
F = sorted(map(int, input().split()), reverse=True)


def ok(x):
    need = 0
    for i in range(N):
        need += max(0, A[i] - x // F[i])
    if need <= K:
        return True
    return False


left = -1
right = 10 ** 12 + 1

while right - left > 1:
    mid = (right + left) // 2
    if ok(mid):
        right = mid
    else:
        left = mid

print(right)

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


def ok(x):
    need = 0
    for i in range(N):
        need += max(0, A[i] - x // F[i])
    if need <= K:
        return True
    return False


left = -1
right = 10 ** 12 + 1

while right - left > 1:
    mid = (right + left) // 2
    if ok(mid):
        right = mid
    else:
        left = mid

print(right)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input().strip()

after = S[0]
for i in range(1, N):
    if S[i] != S[i-1]:
        after += S[i]

print(len(after))


Fixed submission:
N = int(input())
S = input().strip()

after = [S[0]]
for i in range(1, N):
    if S[i] != S[i-1]:
        after.append(S[i])

print(len(after))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = sorted(map(int, input().split()))

ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if L[k] - L[i] < L[j] < L[i] + L[k]:
                ans += 1
print(ans)


Fixed submission:
import bisect

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

ans = 0
for a in range(N):
    for b in range(a+1, N):
        ab = L[a] + L[b]
        left = b + 1
        right = bisect.bisect_left(L, ab)
        ans += right - left

print(ans)
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())
    C = list(map(int, input().split()))
    s = 0
    for c in C:
        c -= 1
        s |= 1 << c
    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
    for c in list(map(int, input().split())):
        c -= 1
        s |= 1 << c
    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)

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
    for c in list(map(int, input().split())):
        c -= 1
        s |= 1 << c
    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
    for c in list(map(int, input().split())):
        c -= 1
        s |= 1 << c
    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)
Buggy python submission (verdict: Runtime Error):
H, W, A, B = map(int, input().split())

M = [[0 for w in range(W)] for h in range(H)]

i = 0
for h in range(H):
    for a in range(A):
        w = i + a
        if w == W:
            w = 0
            i = -a
        M[h][w] = 1
    else:
        i = w + 1
        if i == W:
            i = 0

for w in range(W):
    col = 0
    for h in range(H):
        col += M[h][w]
    if col not in [B, H - B]:
        print('No')
        exit()

for h in range(H):
    print(''.join(list(map(str, M[h]))))

Fixed submission:
H, W, A, B = map(int, input().split())

M = [[0 for w in range(W)] for h in range(H)]

for h in range(B):
    for w in range(A):
        M[h][w] = 1

for h in range(B, H):
    for w in range(A, W):
        M[h][w] = 1

for h in range(H):
    print(''.join(list(map(str, M[h]))))

Buggy python submission (verdict: Runtime Error):
H, W, A, B = map(int, input().split())

M = [[0 for w in range(W)] for h in range(H)]

i = 0
for h in range(H):
    for a in range(A):
        w = i + a
        if w == W:
            w = 0
        M[h][w] = 1
    i = w + 1
    if i == W:
        i = 0

for w in range(W):
    col = 0
    for h in range(H):
        col += M[h][w]
    if col not in [B, H - B]:
        print('No')
        exit()

for h in range(H):
    print(''.join(list(map(str, M[h]))))

Fixed submission:
H, W, A, B = map(int, input().split())

M = [[0 for w in range(W)] for h in range(H)]

for h in range(B):
    for w in range(A):
        M[h][w] = 1

for h in range(B, H):
    for w in range(A, W):
        M[h][w] = 1

for h in range(H):
    print(''.join(list(map(str, M[h]))))

Buggy python submission (verdict: Runtime Error):
H, W, A, B = map(int, input().split())

M = [[0 for w in range(W)] for h in range(H)]

i = 0
for h in range(H):
    for a in range(A):
        w = i + a
        if w == W:
            w = 0
        M[h][w] = 1
        i = w
    i += 1
    if i == W:
        i = 0

for w in range(W):
    col = 0
    for h in range(H):
        col += M[h][w]
    if col not in [B, H - B]:
        print('No')
        exit()

for h in range(H):
    print(''.join(list(map(str, M[h]))))

Fixed submission:
H, W, A, B = map(int, input().split())

M = [[0 for w in range(W)] for h in range(H)]

for h in range(B):
    for w in range(A):
        M[h][w] = 1

for h in range(B, H):
    for w in range(A, W):
        M[h][w] = 1

for h in range(H):
    print(''.join(list(map(str, M[h]))))
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = sorted(map(int, input().split()), reverse=True)

for i in range(M):
    A[0] //= 2
    A.sort(reverse=True)

print(sum(A))

Fixed submission:
from math import ceil
import heapq

N, M = map(int, input().split())
heap = [-x for x in list(map(int, input().split()))]
heapq.heapify(heap)

for i in range(M):
    h = heapq.heappop(heap)
    h = ceil(h/2)
    heapq.heappush(heap, h)

ans = 0
for _ in range(N):
    h = heapq.heappop(heap)
    ans += -h

print(ans)
Buggy python submission (verdict: Runtime Error):
import re

N, K = map(int, input().split())
S = input().strip()

LL = re.finditer('L{1,}', S)
RR = re.finditer('R{1,}', S)

happy = 0
next_happy = []

for l in LL:
    happy += len(l[0]) - 1
    if l.regs[0][0] == 0 or l.regs[0][1] == N:
        next_happy.append(1)
    else:
        next_happy.append(2)

for r in RR:
    happy += len(r[0]) - 1
    if r.regs[0][0] == 0 or r.regs[0][1] == N:
        next_happy.append(1)
    else:
        next_happy.append(2)

happy += sum(sorted(next_happy, reverse=True)[:K])


print(happy)


Fixed submission:
import re

N, K = map(int, input().split())
S = input().strip()

LL = re.finditer('L+', S)
RR = re.finditer('R+', S)

happy = 0
next_happy = []

for l in LL:
    happy += len(l.group(0)) - 1
    if l.regs[0][0] == 0 or l.regs[0][1] == N:
        next_happy.append(1)
    else:
        next_happy.append(2)

for r in RR:
    happy += len(r.group(0)) - 1
    if r.regs[0][0] == 0 or r.regs[0][1] == N:
        next_happy.append(1)
    else:
        next_happy.append(2)

happy += sum(sorted(next_happy, reverse=True)[:K])

if happy >= N:
    happy = N - 1

print(happy)

Buggy python submission (verdict: Runtime Error):
import re

N, K = map(int, input().split())
S = input().strip()

LL = re.finditer(r'L{1,}', S)
RR = re.finditer(r'R{1,}', S)

happy = 0
next_happy = []

for l in LL:
    happy += len(l[0]) - 1
    if l.regs[0][0] == 0 or l.regs[0][1] == N:
        next_happy.append(1)
    else:
        next_happy.append(2)

for r in RR:
    happy += len(r[0]) - 1
    if r.regs[0][0] == 0 or r.regs[0][1] == N:
        next_happy.append(1)
    else:
        next_happy.append(2)

happy += sum(sorted(next_happy, reverse=True)[:K])


print(happy)


Fixed submission:
import re

N, K = map(int, input().split())
S = input().strip()

LL = re.finditer('L+', S)
RR = re.finditer('R+', S)

happy = 0
next_happy = []

for l in LL:
    happy += len(l.group(0)) - 1
    if l.regs[0][0] == 0 or l.regs[0][1] == N:
        next_happy.append(1)
    else:
        next_happy.append(2)

for r in RR:
    happy += len(r.group(0)) - 1
    if r.regs[0][0] == 0 or r.regs[0][1] == N:
        next_happy.append(1)
    else:
        next_happy.append(2)

happy += sum(sorted(next_happy, reverse=True)[:K])

if happy >= N:
    happy = N - 1

print(happy)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

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

jobs = []
for i in range(N):
    a, b = map(int, input().split())
    jobs.append((a, b))
jobs.sort()

hq = []
ans = 0
index = 0
for i in reversed(range(M)):
    for j in range(index, N):
        if jobs[j][0] < M - i:
            break
        if jobs[j][0] == M - i:
            heapq.heappush(hq, -jobs[j][1])
            index += 1

    if len(hq):
        ans += heapq.heappop(hq) * (-1)

print(ans)


Fixed submission:
import heapq

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

jobs = []
for i in range(N):
    a, b = map(int, input().split())
    jobs.append((a, b))
jobs.sort()

hq = []
ans = 0
index = 0
for i in reversed(range(M)):
    for j in range(index, N):
        a, b = jobs[j]
        if a > M - i:
            break
        if a == M - i:
            heapq.heappush(hq, -jobs[j][1])
            index += 1

    if len(hq):
        ans += heapq.heappop(hq) * (-1)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

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

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

hq = []
ans = 0
for i in reversed(range(M)):
    for x in jobs:
        if x[0] == M - i:
            heapq.heappush(hq, -x[1])
    if len(hq):
        ans += heapq.heappop(hq) * (-1)

print(ans)


Fixed submission:
import heapq

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

jobs = []
for i in range(N):
    a, b = map(int, input().split())
    jobs.append((a, b))
jobs.sort()

hq = []
ans = 0
index = 0
for i in reversed(range(M)):
    for j in range(index, N):
        a, b = jobs[j]
        if a > M - i:
            break
        if a == M - i:
            heapq.heappush(hq, -jobs[j][1])
            index += 1

    if len(hq):
        ans += heapq.heappop(hq) * (-1)

print(ans)

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

baito = []
dp = [0] * (10**5+1)
for i in range(N):
    a, b = map(int, input().split())
    baito.append([a, b, 0])

for i in range(M):
    rewards = sorted([x for x in baito if x[0] + i <= M and x[2] == 0], key=lambda x: (-x[1], -x[0]))
    if rewards:
        max_reward = rewards[0]
        max_reward[2] = 1
        if i == 0:
            dp[i] = max_reward[1]
        else:
            dp[i] = dp[i-1] + max_reward[1]
    else:
        if i == 0:
            dp[i] = 0
        else:
            dp[i] = dp[i-1]

print(dp[M-1])


Fixed submission:
import heapq

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

jobs = []
for i in range(N):
    a, b = map(int, input().split())
    jobs.append((a, b))
jobs.sort()

hq = []
ans = 0
index = 0
for i in reversed(range(M)):
    for j in range(index, N):
        a, b = jobs[j]
        if a > M - i:
            break
        if a == M - i:
            heapq.heappush(hq, -jobs[j][1])
            index += 1

    if len(hq):
        ans += heapq.heappop(hq) * (-1)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input().strip()
N = len(S)
MOD = 10**9+7
dp = [[0] * 13 for _ in range(N + 1)]
dp[0][0] = 1
mul = 1

for i in range(N):
    x = S[i]
    for j in range(13):
        if x == '?':
            for k in range(10):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
        else:
            n = int(x)
            dp[i + 1][(j * 10 + n) % 13] += dp[i][j]

print(dp[N][5] % MOD)


Fixed submission:
S = input().strip()
N = len(S)
MOD = 10**9+7
dp = [[0] * 13 for _ in range(N + 1)]
dp[0][0] = 1
mul = 1

for i in range(N):
    x = S[i]
    for j in range(13):
        if x == '?':
            for k in range(10):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
                dp[i + 1][(j * 10 + k) % 13] %= MOD
        else:
            n = int(x)
            dp[i + 1][(j * 10 + n) % 13] += dp[i][j]
            dp[i + 1][(j * 10 + n) % 13] %= MOD


print(dp[N][5] % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
S = input().strip()
N = len(S)
MOD = 10**9+7
dp = [[0] * 13 for _ in range(N + 1)]
dp[0][0] = 1
mul = 1

for i in range(N):
    x = S[i]
    for j in range(13):
        if x == '?':
            for k in range(10):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
                dp[i + 1][(j * 10 + k) % 13] %= MOD
        else:
            n = int(x)
            dp[i + 1][(j * 10 + n) % 13] += dp[i][j]
            dp[i + 1][(j * 10 + n) % 13] %= MOD


print(dp[N][5] % MOD)



Fixed submission:
S = input().strip()
N = len(S)
MOD = 10**9+7
dp = [[0] * 13 for _ in range(N + 1)]
dp[0][0] = 1
mul = 1

for i in range(N):
    x = S[i]
    for j in range(13):
        if x == '?':
            for k in range(10):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
                dp[i + 1][(j * 10 + k) % 13] %= MOD
        else:
            n = int(x)
            dp[i + 1][(j * 10 + n) % 13] += dp[i][j]
            dp[i + 1][(j * 10 + n) % 13] %= MOD


print(dp[N][5] % MOD)