Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)

N, M = map(int, input().split())
adjL = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    adjL[A-1].append(B-1)
    adjL[B-1].append(A-1)

if M % 2:
    print(-1)
    sys.exit()

anss = []
degs = [0] * N
useds = [False] * N

vNotLeafs = []
for v in range(N):
    if len(adjL[v]) == 1:
        v0 = adjL[v][0]
        anss.append(v0, v)
        degs[v0] += 1
        useds[v] = True
    else:
        vNotLeafs.append(v)
#print(vNotLeafs)

def dfs(vNow):
    if degs[vNow] % 2 == 0:
        useds[vNow] = True
    for v2 in adjL[vNow]:
        if useds[v2]: continue
        if not useds[vNow]:
            anss.append((vNow, v2))
            degs[vNow] += 1
            useds[vNow] = True
        else:
            anss.append((v2, vNow))
            degs[v2] += 1
        dfs(v2)

dfs(vNotLeafs[0])

print('\n'.join(map(lambda x: str(x[0]+1)+' '+str(x[1]+1), anss)))


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

N, M = map(int, input().split())
adjL = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    adjL[A-1].append(B-1)
    adjL[B-1].append(A-1)

if M % 2:
    print(-1)
    sys.exit()

def makeSpanningTree(vNow, vPar):
    useds[vNow] = True
    for v2 in adjL[vNow]:
        if v2 == vPar:
            pass
        elif useds[v2]:
            if vNow < v2:
                anss.append((vNow, v2))
                outdegs[vNow] += 1
        else:
            adjL2[vNow].append(v2)
            adjL2[v2].append(vNow)
            makeSpanningTree(v2, vNow)

anss = []
adjL2 = [[] for _ in range(N)]
outdegs = [0] * N
useds = [False] * (N)
makeSpanningTree(0, -1)

def dfs(vNow, vPar):
    for v2 in adjL2[vNow]:
        if v2 != vPar:
            dfs(v2, vNow)
    if outdegs[vNow] % 2:  # 出す
        anss.append((vNow, vPar))
        outdegs[vNow] += 1
    else:  # 入れる
        anss.append((vPar, vNow))
        outdegs[vPar] += 1

dfs(0, -1)
anss.pop()

