Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
S=input()
N=len(S)
MOD=10**9+7

dp=[[0]*13 for _ in range(N+1)]
dp[0][0]=1
for i in range(1,N+1):
    c=S[i-1]
    if c=='?':
        for k in range(10):
            for n in range(13):
                nn=(n*10+k)%13
                dp[i][nn]+=dp[i-1][n]
                dp[i][nn]%=MOD
    else:
        for n in range(13):
            nn=(n*10+int(c))%13
            dp[i][nn]+=dp[i-1][n]
            dp[i][nn]%=MOD
print(dp[N][5])

Fixed submission:
S=input()
N=len(S)
MOD=10**9+7

dp=[[0]*13 for _ in range(N+1)]
dp[0][0]=1
for i in range(1,N+1):
    c=S[i-1]
    if c=='?':
        for k in range(10):
            for n in range(13):
                nn=(n*10+k)%13
                dp[i][nn]+=dp[i-1][n]
                dp[i][nn]%=MOD
    else:
        for n in range(13):
            nn=(n*10+int(c))%13
            dp[i][nn]+=dp[i-1][n]
            dp[i][nn]%=MOD
print(dp[N][5])
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[int(input()) for _ in range(N)]

dp=[1]*N
for i in range(N):
    for j in range(i):
        if A[j]<A[i]:
            dp[i]=max(dp[i],dp[j]+1)

print(sum([1 for v in dp if v==1]))


Fixed submission:
N=int(input())
A=[int(input()) for _ in range(N)]

import bisect
B=[A[N-1]]
for i in range(N-2,-1,-1):
    if A[i]>=B[-1]:
        B.append(A[i])
    else:
        B[bisect.bisect_right(B,A[i])]=A[i]

print(len(B))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
*A,=map(int, input().split())

def check(si,xi):
    X = [-1] * N
    X[si] = xi
    for i in range(N-1):
        ci = (si+i+1)%N-1
        X[ci+1] = 2*A[ci] - X[ci]
    if X[si] == 2*A[si-1] - X[si-1]:
        return X
    return []

mm = 10**10
mi = -1
for i,a in enumerate(A):
    if a < mm:
        mm = a
        mi = i

for xi in range(2*mm+1):
    X = check(mi, xi)
    if X:
        print(*X)
        exit()

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

S=sum(A)
X1=S-2*sum([A[i] for i in range(N) if i&1])

