Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7

N, P = MI()
S = input()

if P == 2:
    ans = 0
    for i, c in enumerate(S):
        if int(c) % 2 == 0:
            ans += i + 1
    print(ans)
elif P == 5:
    ans = 0
    for i, c in enumerate(S):
        if c in ['5', '0']:
            ans += i + 1
    print(ans)
else:
    d = defaultdict(int)
    s = ''
    tenmod = 1
    lastmod = 0
    for i, c in enumerate(reversed(S)):
        s += c
        if i > 0:
            tenmod = tenmod * 10 % P
        lastmod = (int(c) * tenmod % P + lastmod) % P
        d[lastmod] += 1
    ans = 0
    for m, cnt in d.items():
        if m == 0:
            ans += cnt
        ans += cnt * (cnt - 1) // 2
    print(ans)


Fixed submission:
import sys
from collections import defaultdict

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7

N, P = MI()
S = input()

if P == 2:
    ans = 0
    for i, c in enumerate(S):
        if int(c) % 2 == 0:
            ans += i + 1
    print(ans)
elif P == 5:
    ans = 0
    for i, c in enumerate(S):
        if c in ['5', '0']:
            ans += i + 1
    print(ans)
else:
    d = defaultdict(int)
    tenmod = 1
    lastmod = 0
    for i, c in enumerate(reversed(S)):
        if i > 0:
            tenmod = tenmod * 10 % P
        lastmod = (int(c) * tenmod % P + lastmod) % P
        d[lastmod] += 1
    ans = 0
    for m, cnt in d.items():
        if m == 0:
            ans += cnt
        ans += cnt * (cnt - 1) // 2
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))
MOD=10 ** 9 + 7

def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


n, k = MI()

if k >= n:
    print(combination(2 * n - 1, n, MOD))
    exit(0)

ans = 1
for l in range(1, k + 1):
    ans += combination(n, l) * combination(n - 1, l)
    ans %= MOD
print(ans % MOD)


Fixed submission:
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))
MOD=10 ** 9 + 7

def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


class BinomialCoefficient(object):

    def __init__(self, N=510000, MOD=10**9+7):
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]
        self.MOD = MOD
        for i in range(2, N + 1):
            self.fac.append((self.fac[-1] * i) % MOD)
            self.inv.append((-self.inv[MOD % i] * (MOD // i)) % MOD)
            self.finv.append((self.finv[-1] * self.inv[-1]) % MOD)

    def comb(self, n, r):
        if r < 0 or n < r or r < 0:
            return 0
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.MOD



n, k = MI()

if k >= n:
    print(combination(2 * n - 1, n, MOD))
    exit(0)

coef = BinomialCoefficient(n + 1, MOD)
ans = 1
for l in range(1, k + 1):
    ans += coef.comb(n, l) * coef.comb(n - 1, l)
    ans %= MOD
print(ans % MOD)
Buggy python submission (verdict: Runtime Error):
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))


S, T = input().split()
A, B = MI()
U = input()
if U == S:
    S -= 1
elif U == T:
    B -= 1
print(A, B)

Fixed submission:
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))


S, T = input().split()
A, B = MI()
U = input()
if U == S:
    A -= 1
elif U == T:
    B -= 1
print(A, B)
Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())

# dp[i][j] = 魔法iまでからダメージの総和がj以上になるように選んだ時の魔力の最小値
# dp[i][j] = min(dp[i][j - a] + b, dp[i - 1][j])