print('\n'.join(map(lambda x: str(x[0]+1)+' '+str(x[1]+1), anss)))
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    MOD = 10**9 + 7

    N, M = map(int, input().split())
    Ss = list(map(int, input().split()))
    Ts = list(map(int, input().split()))

    dp = [[0]*(M+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 1
    for j in range(M+1):
        dp[0][j] = 1

    for i, S in enumerate(Ss, start=1):
        for j, T in enumerate(Ts, start=1):
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
            if S == T:
                dp[i][j] += dp[i-1][j-1]
            dp[i][j] %= MOD

    print(dp[N][M])


solve()


Fixed submission:
MOD = 10**9 + 7

N, M = map(int, input().split())
Ss = list(map(int, input().split()))
Ts = list(map(int, input().split()))

dp = [[1]*(M+1) for _ in range(N+1)]
for i, S in enumerate(Ss, 1):
    for j, T in enumerate(Ts, 1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
        if S != T:
            dp[i][j] -= dp[i-1][j-1]
        dp[i][j] %= MOD

print(dp[-1][-1])
Buggy python submission (verdict: Runtime Error):
from collections import Counter

N = int(input())
balls = [tuple(map(int, input().split())) for _ in range(N)]

diffs = Counter()
for i in range(N):
    x1, y1 = balls[i]
    for j in range(i+1, N):
        x2, y2 = balls[j]
        diffs.update([(x2-x1, y2-y1)])

ans = N - diffs.most_common(1)[0][1]
print(ans)


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

balls.sort()

ans = N
for i in range(N):
    for j in range(i+1, N):
        p, q = balls[j][0]-balls[i][0], balls[j][1]-balls[i][1]
        useds = [False] * N
        num = 0
        for a in range(N):
            if useds[a]: continue
            useds[a] = True
            num += 1
            x, y = balls[a]
            for b in range(a+1, N):
                if useds[b]: continue
                if balls[b] == (x+p, y+q):
                    useds[b] = True
                    x, y = balls[b]
        ans = min(ans, num)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

def solve():
    def getNums(Ss):
        lenS = len(Ss)
        nums = [0] * lenS
        Ss += '#'
        num = -1
        for i, S in enumerate(Ss):
            if S == '.':
                num += 1
            else:
                if num > 0:
                    nums[i-(num+1)] = num
                    if i < lenS:
                        nums[i] = -num
                num = -1
        return accumulate(nums)


    H, W = map(int, input().split())
    Sss = [input() for _ in range(H)]

    numHss = [list(getNums(Ss)) for Ss in Sss]
    Sss_tr = list(map(''.join, zip(*Sss))) # 転置
    numVss_tr = [getNums(Ss) for Ss in Sss_tr]
    numVss = list(map(list, zip(*numVss_tr))) # 転置

    ans = 0
    for i in range(H):
        for j in range(W):
            num = numHss[i][j] + numVss[i][j] + 1
            if num > ans:
                ans = num

    print(ans)

solve()


Fixed submission:
from itertools import accumulate

def getNums(Ss):
    lenS = len(Ss)
    nums = [0] * lenS
    Ss += '#'
    num = -1
    for i, S in enumerate(Ss):
        if S == '.':
            num += 1
        else:
            if num > 0:
                nums[i-(num+1)] = num
                if i < lenS:
                    nums[i] = -num
            num = -1
    return accumulate(nums)


H, W = map(int, input().split())
Sss = [input() for _ in range(H)]

numHss = [list(getNums(Ss)) for Ss in Sss]
Sss_tr = list(map(''.join, zip(*Sss))) # 転置
numVss_tr = [getNums(Ss) for Ss in Sss_tr]
numVss = list(map(list, zip(*numVss_tr))) # 転置

ans = 0
for i in range(H):
    for j in range(W):
        num = numHss[i][j] + numVss[i][j] + 1
        if num > ans:
            ans = num

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
As = list(map(int, input().split()))
BCs = [tuple(map(int, input().split())) for _ in range(M)]

As.sort()
BCs.sort(reverse=True, key=lambda x: x[1])

i = 0
for B, C in BCs:
    num = min(N-i, B)
    for j in range(i, i+B):
        if As[j] >= C:
            break
        As[j] = C
    else:
        i += B
        continue
    break
#print('As:', As)

print(sum(As))


Fixed submission:
N, M = map(int, input().split())
As = list(map(int, input().split()))
BCs = [tuple(map(int, input().split())) for _ in range(M)]

As.sort()
BCs.sort(key=lambda x: x[1], reverse=True)

iA = 0
for B, C in BCs:
    for j in range(B):
        if As[iA] < C:
            As[iA] = C
            iA += 1
            if iA >= N:
                break
        else:
            break
    else:
        continue
    break

print(sum(As))

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
As = list(map(int, input().split()))
BCs = [tuple(map(int, input().split())) for _ in range(M)]

As.sort()
BCs.sort(key=lambda x: x[1], reverse=True)

iA = 0
for B, C in BCs:
    for j in range(B):
        if As[iA] < C:
            As[iA] = C
            iA += 1
        else:
            break
    else:
        continue
    break

print(sum(As))


Fixed submission:
N, M = map(int, input().split())
As = list(map(int, input().split()))
BCs = [tuple(map(int, input().split())) for _ in range(M)]

As.sort()
BCs.sort(key=lambda x: x[1], reverse=True)

iA = 0
for B, C in BCs:
    for j in range(B):
        if As[iA] < C:
            As[iA] = C
            iA += 1
            if iA >= N:
                break
        else:
            break
    else:
        continue
    break

print(sum(As))
Buggy python submission (verdict: Time Limit Exceeded):
R, G, B, N = map(int, input().split())

num = 0
ans = 0
for r in range(N+1):
    numR = R*r
    if numR > N: continue
    for g in range(N+1):
        numG = numR + G*g
        if numG > N: continue
        b = (N-numG) / B
        if int(b) == b and b >= 0:
            ans += 1

print(ans)


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

num = 0
ans = 0
for r in range(N+1):
    numR = R*r
    if numR > N: continue
    for g in range(N+1):
        numG = numR + G*g
        if numG > N: continue
        b = (N-numG) / B
        if int(b) == b and b >= 0:
            ans += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())

anss = set()
for X in range(1, int(N**0.5)+2):
    if (N-X) % X == 0:
        m = (N-X) // X
        if N//m == N%m:
            anss.add(m)

for m in range(1, int(N**0.5)+2):
    if N//m == N%m:
        anss.add(m)

print(sum(anss))


Fixed submission:
N = int(input())

anss = set()
for X in range(1, int(N**0.5)+2):
    if (N-X) % X == 0:
        m = (N-X) // X
        if m <= 0: continue
        if N//m == N%m:
            anss.add(m)

for m in range(1, int(N**0.5)+2):
    if N//m == N%m:
        anss.add(m)

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

def solve():
    H, W = map(int, input().split())
    Ass = ['#'*(W+2)] + ['#'+input()+'#' for _ in range(H)] + ['#'*(W+2)]

    distss = [[-1]*(W) for _ in range(H)]
    Q = deque([])
    for i in range(1, H+1):
        for j in range(1, W+1):
            if Ass[i][j] == '#':
                Q.append((i, j))
                distss[i-1][j-1] = 0

    while Q:
        i, j = Q.popleft()
        for di, dj in [(-1,0), (1,0), (0,-1), (0,1)]:
            i2, j2 = i+di, j+dj
            if Ass[i2][j2] == '.' and distss[i2-1][j2-1] == -1:
                Q.append((i2, j2))
                distss[i2-1][j2-1] = distss[i-1][j-1] + 1

    return max(map(max, distss))

print(solve())


Fixed submission:
from collections import deque

def solve():
    H, W = map(int, input().split())
    Ass = ['#'*(W+2)] + ['#'+input()+'#' for _ in range(H)] + ['#'*(W+2)]

    distss = [[-1]*(W) for _ in range(H)]
    Q = deque([])
    for i in range(1, H+1):
        for j in range(1, W+1):
            if Ass[i][j] == '#':
                Q.append((i, j))
                distss[i-1][j-1] = 0

    while Q:
        i, j = Q.popleft()
        for di, dj in [(-1,0), (1,0), (0,-1), (0,1)]:
            i2, j2 = i+di, j+dj
            if Ass[i2][j2] == '.' and distss[i2-1][j2-1] == -1:
                Q.append((i2, j2))
                distss[i2-1][j2-1] = distss[i-1][j-1] + 1

    return max(map(max, distss))

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

def getDivisor(x):
    ans = []
    for d in range(1, int(x**0.5)+1):
        if x % d == 0:
            ans.append(d)
            if x//d != d:
                ans.append(x//d)
    return sorted(ans)

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

divisors = getDivisor(As[0]) + getDivisor(As[1])
cnt = Counter(divisors)

for i, A in enumerate(As[2:], 2):
    for d, num in list(cnt.items()):
        if A%d == 0:
            cnt[d] += 1

    for d, num in list(cnt.items()):
        if num < i:
            del cnt[d]

print(max(cnt.keys()))


Fixed submission:
from collections import Counter

def getDivisor(x):
    ans = []
    for d in range(1, int(x**0.5)+1):
        if x % d == 0:
            ans.append(d)
            if x//d != d:
                ans.append(x//d)
    return sorted(ans)

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

divisors = getDivisor(As[0]) + getDivisor(As[1])
cnt = Counter(divisors)

for i, A in enumerate(As[2:], 2):
    for d, num in list(cnt.items()):
        if A%d == 0:
            cnt[d] += 1

    for d, num in list(cnt.items()):
        if num < i:
            del cnt[d]

print(max(cnt.keys()))
Buggy python submission (verdict: Runtime Error):
from itertools import accumulate

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

consecutive01s = [[], [0]]
turn = 0
num = 0
for S in Ss+[9]:
    if S == turn:
        num += 1
    else:
        consecutive01s[turn].append(num)
        turn = 1-turn
        num = 1
if turn == 0:
    consecutive01s[0].append(0)
consecutive01s[1].append(0)

N0, N1 = len(consecutive01s[0]), len(consecutive01s[1])

acc0s = list(accumulate([0]+consecutive01s[0]))
acc1s = list(accumulate([0]+consecutive01s[1]))

len0s = [acc0s[i+K]-acc0s[i] for i in range(N0-K+1)]
len1s = [acc1s[i+K+1]-acc1s[i] for i in range(N1-K)]

ans = max([len0+len1 for len0, len1 in zip(len0s, len1s)])
print(ans)


Fixed submission:
from itertools import accumulate

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

consecutive01s = [[], [0]]
turn = 0
num = 0
for S in Ss+[9]:
    if S == turn:
        num += 1
    else:
        consecutive01s[turn].append(num)
        turn = 1-turn
        num = 1
if turn == 0:
    consecutive01s[0].append(0)
consecutive01s[1].append(0)

N0, N1 = len(consecutive01s[0]), len(consecutive01s[1])
K = min(K, N0)

acc0s = list(accumulate([0]+consecutive01s[0]))
acc1s = list(accumulate([0]+consecutive01s[1]))

len0s = [acc0s[i+K]-acc0s[i] for i in range(N0-K+1)]
len1s = [acc1s[i+K+1]-acc1s[i] for i in range(N1-K)]

ans = max([len0+len1 for len0, len1 in zip(len0s, len1s)])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product

X, Y, Z, K = map(int, input().split())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
Cs = list(map(int, input().split()))

sumABs = [A + B for A, B in product(As, Bs)]
sumABs.sort(reverse=True)

sumABCs = [sumAB + C for sumAB, C in product(sumABs[:K], Cs)]
sumABCs.sort(reverse=True)

print('\n'.join(map(str, sumABCs[:K])))


Fixed submission:
from heapq import heapify, heappush, heappop, heappushpop

X, Y, Z, K = map(int, input().split())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
Cs = list(map(int, input().split()))

sum12s = []
for A in As:
    for B in Bs:
        sum12s.append(A+B)
sum12s.sort(reverse=True)

PQ = [Cs[0]+sum12 for sum12 in sum12s[:K]]
heapify(PQ)
for C in Cs[1:]:
    for sum12 in sum12s[:K]:
        heappush(PQ, C+sum12)
    for _ in range(K, len(PQ)):
        heappop(PQ)

anss = []
for _ in range(K):
    anss.append(heappop(PQ))
print('\n'.join(map(str, anss[::-1])))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappush, heappop, heappushpop

X, Y, Z, K = map(int, input().split())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
Cs = list(map(int, input().split()))

sum12s = []
for A in As:
    for B in Bs:
        sum12s.append(A+B)
sum12s.sort(reverse=True)

PQ = [Cs[0]+sum12 for sum12 in sum12s[:K]]
heapify(PQ)
for C in Cs[1:]:
    for sum12 in sum12s[:K]:
        heappush(PQ, C+sum12)
    for _ in range(K, len(PQ)):
        heappop(PQ)

anss = []
for _ in range(K):
    anss.append(heappop(PQ))
print('\n'.join(map(str, anss[::-1])))


Fixed submission:
from heapq import heapify, heappush, heappop, heappushpop

X, Y, Z, K = map(int, input().split())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
Cs = list(map(int, input().split()))

sum12s = []
for A in As:
    for B in Bs:
        sum12s.append(A+B)
sum12s.sort(reverse=True)

PQ = [Cs[0]+sum12 for sum12 in sum12s[:K]]
heapify(PQ)
for C in Cs[1:]:
    for sum12 in sum12s[:K]:
        heappush(PQ, C+sum12)
    for _ in range(K, len(PQ)):
        heappop(PQ)

anss = []
for _ in range(K):
    anss.append(heappop(PQ))
print('\n'.join(map(str, anss[::-1])))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)

MOD = 10**9 + 7

N, X = map(int, input().split())
Ss = list(map(int, input().split()))

Ss.sort(reverse=True)

def dfs(i, xNow):
    if (i, xNow) in memo:
        return memo[(i, xNow)]
    if i == N-1:
        ans = xNow % Ss[i]
    else:
        ans = dfs(i+1, xNow % Ss[i])
        ans += dfs(i+1, xNow) * (N-i-1)
    ans %= MOD
    memo[(i, xNow)] = ans
    return ans

memo = {}
dfs(0, X)

print(memo[(0, X)])


Fixed submission:
MOD = 10**9 + 7

N, X = map(int, input().split())
Ss = list(map(int, input().split()))

Ss.sort(reverse=True)
minS = Ss[-1]

D = {X: 1}
for i, S in enumerate(Ss[:-1]):
    D2 = {}
    for x, num in D.items():
        D2[x] = (D2.get(x, 0) + num*(N-1-i)) % MOD
        D2[x%S] = (D2.get(x%S, 0) + num) % MOD
    D = D2

ans = 0
for x, num in D.items():
    ans += (x%minS) * num % MOD
    ans %= MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_right

def getINearests(ss, ts):
    iNearests = [-1] * len(ss)
    for iS, s in enumerate(ss):
        iT = bisect_right(ts, s)
        if iT == len(ts):
            iNearests[iS] = iT-1
        elif iT == 0:
            iNearests[iS] = 0
        else:
            d1 = abs(s - ts[iT-1])
            d2 = abs(s - ts[iT])
            if d1 <= d2:
                iNearests[iS] = iT-1
            else:
                iNearests[iS] = iT
    return iNearests


A, B, Q = map(int, input().split())
ss = [int(input()) for _ in range(A)]
ts = [int(input()) for _ in range(B)]
xs = [int(input()) for _ in range(Q)]

iTNearests = getINearests(ss, ts)
iSNearests = getINearests(ts, ss)

anss = [0] * Q
for iX, x in enumerate(xs):
    ans = float('inf')

    # 初手: 神社
    iS = bisect_right(ss, x)
    if iS > 0:
        cost = abs(x - ss[iS-1])
        cost += abs(ss[iS-1] - ts[iTNearests[iS-1]])
        ans = min(ans, cost)
    if iS < A:
        cost = abs(x - ss[iS])
        cost += abs(ss[iS] - ts[iTNearests[iS]])
        ans = min(ans, cost)

    # 初手: 寺
    iT = bisect_right(ts, x)
    if iT > 0:
        cost = abs(x - ts[iT-1])
        cost += abs(ts[iT-1] - ss[iSNearests[iT-1]])
        ans = min(ans, cost)
    if iT < B:
        cost = abs(x - ts[iT])
        cost += abs(ts[iT] - ss[iSNearests[iT]])
        ans = min(ans, cost)

    anss[iX] = ans

print('\n'.join(map(str, anss)))


Fixed submission:
import sys
from bisect import bisect_right

def solve():
    def getINearests(ss, ts):
        iNearests = [-1] * len(ss)
        for iS, s in enumerate(ss):
            iT = bisect_right(ts, s)
            if iT == len(ts):
                iNearests[iS] = iT-1
            elif iT == 0:
                iNearests[iS] = 0
            else:
                d1 = abs(s - ts[iT-1])
                d2 = abs(s - ts[iT])
                if d1 <= d2:
                    iNearests[iS] = iT-1
                else:
                    iNearests[iS] = iT
        return iNearests


    A, B, Q = map(int, input().split())
    ss = [int(sys.stdin.readline()) for _ in range(A)]
    ts = [int(sys.stdin.readline()) for _ in range(B)]
    xs = [int(sys.stdin.readline()) for _ in range(Q)]

    iTNearests = getINearests(ss, ts)
    iSNearests = getINearests(ts, ss)

    anss = [0] * Q
    for iX, x in enumerate(xs):
        ans = float('inf')

        # 初手: 神社
        iS = bisect_right(ss, x)
        if iS > 0:
            cost = abs(x - ss[iS-1])
            cost += abs(ss[iS-1] - ts[iTNearests[iS-1]])
            if cost < ans: ans = cost
        if iS < A:
            cost = abs(x - ss[iS])
            cost += abs(ss[iS] - ts[iTNearests[iS]])
            if cost < ans: ans = cost

        # 初手: 寺
        iT = bisect_right(ts, x)
        if iT > 0:
            cost = abs(x - ts[iT-1])
            cost += abs(ts[iT-1] - ss[iSNearests[iT-1]])
            if cost < ans: ans = cost
        if iT < B:
            cost = abs(x - ts[iT])
            cost += abs(ts[iT] - ss[iSNearests[iT]])
            if cost < ans: ans = cost

        anss[iX] = ans

    print('\n'.join(map(str, anss)))

solve()
Buggy python submission (verdict: Runtime Error):
from itertools import accumulate

# 整数Xのときの[高橋くんが上から取る連続枚数]が、k枚以下（k+1以上にはならない）かどうか判定する
def check(X, k):
    # 青木くんがLより先にRを取れれば、条件を満たす
    L, R = As[N-2*k-1], As[N-k-1]
    return abs(L-X) > abs(X-R)

N, Q = map(int, input().split())
As = list(map(int, input().split()))
Xs = [(int(input()), iX) for iX in range(Q)]

numT = (N+1) // 2  # 高橋くんが取るカードの枚数
Ascs = As[::2] if N % 2 else As[1::2]
Descs = As[::-1]
accAscs = [0] + list(accumulate(Ascs))
accDescs = [0] + list(accumulate(Descs))

# 高橋くんが上から連続k枚を取る場合のスコア
scores = [0] * (numT+1)
for k in range(1, numT+1):
    scores[k] = accDescs[k] + accAscs[numT - k]

# Xの降順で処理する
anss = [0] * Q
k = 1
for X, iX in sorted(Xs, reverse=True):
    # [k枚以下]になる最小のkを求める
    while not check(X, k):
        k += 1
    anss[iX] = scores[k]

print('\n'.join(map(str, anss)))


Fixed submission:
from itertools import accumulate
import sys

# 整数Xのときの[高橋くんが上から取る連続枚数]が、k枚以下（k+1以上にはならない）かどうか判定する
def check(X, k):
    # 青木くんがLより先にRを取れれば、条件を満たす
    L, R = As[N-2*k-1], As[N-k-1]
    return abs(L-X) > abs(X-R)

N, Q = map(int, input().split())
As = list(map(int, input().split()))
Xs = [(int(input()), iX) for iX in range(Q)]

if N == 2:
    print('\n'.join(map(str, [As[-1]]*Q)))
    sys.exit()

numT = (N+1) // 2  # 高橋くんが取るカードの枚数
Ascs = As[::2] if N % 2 else As[1::2]
Descs = As[::-1]
accAscs = [0] + list(accumulate(Ascs))
accDescs = [0] + list(accumulate(Descs))

# 高橋くんが上から連続k枚を取る場合のスコア
scores = [0] * (numT+1)
for k in range(1, numT+1):
    scores[k] = accDescs[k] + accAscs[numT - k]

# Xの降順で処理する
anss = [0] * Q
k = 1
for X, iX in sorted(Xs, reverse=True):
    # [k枚以下]になる最小のkを求める
    while not check(X, k):
        k += 1
    anss[iX] = scores[k]

print('\n'.join(map(str, anss)))
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
hs = list(map(int, input().split()))

dp = [0] * N
for i in range(1, N):
    hi = hs[i]
    dp2 = dp[max(0, i-K):i]
    costs = [abs(h - hi) for h in hs[max(0, i-K):i]]
    dp[i] = min([dpj + cost for dpj, cost in zip(dp2, costs)])

print(dp[N-1])


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

dp = [0] * N
for i in range(1, N):
    hi = hs[i]
    dp2 = dp[max(0, i-K):i]
    costs = [abs(h - hi) for h in hs[max(0, i-K):i]]
    dp[i] = min([dpj + cost for dpj, cost in zip(dp2, costs)])

print(dp[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
INF = float('inf')

N, K = map(int, input().split())
hs = list(map(int, input().split())) + [INF] * (K-1)

dp = [INF] * (N+K-1)
dp[0] = 0
for i in range(N-1):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(hs[i] - hs[i+j]))

print(dp[N-1])


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

dp = [0] * N
for i in range(1, N):
    hi = hs[i]
    dp2 = dp[max(0, i-K):i]
    costs = [abs(h - hi) for h in hs[max(0, i-K):i]]
    dp[i] = min([dpj + cost for dpj, cost in zip(dp2, costs)])

print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
INF = float('inf')

N, capW = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

dp = {0: 0}
for wi, vi in items:
    for w, v in list(dp.items()):
        if w+wi <= capW:
            dp[w+wi] = max(dp.get(w+wi, 0), v+vi)

print(max(dp.values()))


Fixed submission:
INF = float('inf')

N, capW = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

dp = [-INF] * (capW+1)
dp[0] = 0
for wi, vi in items:
    for w in reversed(range(capW+1)):
        if dp[w] == -INF: continue
        if w+wi <= capW:
            dp[w+wi] = max(dp[w+wi], dp[w] + vi)

print(max(dp))

Buggy python submission (verdict: Time Limit Exceeded):
INF = float('inf')

N, capW = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

dp = [-INF] * (capW+1)
dp[0] = 0
for wi, vi in items:
    for w in reversed(range(capW+1)):
        if dp[w] == -INF: continue
        if w+wi <= capW:
            dp[w+wi] = max(dp[w+wi], dp[w] + vi)

print(max(dp))


Fixed submission:
INF = float('inf')

N, capW = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

dp = [-INF] * (capW+1)
dp[0] = 0
for wi, vi in items:
    for w in reversed(range(capW+1)):
        if dp[w] == -INF: continue
        if w+wi <= capW:
            dp[w+wi] = max(dp[w+wi], dp[w] + vi)

print(max(dp))