rain=X1
for i in range(N):
    print(rain)
    rain=(A[i]-rain//2)*2
Buggy python submission (verdict: Runtime Error):
N, X = map(int, input().split())
*L, = map(int, input().split())
ans = 0
d = 0
while ans < N and d <= X:
    ans += 1
    d += L[ans]
if d <= X:
    ans += 1
print(ans)


Fixed submission:
N, X = map(int, input().split())
*L, = map(int, input().split())
ans = 1
d = 0
for l in L:
    if d + l <= X:
        ans += 1
        d += l
    else:
        break
print(ans)

Buggy python submission (verdict: Runtime Error):
N, X = map(int, input().split())
*L, = map(int, input().split())
ans = 0
d = 0
while d <= X:
    d += L[ans]
    ans += 1
print(ans)


Fixed submission:
N, X = map(int, input().split())
*L, = map(int, input().split())
ans = 1
d = 0
for l in L:
    if d + l <= X:
        ans += 1
        d += l
    else:
        break
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import Counter
N=int(input())
balls=[tuple(map(int, input().split())) for _ in range(N)]

#2ボールの相対座標をぜんぶ調べる
R=[(x[0]-y[0],x[1]-y[1]) for x in balls for y in balls]
C=Counter(R).most_common(2)

#いちばん多い相対座標を(p,q)とする
#C[0]は(0,0)なので除外
print(N-(C[1][1]))

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

#2ボールの相対座標をぜんぶ調べる
R=[(x[0]-y[0],x[1]-y[1]) for x in balls for y in balls]
C=Counter(R).most_common()

#いちばん多い相対座標を(p,q)とする
#C[0]は(0,0)なので除外
if len(C)<=1:
    print(N)
else:
    print(N-(C[1][1]))
Buggy python submission (verdict: Runtime Error):
s = list(input())

ans = 0
i = 0
if s[0] == 'A' and s[1] == 'B' and s[2] == 'C':
    s[0] = 'B'
    s[1] = 'C'
    s[2] = 'A'
    ans += 1
    i = 3

while i+2 < len(s):
    if s[i] == 'A' and s[i+1] == 'B' and s[i+2] == 'C':
        ans += 1
        s[i] = 'B'
        s[i+1] = 'C'
        s[i+2] = 'A'
        i -= 1
    else:
        i += 1

print(ans)

Fixed submission:
s = input()

s = s.replace('BC', 'D')
ans = 0
a = 0
for c in s:
    if c == 'A':
        a += 1
    elif c == 'D':
        ans += a
    else:
        a = 0

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = list(input())

ans = 0
i = 0
while i+2 < len(s):
    if s[i] == 'A' and s[i+1] == 'B' and s[i+2] == 'C':
        ans += 1
        s[i] = 'B'
        s[i+1] = 'C'
        s[i+2] = 'A'
        i = max(0,i-1)
    else:
        i += 1

print(ans)

Fixed submission:
s = input()

s = s.replace('BC', 'D')
ans = 0
a = 0
for c in s:
    if c == 'A':
        a += 1
    elif c == 'D':
        ans += a
    else:
        a = 0

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = list(input())

ans = 0
while True:
    i = 0
    found = False
    while i+2 < len(s):
        if s[i] == 'A' and s[i+1] == 'B' and s[i+2] == 'C':
            ans += 1
            s[i] = 'B'
            s[i+1] = 'C'
            s[i+2] = 'A'
            i += 2
            found = True
        else:
            i += 1
    if not found:
        break

print(ans)

Fixed submission:
s = input()

s = s.replace('BC', 'D')
ans = 0
a = 0
for c in s:
    if c == 'A':
        a += 1
    elif c == 'D':
        ans += a
    else:
        a = 0

print(ans)
Buggy python submission (verdict: Runtime Error):
import heapq
N,K=map(int, input().split())
V=list(map(int, input().split()))

ans=-10**9
for l in range(K+1):
    for r in range(max(1,K+1-l)):
        for d in range(max(1,K+1-l-r)):
            h=V[:l]
            heapq.heapify(h)
            for i in range(r): heapq.heappush(h, V[-1-i])
            for i in range(min(d,len(h))): heapq.heappop(h)
            ans=max(ans,sum(h))
print(ans)

Fixed submission:
import heapq
N,K=map(int, input().split())
V=list(map(int, input().split()))

ans=-10**9
for l in range(min(N,K)+1):
    for r in range(max(1,min(N,K)+1-l)):
        for d in range(max(1,K+1-l-r)):
            h=V[:l]
            heapq.heapify(h)
            for i in range(r): heapq.heappush(h, V[-1-i])
            for i in range(min(d,len(h))): heapq.heappop(h)
            ans=max(ans,sum(h))
print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
l, r = 1, N
for _ in range(M):
    L, R = map(int, input().split())
    l = max(l, L)
    r = min(r, R)
print((max(0, r-l+1))

Fixed submission:
N, M = map(int, input().split())
l, r = 1, N
for _ in range(M):
    L, R = map(int, input().split())
    l = max(l, L)
    r = min(r, R)
print(max(0, r-l+1))
Buggy python submission (verdict: Runtime Error):
import sys
def main():
    input = sys.stdin.readline
    N,M=map(int, input().split())
    *A,=map(int, input().split())
    BC=[tuple(map(int, input().split())) for _ in range(M)]

    A.sort()
    BC.sort(key=lambda x:x[1], reverse=True)
    ans=0
    i=0
    from bisect import bisect_right
    for b,c in BC:
        j = bisect_right(A, c, i, i+b)
        ans += c*(j-i)
        i=j
    for j in range(i,N):
        ans+=A[j]
    print(ans)

if __name__ == '__main__':
    main()

Fixed submission:
import sys
def main():
    input = sys.stdin.readline
    N,M=map(int, input().split())
    *A,=map(int, input().split())
    BC=[tuple(map(int, input().split())) for _ in range(M)]

    A.sort()
    BC.sort(key=lambda x:x[1], reverse=True)
    ans=0
    i=0
    from bisect import bisect_right
    for b,c in BC:
        j = bisect_right(A, c, i, min(N,i+b))
        ans += c*(j-i)
        i=j
    for j in range(i,N):
        ans+=A[j]
    print(ans)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
N,K=map(int, input().split())

t = 0
import math
for x in range(1, min(N,K-1)+1):
    t += (1-pow(0.5, math.ceil(math.log2(K/x))))

print(1 - t / N)

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

t = 0
import math
for x in range(1, min(N,K-1)+1):
    t += (1-pow(0.5, math.ceil(math.log2(K/x))))

print(1 - t / N)
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
S=input()

#連続する0or1の数をリスト化
L=[]
c=1
for i in range(1,N):
    if S[i]==S[i-1]:
        c+=1
        continue
    if c>0:
        L.append(c)
    c=1
if c>0:
    L.append(c)

#1で始まる2K+1個の塊を連続させることができる
#最大値を求める
ans=0
start=0
if S[0]=='0':
    #0から始まっている場合はそこから2K個をつなげる
    ans=sum(L[0:2*K])
    start=1
for i in range(start,len(L),2):
    ans=max(ans,sum(L[i:i+2*K+1]))
print(ans)


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

ans=0
history=[0]*(2*K+1)
sum_recent=0
idx=0
c=1
for i in range(1,N+1):
    #print(ans,sum_recent,history,idx,c)
    if i<N and S[i]==S[i-1]:
        c+=1
        continue
    sum_recent=sum_recent+c-history[idx]
    history[idx]=c
    idx=(idx+1)%(2*K+1)
    c=1
    if S[i-1]=='1':
        ans=max(ans,sum_recent)
    elif i==N:
        sum_recent-=history[idx]
        ans=max(ans,sum_recent)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappop, heappush
import sys
def main(X, Y, Z, K, A, B, C):
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)
    used = [[[False] * Z for _ in range(Y)] for __ in range(X)]
    q = [(-(A[0] + B[0] + C[0]), 0, 0, 0)]
    used[0][0][0] = True
    for i in range(K):
        v, ai, bi, ci = heappop(q)
        print(-v)
        for nai, nbi, nci in [(ai + 1, bi, ci), (ai, bi + 1, ci), (ai, bi, ci + 1)]:
            if nai >= X or nbi >= Y or nci >= Z: continue
            if used[nai][nbi][nci]: continue
            used[nai][nbi][nci] = True
            heappush(q, (-(A[nai] + B[nbi] + C[nci]), nai, nbi, nci))

if __name__ == '__main__':
    input = sys.stdin.readline
    X, Y, Z, K = map(int, input().split())
    *A, = map(int, input().split())
    *B, = map(int, input().split())
    *C, = map(int, input().split())
    main(X, Y, Z, K, A, B, C)


Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from itertools import product
import sys
def main(X, Y, Z, K, A, B, C):
    AB = sorted([a + b for a, b in product(A, B)], reverse=True)
    ABC = sorted([ab + c for ab, c in product(AB[:K], C)], reverse=True)
    for k in range(K):
        print(ABC[k])

if __name__ == '__main__':
    input = sys.stdin.readline
    X, Y, Z, K = map(int, input().split())
    *A, = map(int, input().split())
    *B, = map(int, input().split())
    *C, = map(int, input().split())
    main(X, Y, Z, K, A, B, C)

Buggy python submission (verdict: Time Limit Exceeded):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappop, heappush
import sys
def main(X, Y, Z, K, A, B, C):
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)
    used = [[[False] * Z for _ in range(Y)] for __ in range(X)]
    q = [(-(A[0] + B[0] + C[0]), 0, 0, 0)]
    used[0][0][0] = True
    for i in range(K):
        v, ai, bi, ci = heappop(q)
        print(-v)
        for nai, nbi, nci in [(ai + 1, bi, ci), (ai, bi + 1, ci), (ai, bi, ci + 1)]:
            if nai >= X or nbi >= Y or nci >= Z: continue
            if used[nai][nbi][nci]: continue
            used[nai][nbi][nci] = True
            heappush(q, (-(A[nai] + B[nbi] + C[nci]), nai, nbi, nci))