dp = [[float('inf') for _ in range(H + 1)] for _ in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 0
for i in range(1, N + 1):
    a, b = map(int, input().split())
    for j in range(H + 1):
        dp[i][j] = min(dp[i][max(0, j - a)] + b, dp[i - 1][j])
print(dp[N][H])

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

# dp[i][j] = 魔法iまでからダメージの総和がj以上になるように選んだ時の魔力の最小値
# dp[i][j] = min(dp[i][j - a] + b, dp[i - 1][j])

dp = [[float('inf')] * (H + 1)] * (N + 1)
for i in range(N + 1):
    dp[i][0] = 0
for i in range(1, N + 1):
    a, b = map(int, input().split())
    for j in range(H + 1):
        dp[i][j] = min(dp[i][max(0, j - a)] + b, dp[i - 1][j])
print(dp[N][H])

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
a = [None] * (N + 1)
b = [None] * (N + 1)
for i in range(1, N + 1):
    a[i], b[i] = map(int, input().split())

# dp[i][j] = 魔法iまでからダメージの総和がj以上になるように選んだ時の魔力の最小値
# dp[i][j] = min(dp[i][j - a] + b, dp[i - 1][j])

dp = [[float('inf') for _ in range(H + 1)] for _ in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 0
for i in range(1, N + 1):
    for j in range(H + 1):
        dp[i][j] = min(dp[i][max(0, j - a[i])] + b[i], dp[i - 1][j])
print(dp[N][H])


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

# dp[i][j] = 魔法iまでからダメージの総和がj以上になるように選んだ時の魔力の最小値
# dp[i][j] = min(dp[i][j - a] + b, dp[i - 1][j])

dp = [[float('inf')] * (H + 1)] * (N + 1)
for i in range(N + 1):
    dp[i][0] = 0
for i in range(1, N + 1):
    a, b = map(int, input().split())
    for j in range(H + 1):
        dp[i][j] = min(dp[i][max(0, j - a)] + b, dp[i - 1][j])
print(dp[N][H])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


N, D, A = MI()
monsters = list()
for i in range(N):
    x, h = MI()
    monsters.append((x, (h + A - 1) // A))
monsters.sort()

ans = 0
for i, (x, h) in enumerate(monsters):
    if h > 0:
        ans += h
        j = i + 1
        while j < N:
            xj, hj = monsters[j]
            if xj > x + 2 * D:
                break
            monsters[j] = (xj, max(0, hj - h))
            j += 1
print(ans)

Fixed submission:
import sys
from bisect import bisect_right

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


N, D, A = MI()
monsters = list()
for i in range(N):
    x, h = MI()
    monsters.append((x, (h + A - 1) // A))
monsters.sort()

X = [x for x, h in monsters]
ub = [0] * N
for i, x in enumerate(X):
    ub[i] = bisect_right(X, x + 2 * D)

dmg = [0] * N
accum = 0
ans = 0
for i, (x, h) in enumerate(monsters):
    h = h - max(0, accum + dmg[i])
    if h > 0:
        ans += h
        dmg[i] += h
        if ub[i] < N:
            dmg[ub[i]] -= h
    accum += dmg[i]
print(ans)
Buggy python submission (verdict: Runtime Error):
import numpy as np



N, M = map(int, input().split())
A = np.array(list(map(int, input().split())))
A = A // 2
v = np.lcm.reduce(A)

print((M // v + 1) // 2)





Fixed submission:
from fractions import gcd
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = list(map(lambda x: int(x) // 2, input().split()))

    X = A[0]
    for i in range(1, N):
        a, b = X, A[i]
        X = a * b // gcd(a, b)
        if X > M:
            print(0)
            exit(0)

    cnt = 0
    tmp = X
    while tmp % 2 == 0:
        tmp = tmp // 2
        cnt += 1
    for a in A:
        if a % (2 ** cnt) == 0 and a % (2 ** (cnt + 1)) != 0:
            continue
        else:
            print(0)
            exit(0)
    print((M // X + 1) // 2)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
from itertools import combinations

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

ans = 0
for e1, e2, e3 in combinations(L, 3):
    if e1 < e2 + e3 and e2 < e1 + e3 and e3 < e1 + e2:
        ans += 1
print(ans)


Fixed submission:
from bisect import bisect_left, bisect_right

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

L.sort()
ans = 0

for a in range(N):
    for b in range(a + 1, N):
        c = bisect_left(L, L[a] + L[b])
        ans += c - b - 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from random import randint


class RollingHash(object):
    mod = 1 << 61 - 1
    base = randint(2, mod - 2)

    def __init__(self, s):
        """
        sに関するローリングハッシュを構築する O(|s|)
        """
        self.s = s
        self.pw = pw = [1] * (len(s) + 1)

        l = len(s)
        self.h = h = [0] * (l + 1)

        v = 0
        for i in range(l):
            h[i + 1] = v = (v * self.base + ord(s[i])) % self.mod
        v = 1
        for i in range(l):
            pw[i + 1] = v = v * self.base % self.mod

    def hash(self, l, r):
        """ s[l:r] のhash (rはexclusive) O(1) """
        return (self.h[r] - self.h[l] * self.pw[r - l]) % self.mod

    def contains(self, t):
        """
        sがtを含むか O(|s|-|t|)
        tはRollingHashオブジェクト
        """
        slen, tlen = len(self.s), len(t.s)
        if slen < tlen:
            return False
        th = t.hash(0, tlen)
        for i in range(slen - tlen + 1):
            if th == self.hash(i, i + tlen):
                return True
        return False

    def count(self, t):
        """
        s中に含まれるtの数をカウントする O(|s|-|t|)
        tはRollingHashオブジェクト
        """
        slen, tlen = len(self.s), len(t.s)
        if slen < tlen:
            return 0
        cnt = 0
        th = t.hash(0, tlen)
        for i in range(slen - tlen + 1):
            if th == self.hash(i, i + tlen):
                cnt += 1
        return cnt

    def getLCP(self, a, b):
        l = min(len(self.s) + 1 - a, len(self.s) + 1 - b)
        low, high = 0, l
        while high - low > 1:
            mid = (low + high) >> 1
            if self.hash(a, a + mid) != self.hash(b, b + mid):
                high = mid
            else:
                low = mid
        return low


N = int(input())
S = input()

rh = RollingHash(S)
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        lcp = rh.getLCP(i, j)
        lcp = min(lcp, j - i)
        ans = max(ans, lcp)
print(ans)

Fixed submission:
def z_algorithm(S):
    """
    文字列の各インデックスについて「SとS[i: len(S) - 1]の最良共通接頭辞の長さ」を求め、
    それを記録した配列Aを O(|S|) で作成します。
    """
    A = [-1 for _ in range(len(S))]
    A[0] = len(S)
    i = 1
    j = 0
    while i < len(S):
        while i + j < len(S) and S[j] == S[i + j]:
            j += 1
        A[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(S) and k + A[k] < j:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A


N = int(input())
S = input()

ans = 0
for i in range(N - 1):
    s = S[i:]
    A = z_algorithm(s)
    A = [min(i, a) for i, a in enumerate(A)]  # 重複する区間の除去
    ans = max(ans, max(A[1:]))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop

N, M = map(int, input().split())
q = list()
for _ in range(N):
    A, B = map(int, input().split())
    deadline = M - A
    reward_inv = -B
    if deadline >= 0:
        heappush(q, (reward_inv, deadline))

ans = [0] * (M + 1)
while len(q) > 0:
    reward_inv, deadline = heappop(q)
    while ans[deadline] != 0 and deadline > 0:
        deadline -= 1
    if ans[deadline] < -reward_inv:
        ans[deadline] = -reward_inv

print(sum(ans))

Fixed submission:
from heapq import heappush, heappop
from collections import defaultdict
N, M = map(int, input().split())
d = defaultdict(list)  # {deadline: [rewards]}
for _ in range(N):
    A, B = map(int, input().split())
    deadline = M - A
    d[deadline].append(B)

ans = list()
for day in range(M + 1):
    rewards = d.get(day)
    if rewards is None or len(rewards) == 0:
        continue
    # rewards.sort(reverse=True)
    for reward in rewards:
        if len(ans) <= day:
            heappush(ans, reward)
        else:
            min_reward = heappop(ans)
            if reward > min_reward:
                heappush(ans, reward)
            else:
                heappush(ans, min_reward)

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

X = list()
for i in range(N):
    x_i = A[i]
    keisu = -1
    for j in range(1, N):
        x_i += keisu * A[(i + j) % N]
        keisu = keisu * -1
    X.append(str(x_i))
print(' '.join(X))

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

# x1さえ求めてしまえば連立方程式の解は連鎖的にO(N)で求まる
X = list()
x_1 = sum(A)
for i in range(N):
    if i % 2 != 0:
        x_1 -= 2 * A[i]
X.append(x_1)

for i in range(1, N):
    x_i = 2 * A[i - 1] - X[i - 1]
    X.append(x_i)
print(' '.join([str(x) for x in X]))
Buggy python submission (verdict: Runtime Error):
S = input()

if S[0] == S[1] and S[2] == S[3] and S[0] != S[3]:
    print("Yes")
elif S[0] == S[2] and S[1] == S[4] and S[0] != S[1]:
    print("Yes")
elif S[0] == S[3] and S[2] == S[1] and S[0] != S[1]:
    print("Yes")
else:
    print("No")
    

Fixed submission:
S = input()

if S[0] == S[1] and S[2] == S[3] and S[0] != S[3]:
    print("Yes")
elif S[0] == S[2] and S[1] == S[3] and S[0] != S[1]:
    print("Yes")
elif S[0] == S[3] and S[2] == S[1] and S[0] != S[1]:
    print("Yes")
else:
    print("No")

Buggy python submission (verdict: Runtime Error):
S = input()

if S[0] == S[1] and S[2] == S[3] and S[0] != S[3]:
    print("Yes")
    exit(0)
if S[0] == S[2] and S[1] == S[4] and S[0] != S[1]:
    print("Yes")
    exit(0)
if S[0] == S[3] and S[2] == S[1] and S[0] != S[1]:
    print("Yes")
    exit(0)
print("No")

Fixed submission:
S = input()

if S[0] == S[1] and S[2] == S[3] and S[0] != S[3]:
    print("Yes")
elif S[0] == S[2] and S[1] == S[3] and S[0] != S[1]:
    print("Yes")
elif S[0] == S[3] and S[2] == S[1] and S[0] != S[1]:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
N = int(input())
D = list(map(int, input().split()))
D.sort()

count = 0
cur = 0
for i in range(10**5 + 1):
    if cur == N / 2:
        count += 1
    if cur > N / 2:
        break
    if D[cur] < i and cur < N:
        cur += 1
        while D[cur - 1] == D[cur]:
            cur += 1
print(count)


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

ans = D[int(N / 2)] - D[int((N / 2) - 1)]
print(ans)

Buggy python submission (verdict: Runtime Error):
N = int(input())
D = list(map(int, input().split()))
D.sort()

count = 0
cur = 0
for i in range(10**5 + 1):
    if cur == N / 2:
        count += 1
    if cur > N / 2:
        break
    if D[cur] < i:
        cur += 1
        while D[cur - 1] == D[cur]:
            cur += 1
print(count)


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

ans = D[int(N / 2)] - D[int((N / 2) - 1)]
print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
broken = set()
for _ in range(M):
    a = int(input())
    broken.add(a)

INF = 10 ** 9 + 7

memo = [None for _ in range(N + 1)]
if 1 not in broken:
    memo[1] = 1
else:
    memo[1] = 0
if 2 not in broken:
    if 1 not in broken:
        memo[2] = 2
    else:
        memo[2] = 1
else:
    memo[2] = 0
for i in range(3, N + 1):
    if i in broken:
        memo[i] = 0
    else:
        memo[i] = (memo[i - 2] + memo[i - 1])

print(memo[N] % INF)


Fixed submission:
N, M = map(int, input().split())
broken = set()
for _ in range(M):
    a = int(input())
    broken.add(a)

INF = 10 ** 9 + 7

memo = [None for _ in range(N + 1)]
memo[0] = 1
memo[1] = 0 if 1 in broken else 1
for i in range(2, N + 1):
    if i in broken:
        memo[i] = 0
    else:
        memo[i] = (memo[i - 2] + memo[i - 1]) % INF

print(memo[N])

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
broken = set()
for _ in range(M):
    a = int(input())
    broken.add(a)

INF = 10 ** 9 + 7

memo = [None for _ in range(N + 1)]
if 1 not in broken:
    memo[1] = 1
else:
    memo[1] = 0
if 2 not in broken:
    if 1 not in broken:
        memo[2] = 2
    else:
        memo[2] = 1
else:
    memo[2] = 0
for i in range(3, N + 1):
    if i in broken:
        memo[i] = 0
    else:
        memo[i] = (memo[i - 2] + memo[i - 1]) % INF

print(memo[N])


Fixed submission:
N, M = map(int, input().split())
broken = set()
for _ in range(M):
    a = int(input())
    broken.add(a)

INF = 10 ** 9 + 7

memo = [None for _ in range(N + 1)]
memo[0] = 1
memo[1] = 0 if 1 in broken else 1
for i in range(2, N + 1):
    if i in broken:
        memo[i] = 0
    else:
        memo[i] = (memo[i - 2] + memo[i - 1]) % INF

print(memo[N])

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
broken = [False for _ in range(10 **5)]
for _ in range(M):
    a = int(input())
    broken[a] = True

INF = 1000000007

memo = [None for _ in range(N + 1)]
if not broken[1]:
    memo[1] = 1
else:
    memo[1] = 0
if not broken[2]:
    memo[2] = 2
else:
    memo[2] = 0
for i in range(3, N + 1):
    if broken[i]:
        memo[i] = 0
        continue
    memo[i] = (memo[i - 2] + memo[i - 1]) % INF

print(memo[N])


Fixed submission:
N, M = map(int, input().split())
broken = set()
for _ in range(M):
    a = int(input())
    broken.add(a)

INF = 10 ** 9 + 7

memo = [None for _ in range(N + 1)]
memo[0] = 1
memo[1] = 0 if 1 in broken else 1
for i in range(2, N + 1):
    if i in broken:
        memo[i] = 0
    else:
        memo[i] = (memo[i - 2] + memo[i - 1]) % INF

print(memo[N])
Buggy python submission (verdict: Runtime Error):
def solve(N, b):
    for i in range(N):
        if b[i] > i + 1:
            return -1
    ans = [None for _ in range(N)]
    for i in reversed(range(N)):
        min_j = b[i]
        max_j = N + b[i] - i - 1
        for j in reversed(range(min_j - 1, max_j)):
            if not ans[j]:
                ans[j] = b[i]
                break
    return ans


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

for i in solve(N, b):
    print(i)

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

ans = list()
for k in reversed(range(N)):
    hit = False
    for l in reversed(range(1, k + 2)):
        if B[l - 1] == l:
            B = B[:l - 1] + B[l:]
            hit = True
            ans.append(l)
            break
    if not hit:
        print(-1)
        exit(0)

for e in reversed(ans):
    print(e)
Buggy python submission (verdict: Time Limit Exceeded):

A, B = map(int, input().split())
x = A
for i in range(A + 1, B + 1):
    x = x ^ i

print(x)

Fixed submission:
from operator import xor

A, B = map(int, input().split())


def f(n):
    if n % 2 == 0:
        if n % 4 == 0:
            return n
        else:
            return xor(n, 1)
    else:
        return xor(n, f(n - 1))


print(xor(f(A - 1), f(B)))

# 0,   1,   2,   3,   4,   5,   6,   7
# 000, 001, 010, 011, 100, 101, 110, 111
# 000, 001, 011, 000, 100, 001, 000, 111
# f(A, B) = f(0, A - 1) ^ f(0, B)
# f(0, X) = X ^ (X - 1)

Buggy python submission (verdict: Time Limit Exceeded):
def xor(a, b):
    a_bin = bin(a)[2:]
    b_bin = bin(b)[2:]
    a_len = len(a_bin)
    b_len = len(b_bin)
    result = []
    for i in range(1, max(a_len, b_len) + 1):
        if a_len < i:
            result.append(b_bin[b_len - i])
        elif b_len < i is None:
            result.append(a_bin[a_len - i])
        else:
            result.append('0' if a_bin[a_len - i] == b_bin[b_len - i] else '1')
    res_str = ''
    result.reverse()
    for s in result:
        res_str += s
    return int(res_str, 2)


A, B = map(int, input().split())
x = A
for i in range(A + 1, B + 1):
    x = xor(x, i)

print(x)

Fixed submission:
from operator import xor

A, B = map(int, input().split())


def f(n):
    if n % 2 == 0:
        if n % 4 == 0:
            return n
        else:
            return xor(n, 1)
    else:
        return xor(n, f(n - 1))


print(xor(f(A - 1), f(B)))

# 0,   1,   2,   3,   4,   5,   6,   7
# 000, 001, 010, 011, 100, 101, 110, 111
# 000, 001, 011, 000, 100, 001, 000, 111
# f(A, B) = f(0, A - 1) ^ f(0, B)
# f(0, X) = X ^ (X - 1)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

m = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# 最大何桁作れるか

# dp[i] := ちょうど i 本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
# dp[i + 1] = max(dp[i - m[j]] + 1) for all j in A

dp = [float('-inf') for _ in range(N + 1)]
dp[0] = 0

for i in range(1, N + 1):
    for num in A:
        if i - m[num] >= 0:
            dp[i] = max(dp[i], dp[i - m[num]] + 1)

matches = N
ans = ''
for _ in range(dp[N]):
    for a in A:
        if dp[matches - m[a]] == dp[matches] - 1:
            matches -= m[a]
            ans += str(a)
            break

print(ans)


Fixed submission:
from math import isinf

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

m = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# 最大何桁作れるか

# dp[i] := ちょうど i 本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
# dp[i + 1] = max(dp[i - m[j]] + 1) for all j in A

dp = [float('-inf') for _ in range(N + 1)]
dp[0] = 0

for i in range(1, N + 1):
    for num in A:
        if i - m[num] >= 0:
            dp[i] = max(dp[i], dp[i - m[num]] + 1)

matches = N
ans = ''
for _ in range(dp[N]):
    for a in A:
        if matches - m[a] < 0:
            continue
        if dp[matches - m[a]] == dp[matches] - 1:
            matches -= m[a]
            ans += str(a)
            break

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

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, M = MI()

nl = [list() for _ in range(N + 1)]
rev = [list() for _ in range(N + 1)]
for _ in range(N - 1 + M):
    A, B = MI()
    nl[A].append(B)
    rev[B].append(A)

for i, l in enumerate(rev):
    if i > 0 and len(l) == 0:
        root = i
        break

ans = [-1] * (N + 1)
q = deque([(root, 0)])
while len(q) > 0:
    v, p = q.popleft()
    ans[v] = p
    for next_v in nl[v]:
        q.append((next_v, v))

for a in ans[1:]:
    print(a)

Fixed submission:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, M = MI()

nl = [list() for _ in range(N + 1)]
rev = [list() for _ in range(N + 1)]
deg = [0 for _ in range(N + 1)]
for _ in range(N - 1 + M):
    A, B = MI()
    nl[A].append(B)
    rev[B].append(A)
    deg[B] += 1

for i, l in enumerate(deg):
    if i > 0 and l == 0:
        root = i
        break

stack = [root]
tsorted = list()
while len(stack) > 0:
    v = stack.pop()
    tsorted.append(v)
    for next_v in nl[v]:
        deg[next_v] -= 1
        if deg[next_v] == 0:
            stack.append(next_v)

ans = [0] * (N + 1)
p = {root: 0}
for v in tsorted:
    ans[v] = p[v]
    for next_v in nl[v]:
        p[next_v] = v
for a in ans[1:]:
    print(a)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]

h.sort()

ans = float('inf')
for i in range(N - K + 1):
    s = h[i: i + K]
    ans = min(ans, max(s) - min(s))

print(ans)

Fixed submission:
N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]

h.sort()

ans = min([h[i + K - 1] - h[i] for i in range(N - K + 1)])
print(ans)