if __name__ == '__main__':
    input = sys.stdin.readline
    X, Y, Z, K = map(int, input().split())
    *A, = map(int, input().split())
    *B, = map(int, input().split())
    *C, = map(int, input().split())
    main(X, Y, Z, K, A, B, C)


Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from itertools import product
import sys
def main(X, Y, Z, K, A, B, C):
    AB = sorted([a + b for a, b in product(A, B)], reverse=True)
    ABC = sorted([ab + c for ab, c in product(AB[:K], C)], reverse=True)
    for k in range(K):
        print(ABC[k])

if __name__ == '__main__':
    input = sys.stdin.readline
    X, Y, Z, K = map(int, input().split())
    *A, = map(int, input().split())
    *B, = map(int, input().split())
    *C, = map(int, input().split())
    main(X, Y, Z, K, A, B, C)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

P=list(range(N+1))
C=[1 for _ in range(N+1)]
C[0] = 0

def root(x):
    if P[x]==x: return x
    P[x] = root(P[x])
    return P[x]

def unite(a,b):
    ra = root(a)
    rb = root(b)
    C[ra] += C[rb]
    C[rb] = 0
    P[rb] = ra

def same(a,b):
    return root(a) == root(b)

def count(x):
    return C[root(x)]

ans=[0]*(M+1)
ans[M] = N * (N-1)

for i in range(M-1,-1,-1):
    a,b = B[i]
    if same(a,b):
        ans[i] = ans[i+1]
        continue
    ans[i] = ans[i+1] - count(a) * count(b)
    unite(a,b)

for i in range(1,M+1):
    print(ans[i] - ans[0])

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

P=list(range(N+1))
C=[1 for _ in range(N+1)]
C[0] = 0

def root(x):
    if P[x]==x: return x
    P[x] = root(P[x])
    return P[x]

def unite(a,b):
    ra = root(a)
    rb = root(b)
    C[ra] += C[rb]
    C[rb] = 0
    P[rb] = ra

def same(a,b):
    return root(a) == root(b)

def count(x):
    return C[root(x)]

ans=[0]*(M+1)
ans[M] = N * (N-1)

for i in range(M-1,-1,-1):
    a,b = B[i]
    if same(a,b):
        ans[i] = ans[i+1]
        continue
    ans[i] = ans[i+1] - count(a) * count(b)
    unite(a,b)

for i in range(1,M+1):
    print(ans[i] - ans[0])

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
N,M=map(int, input().split())
B=[tuple(map(int, input().split())) for _ in range(M)]

P=list(range(N+1))
C=[1 for _ in range(N+1)]
C[0] = 0

def root(x):
    if P[x]==x: return x
    P[x] = root(P[x])
    return P[x]

def unite(a,b):
    ra = root(a)
    rb = root(b)
    C[ra] += C[rb]
    C[rb] = 0
    P[rb] = ra

def same(a,b):
    return root(a) == root(b)

def count(x):
    return C[root(x)]

ans=[0]*(M+1)
ans[M] = N * (N-1)

for i in range(M-1,-1,-1):
    a,b = B[i]
    if same(a,b):
        ans[i] = ans[i+1]
        continue
    ans[i] = ans[i+1] - count(a) * count(b)
    unite(a,b)

for i in range(1,M+1):
    print(ans[i] - ans[0])

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

P=list(range(N+1))
C=[1 for _ in range(N+1)]
C[0] = 0

def root(x):
    if P[x]==x: return x
    P[x] = root(P[x])
    return P[x]

def unite(a,b):
    ra = root(a)
    rb = root(b)
    C[ra] += C[rb]
    C[rb] = 0
    P[rb] = ra

def same(a,b):
    return root(a) == root(b)

def count(x):
    return C[root(x)]

ans=[0]*(M+1)
ans[M] = N * (N-1)

for i in range(M-1,-1,-1):
    a,b = B[i]
    if same(a,b):
        ans[i] = ans[i+1]
        continue
    ans[i] = ans[i+1] - count(a) * count(b)
    unite(a,b)

for i in range(1,M+1):
    print(ans[i] - ans[0])
Buggy python submission (verdict: Time Limit Exceeded):
A,B,Q=map(int, input().split())
S=[int(input()) for _ in range(A)]
T=[int(input()) for _ in range(B)]
X=[int(input()) for _ in range(Q)]

import bisect
def solve(x):
    sr=bisect.bisect_right(S,x)
    tr=bisect.bisect_right(T,x)
    sl=sr-1
    tl=tr-1
    ret=10**12
    if sl>=0 and tl>=0:
        ret=min(ret,x-min(S[sl],T[tl]))
    if sr<A and tl>=0:
        ret=min(ret,S[sr]-T[tl]+min(S[sr]-x,x-T[tl]))
    if sl>=0 and tr<B:
        ret=min(ret,T[tr]-S[sl]+min(T[tr]-x,x-S[sl]))
    if sr<A and tr<B:
        ret=min(ret,max(S[sr],T[tr])-x)
    return ret

for x in X:
    print(solve(x))

Fixed submission:
import sys
input = sys.stdin.readline
A,B,Q=map(int, input().split())
S=[int(input()) for _ in range(A)]
T=[int(input()) for _ in range(B)]
X=[int(input()) for _ in range(Q)]

import bisect
def solve(x):
    sr=bisect.bisect_right(S,x)
    tr=bisect.bisect_right(T,x)
    sl=sr-1
    tl=tr-1
    ret=10**12
    if sl>=0 and tl>=0:
        ret=min(ret,x-min(S[sl],T[tl]))
    if sr<A and tl>=0:
        ret=min(ret,S[sr]-T[tl]+min(S[sr]-x,x-T[tl]))
    if sl>=0 and tr<B:
        ret=min(ret,T[tr]-S[sl]+min(T[tr]-x,x-S[sl]))
    if sr<A and tr<B:
        ret=min(ret,max(S[sr],T[tr])-x)
    return ret

for x in X:
    print(solve(x))

Buggy python submission (verdict: Time Limit Exceeded):
A,B,Q=map(int, input().split())
S=[int(input()) for _ in range(A)]
T=[int(input()) for _ in range(B)]
X=[int(input()) for _ in range(Q)]

import bisect
def solve(x):
    sl=bisect.bisect_left(S,x)
    sr=bisect.bisect_right(S,x)
    tl=bisect.bisect_left(T,x)
    tr=bisect.bisect_right(T,x)
    sl-=1
    tl-=1
    ret=10**12
    if sl>=0 and tl>=0:
        ret=min(ret,x-min(S[sl],T[tl]))
    if sr<A and tl>=0:
        ret=min(ret,S[sr]-T[tl]+min(S[sr]-x,x-T[tl]))
    if sl>=0 and tr<B:
        ret=min(ret,T[tr]-S[sl]+min(T[tr]-x,x-S[sl]))
    if sr<A and tr<B:
        ret=min(ret,max(S[sr],T[tr])-x)
    return ret

for x in X:
    print(solve(x))

Fixed submission:
import sys
input = sys.stdin.readline
A,B,Q=map(int, input().split())
S=[int(input()) for _ in range(A)]
T=[int(input()) for _ in range(B)]
X=[int(input()) for _ in range(Q)]

import bisect
def solve(x):
    sr=bisect.bisect_right(S,x)
    tr=bisect.bisect_right(T,x)
    sl=sr-1
    tl=tr-1
    ret=10**12
    if sl>=0 and tl>=0:
        ret=min(ret,x-min(S[sl],T[tl]))
    if sr<A and tl>=0:
        ret=min(ret,S[sr]-T[tl]+min(S[sr]-x,x-T[tl]))
    if sl>=0 and tr<B:
        ret=min(ret,T[tr]-S[sl]+min(T[tr]-x,x-S[sl]))
    if sr<A and tr<B:
        ret=min(ret,max(S[sr],T[tr])-x)
    return ret

for x in X:
    print(solve(x))
Buggy python submission (verdict: Time Limit Exceeded):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(N, M, G, root):
    P = [-1] * N
    D = [-1] * N
    q = deque()
    q.append((root, 0, -1))
    while q:
        v, d, p = q.popleft()
        if D[v] < d:
            D[v] = d
            P[v] = p
        for to in G[v]:
            q.append((to, d + 1, v))
    for p in P:
        print(p + 1)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    I = [0] * N
    for _ in range(N - 1 + M):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        G[a].append(b)
        I[b] += 1
    main(N, M, G, I.index(0))


Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(N, M, G, R, I, root):
    P = [-1] * N
    D = [-1] * N
    D[root] = 0
    q = deque()
    q.append(root)
    while q:
        v = q.popleft()
        for to in G[v]:
            I[to] -= 1
            if I[to] == 0:
                p = pd = -1
                for r in R[to]:
                    if D[r] > pd:
                        pd = D[r]
                        p = r
                D[to] = pd + 1
                P[to] = p
                q.append(to)
    for p in P:
        print(p + 1)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    R = [[] for _ in range(N)]
    I = [0] * N
    for _ in range(N - 1 + M):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        G[a].append(b)
        R[b].append(a)
        I[b] += 1
    main(N, M, G, R, I, I.index(0))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

diff = [0] * (N)
diffsum = 0
for i in range(N):
    diff[i] = A[i] - B[i]
    diffsum += diff[i]
if diffsum < 0:
    print("-1")
    exit()
diff.sort()
change = [0] * (N)
for i in range(N):
    if diff[i] < 0:
        change[i] = 1
        for j in range(N)[::-1]:
            if diff[j] > 0:
                change[j] = 1
                ch = min(-diff[i], diff[j])
                diff[i] += ch
                diff[j] -= ch
                if diff[i] == 0:
                    break
print(sum(change))

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

diff = [0] * (N)
diffsum = 0
for i in range(N):
    diff[i] = A[i] - B[i]
    diffsum += diff[i]
if diffsum < 0:
    print("-1")
    exit()
diff.sort()
count = 0
sumn = 0
for i in range(N):
    if diff[i] < 0:
        count += 1
        sumn -= diff[i]
    else:
        break
for j in range(N)[::-1]:
    if sumn > 0:
        count += 1
        sumn -= diff[j]
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
H,W=map(int, input().split())
M=[list(map(lambda x:1 if x=='#' else 0,input())) for _ in range(H)]

R=[[0 for _ in range(H*W+W)] for __ in range(H*W+W)]

#横1マス
for y in range(H):
    l=M[y]
    for x in range(W-1):
        if l[x]^l[x+1]:
            R[y*W+x][y*W+x+1]=1
            R[y*W+x+1][y*W+x]=1

#縦1マス
for x in range(W):
    for y in range(H-1):
        if M[y][x]^M[y+1][x]:
            R[y*W+x][(y+1)*W+x]=1
            R[(y+1)*W+x][y*W+x]=1

for z in range(H*W+W):
    for p in range(H*W+W):
        for q in range(H*W+W):
            if R[p][z] and R[q][z]:
                if R[p][q]&1: continue
                d=R[p][z]+R[q][z]
                R[p][q]=R[q][p]=d

ans=0
for p in range(H*W+W):
    for q in range(p+1,H*W+W):
        if R[p][q]&1: ans+=1
print(ans)


Fixed submission:
H,W=map(int, input().split())
M=[list(input()) for _ in range(H)]

used=[[False for _ in range(W)] for __ in range(H)]
def dfs(sx,sy):
    global used
    if used[sy][sx]: return (0,0)
    black=white=0
    stack=[(sx,sy)]
    used[sy][sx]=True
    while stack:
        x,y=stack.pop()
        if M[y][x]=='#':
            black+=1
        else:
            white+=1
        for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
            nx,ny=x+dx,y+dy
            if 0<=nx<W and 0<=ny<H and not used[ny][nx]:
                if M[y][x]!=M[ny][nx]:
                    stack.append((nx,ny))
                    used[ny][nx]=True
    return (black,white)

ans=0
for y in range(H):
    for x in range(W):
        black,white=dfs(x,y)
        ans+=black*white
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = list(map(int, input().split()))

#dp[足場i]=足場iにたどり着く最小コスト
dp = [10**10 for _ in range(N+10)]

dp[0] = 0
for i in range(N):
    for k in range(1,K+1):
        if i+k <= N-1:
            dp[i+k] = min(dp[i+k], dp[i] + abs(H[i]-H[i+k]))

print(dp[N-1])


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

#dp[足場i]=足場iにたどり着く最小コスト
dp = [10**10 for _ in range(N+10)]

dp[0] = 0
for i in range(N):
    for k in range(1,min(K+1,N-i)):
        dp[i+k] = min(dp[i+k], dp[i] + abs(H[i]-H[i+k]))

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

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    AC = accumulate([0] + A, func=lambda x,y:(x+y)%M)
    ACC = Counter(AC)

    ans = 0
    for c in ACC.values():
        ans += c * (c-1) // 2
    print(ans)

if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import Counter
from itertools import accumulate

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    AC = accumulate([0] + A, func=lambda x,y:(x+y)%M)
    ACC = Counter(AC)

    ans = 0
    for c in ACC.values():
        ans += c * (c-1) // 2
    print(ans)

if __name__ == '__main__':
    main()