Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N):
AB.sort(key = lambda x:x[0])
dp = [0]*(T+1)
for A,B in AB:  #それぞれの食事について
    for i in range(T-1,-1,-1):
        if A+i>=T:  #時間オーバー
            dp[T] = max(dp[T], dp[i]+B)
        else:   #時間内
            dp[i+A] = max(dp[i+A],dp[i]+B)
#これが成り立つのはAB.sortしているから
print(max(dp))


Fixed submission:
N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB.sort(key = lambda x:x[0])
dp = [0]*(T+1)
for A,B in AB:  #それぞれの食事について
    for i in range(T-1,-1,-1):
        if A+i>=T:  #時間オーバー
            dp[T] = max(dp[T], dp[i]+B)
        else:   #時間内
            dp[i+A] = max(dp[i+A],dp[i]+B)
#これが成り立つのはAB.sortしているから
print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort()
F.sort(reverse=True)
#二分探索をつくる
L = -1
R = 10**12 +1 
while R-L>1:
    Mid = (L+R)//2
    tmp = 0
    for a,f in zip(A,F):
        tmp += max(0, a-Mid//f)
    if tmp<=K:
        R = Mid
    else:
        L = Mid
print(R)

Fixed submission:
N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort()
F.sort(reverse=True)
#二分探索をつくる
L = -1
R = 10**12 +1 
while R-L>1:
    Mid = (L+R)//2
    tmp = 0
    for a,f in zip(A,F):
        tmp += max(0, a-Mid//f)
    if tmp<=K:
        R = Mid
    else:
        L = Mid
print(R)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = list(map(int,input().split()))
ans = 0
L.sort()
for na,a in enumerate(L[:N-2]):
    for nb_,b in enumerate(L[na+1:N-1]):
        nb = nb_+na+1 
        for c in L[nb+1:]:
            if c < a+b:
               ans += 1
            else:
                break
print(ans)


Fixed submission:
from bisect import bisect_left
N = int(input())
L = list(map(int,input().split()))
ans = 0
L.sort()
for na,a in enumerate(L[:N-2]):
    for nb_,b in enumerate(L[na+1:N-1]):
        nb = nb_+na+1
        nc = bisect_left(L,a+b)
        ans += nc-nb-1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
N = int(input())
L = list(map(int,input().split()))
lis = combinations(L,3)
ans = 0
for thr in lis:
    if thr[0]<thr[1]+thr[2] and thr[1]<thr[2]+thr[0] and thr[2]<thr[0]+thr[1]:
        ans += 1
print(ans)

Fixed submission:
from bisect import bisect_left
N = int(input())
L = list(map(int,input().split()))
ans = 0
L.sort()
for na,a in enumerate(L[:N-2]):
    for nb_,b in enumerate(L[na+1:N-1]):
        nb = nb_+na+1
        nc = bisect_left(L,a+b)
        ans += nc-nb-1
print(ans)
Buggy python submission (verdict: Runtime Error):
S=input()
K=int(input())
S2 = S*2
tmp=0
tmp2=0
for i in range(1,S):
    if S[i-1]==S[i]:
        S[i]="0"
        tmp += 1

for i in range(1,S2):
    if S2[i-1]==S2[i]:
        S2[i]="0"
        tmp2 += 1
print(tmp+(tmp2-tmp)*(K-1))

Fixed submission:
S=list(input())
K=int(input())
S2 = S*2
tmp=0
tmp2=0

if all([S[i] == S[0] for i in range(1,len(S))]):
    print((len(S)*K)//2)
    exit()
for i in range(1,len(S)):
    if S[i-1]==S[i]:
        S[i]="0"
        tmp += 1

for i in range(1,len(S2)):
    if S2[i-1]==S2[i]:
        S2[i]="0"
        tmp2 += 1

print(tmp+(tmp2-tmp)*(K-1))

Buggy python submission (verdict: Runtime Error):
S=input()
K=int(input())
S2 = S*2
tmp=0
tmp2=0
for i in range(1,S):
    if S[i-1]==S[i]:
        S[i]="0"
        tmp += 1

for i in range(1,S2):
    if S2[i-1]==S2[i]:
        S[i]="0"
        tmp2 += 1
print(tmp+tmp*(K-1))

Fixed submission:
S=list(input())
K=int(input())
S2 = S*2
tmp=0
tmp2=0

if all([S[i] == S[0] for i in range(1,len(S))]):
    print((len(S)*K)//2)
    exit()
for i in range(1,len(S)):
    if S[i-1]==S[i]:
        S[i]="0"
        tmp += 1

for i in range(1,len(S2)):
    if S2[i-1]==S2[i]:
        S2[i]="0"
        tmp2 += 1

print(tmp+(tmp2-tmp)*(K-1))
Buggy python submission (verdict: Runtime Error):
#https://atcoder.jp/contests/abc141/submissions/7539109
#Z-Algorithm
n = int(input())
s = input()
 
a = ""
ans = 0
for i in range(n):
    a += s[i]
    while(len(a) > 0):
        if a in s[i+1:]:    #見つかる限りこの処理
            ans = max(ans,len(a))
            break
        else:               #ダメなら次の文字を接頭辞に、短いものは調べなくてよい
        a = a[1:]
print(ans)

Fixed submission:
#https://atcoder.jp/contests/abc141/submissions/7539109
#Z-Algorithm
n = int(input())
s = input()
 
a = ""
ans = 0
for i in range(n):
    a += s[i]
    while(len(a) > 0):
        if a in s[i+1:]:    #見つかる限りこの処理
            ans = max(ans,len(a))
            break
        else:               #ダメなら次の文字を接頭辞に、短いものは調べなくてよい
            a = a[1:]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
ans = 0
TF = False
for i in range((N//2),-1,-1): #iが長さ
    if TF == True:
        break
    for j in range(N-2*i):    #jは開始位置
        if TF == True:
            break
        tmp = S[j:j+i+1]
        for k in range(j+i+1,N-i):    #kは判断する方の開始位置
            if S[k:k+i+1] == tmp:
                #print("i=",i,"j=",j,"k=",k, tmp)
                ans = i+1
                TF = True
                break
print(ans)

Fixed submission:
#https://atcoder.jp/contests/abc141/submissions/7539109
#Z-Algorithm
n = int(input())
s = input()
 
a = ""
ans = 0
for i in range(n):
    a += s[i]
    while(len(a) > 0):
        if a in s[i+1:]:    #見つかる限りこの処理
            ans = max(ans,len(a))
            break
        else:               #ダメなら次の文字を接頭辞に、短いものは調べなくてよい
            a = a[1:]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
ans = 0
TF = False
for i in range(0,(N//2)+1): #iが長さ
    TF = False
    for j in range(N-2*i):    #jは開始位置
        if TF == True:
            break
        tmp = S[j:j+i+1]
        for k in range(j+i+1,N-i):    #kは判断する方の開始位置
            if S[k:k+i+1] == tmp:
                #print("i=",i,"j=",j,"k=",k, tmp)
                ans = i+1
                TF = True
                break
print(ans)

Fixed submission:
#https://atcoder.jp/contests/abc141/submissions/7539109
#Z-Algorithm
n = int(input())
s = input()
 
a = ""
ans = 0
for i in range(n):
    a += s[i]
    while(len(a) > 0):
        if a in s[i+1:]:    #見つかる限りこの処理
            ans = max(ans,len(a))
            break
        else:               #ダメなら次の文字を接頭辞に、短いものは調べなくてよい
            a = a[1:]
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque
N = int(input())
A = [deque(list(map(int, input().split()))) for _ in range(N)]
ans = 0
t = 0
for i in range(10**3+1):
    for k in range(N):
        if A[k] != deque([]):
            if A[k][0] == 0:
                A[k].popleft()
        else:
            t += 1
    if t == N:
        break
    t = 0
    for j in range(N):
        if A[j]:
            tmp = A[j][0]
        else:
            continue
        if tmp-1 > j and A[tmp-1][0] -1 == j:
            A[j][0] = 0
            A[tmp-1][0] = 0
    ans += 1
if ans == 1001:
    print(-1)
    exit()
print(ans-1)

Fixed submission:
S = list(input())
T = list(input())
ans = 0
for i in range(3):
    if S[i] == T[i]:
        ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
H = list(map(int, input().split()))
ans = 0
ansk = 0
tmp = 0
for i in range(N-1):
    if tmp > 0:
        tmp -= 1
        continue
    ans = 0
    for j in range(i+1,N):
            if H[j-1] < H[j]:
                tmp = ans
                ansk = max(ansk,ans)
                break
            ans += 1
            if j == N-1:
                ansk = max(ansk,ans)
                break
print(ansk)

Fixed submission:
N = int(input())
H = list(map(int, input().split()))
ans = 0
ansk = 0
tmp = -1
while tmp < N:
    tmp += 1
    if ans > 0:
        tmp += ans-1
        ans = 0
        continue
    for j in range(tmp+1,N):
            if H[j-1] < H[j]:
                ansk = max(ansk,ans)
                break
            ans += 1
            if j == N-1:
                ansk = max(ansk,ans)
                tmp = N
                break
print(ansk)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
H = list(map(int, input().split()))
ans = 0
ansk = 0
tmp = 0
for i in range(N-1):
    if tmp > 0:
        tmp -= 1
        continue
    ans = 0
    for j in range(i+1,N):
            if H[j-1] < H[j]:
                tmp = ans
                ansk = max(ansk,ans)
                break
            ans += 1
            if j == N-1:
                ansk = max(ansk,ans)
                break
print(ansk)

Fixed submission:
N = int(input())
H = list(map(int, input().split()))
ans = 0
ansk = 0
tmp = -1
while tmp < N:
    tmp += 1
    if ans > 0:
        tmp += ans-1
        ans = 0
        continue
    for j in range(tmp+1,N):
            if H[j-1] < H[j]:
                ansk = max(ansk,ans)
                break
            ans += 1
            if j == N-1:
                ansk = max(ansk,ans)
                tmp = N
                break
print(ansk)

Buggy python submission (verdict: Runtime Error):
A,B = map(int, input().split())
ans = 0
b = A
for i in range(21):
    ans += 1
    if b >= B:
        break
    b += A-1
print(ans)

Fixed submission:
N = int(input())
H = list(map(int, input().split()))
ans = 0
ansk = 0
tmp = -1
while tmp < N:
    tmp += 1
    if ans > 0:
        tmp += ans-1
        ans = 0
        continue
    for j in range(tmp+1,N):
            if H[j-1] < H[j]:
                ansk = max(ansk,ans)
                break
            ans += 1
            if j == N-1:
                ansk = max(ansk,ans)
                tmp = N
                break
print(ansk)
Buggy python submission (verdict: Runtime Error):

M = 10**9+7
N = int(input())
S = list(input())
s = []

#0ならW、1ならB
s_append = s.append
for i in range(2*N):
    if S[i] == "B":
        s_append(1)
    else:
        s_append(0)

#端が0なら0を返す
if s[0] == 0 or s[2*N-1] == 0:
    print(0)
    exit()

ans = 0
lis = [0] #0なら左、1なら右
#全て0にする
lis_append = lis.append
for j in range(1,2*N):
    j1 = lis[j-1]
    if s[j-1] != s[j]:
        lis_append(j1)
    elif j1 == 0:
        lis_append(1)
    else:
        lis_append(0)

#左と右の数が違ったら0を返す
if lis.count(0) != lis.count(1):
    print(0)
    exit()

#"右"が選べる"左"の選択肢を掛けていく
cnt = 1
ans = 1
for k in range(1,2*N):
    if lis[k] == 0:
        cnt += 1
    else:
        ans *= cnt
        cnt -= 1

#N!をかける
for l in range(1,N+1):
    ans *= l
    ans %= M
print(ans)

Fixed submission:
M,D = map(int, input().split())

ans = 0

if D <= 21:
    ans = 0
else:
    for d_ in range(22,D+1):
        d = list(map(int, str(d_)))
        if int(d[0])<2 or int(d[1])<2:
            continue
        for m in range(1,M+1):
            if d[0] * d[1] == m:
                ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
M = 10**9+7
import sys
input = sys.stdin.readline

N,K = map(int, input().split())
A = list(map(int, input().split()))
A_ = sorted(A, reverse = True)
ans = 0
ans_ = 0
for i in range(0,N-1):
      for j in range(i+1,N):
          if A[i] > A[j]:
            ans += 1
         if A_[i] > A_[j]:
            ans_ += 1

print(((int((K*(K-1))/2)%M)*ans_+ans*K)%M)

Fixed submission:
M = 10**9+7
import sys
input = sys.stdin.readline
def main():
    N,K = map(int, input().split())
    A = list(map(int, input().split()))
    A_ = sorted(A, reverse = True)
    ans = 0
    ans_ = 0
    for i in range(0,N-1):
        for j in range(i+1,N):
            if A[i] > A[j]:
                ans += 1
            if A_[i] > A_[j]:
                ans_ += 1

    print(int((((K*(K-1)//2)%M)*ans_+ans*K)%M))

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#https://atcoder.jp/contests/abc138/submissions/8926003

S = input()
T = input()
if not set(T) <= set(S):
    print(-1)
    exit()
now = -1
rep = 0
for t in T:
    now = S.find(t,now+1)
    if now == -1:
        rep += 1
        now = S.find(t)
print(rep*len(S)+now+1)


Fixed submission:
from bisect import bisect_left
s = list(input())
t = list(input())
N = len(s)
if not set(t) <= set(s):
    print(-1)
    exit()
lis = [[] for _ in range(26)]
s = s+s
for i in range(2*N):
    alp = ord(s[i])-97
    lis[alp].append(i+1)
nex = [[0]*N for _ in range(26)]
for now in range(N):
    for alp in range(26):
        if not lis[alp]:
            continue
        i = bisect_left(lis[alp],now+1)
        #print(lis[alp],now+1,i)
        nex[alp][now] = lis[alp][i] - now
ans = 0
now = 0
tN = len(t)
for i in range(tN):
    alp = ord(t[i])-97
    ne = nex[alp][now]
    ans += ne
    if now+ne >= N:
        now += ne-N
    else:
        now += ne
    #print(now,ans)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
s = list(input())
t = list(input())
N = len(s)
if not set(t) <= set(s):
    print(-1)
    exit()
lis = [[] for _ in range(26)]
s = s+s
for i in range(2*N):
    alp = ord(s[i])-97
    lis[alp].append(i+1)
nex = [[0]*N for _ in range(26)]
for now in range(N):
    for alp in range(26):
        if not lis[alp]:
            continue
        i = bisect_left(lis[alp],now+1)
        #print(lis[alp],now+1,i)
        nex[alp][now] = lis[alp][i] - now
ans = 0
now = 0
tN = len(t)
for i in range(tN):
    alp = ord(t[i])-97
    ne = nex[alp][now]
    ans += ne
    if now+ne >= N:
        now += ne-N
    else:
        now += ne
    #print(now,ans)
print(ans)

Fixed submission:
from bisect import bisect_left
s = list(input())
t = list(input())
N = len(s)
if not set(t) <= set(s):
    print(-1)
    exit()
lis = [[] for _ in range(26)]
s = s+s
for i in range(2*N):
    alp = ord(s[i])-97
    lis[alp].append(i+1)
nex = [[0]*N for _ in range(26)]
for now in range(N):
    for alp in range(26):
        if not lis[alp]:
            continue
        i = bisect_left(lis[alp],now+1)
        #print(lis[alp],now+1,i)
        nex[alp][now] = lis[alp][i] - now
ans = 0
now = 0
tN = len(t)
for i in range(tN):
    alp = ord(t[i])-97
    ne = nex[alp][now]
    ans += ne
    if now+ne >= N:
        now += ne-N
    else:
        now += ne
    #print(now,ans)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s_lis =[]
for _ in range(n):
    s = sorted(input())
    s_lis.append("".join(s))


ans = 0
for i in range(n):
    for j in range(i+1,n):
        if s_lis[i] == s_lis[j]:
            ans += 1

print(ans)


Fixed submission:
n = int(input())
ans = 0
dic = {}
for i in range(n):
    s = input()
    s = str(sorted(s))
    tmp = dic.get(s,0)
    ans += tmp
    dic[s] = tmp + 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s_lis =[]
for _ in range(n):
    s = sorted(input())
    s_lis.append("".join(s))


ans = 0
for i in range(n):
    for j in range(i+1,n):
        if s_lis[i] == s_lis[j]:
            ans += 1

print(ans)

Fixed submission:
n = int(input())
ans = 0
dic = {}
for i in range(n):
    s = input()
    s = str(sorted(s))
    tmp = dic.get(s,0)
    ans += tmp
    dic[s] = tmp + 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import copy
n = int(input())
a = [int(input()) for _ in range(n)]

for i in range(n):
    a_ = copy.copy(a)
    a_.pop(i)
    print(max(a_))

Fixed submission:
n = int(input())
a = [int(input()) for _ in range(n)]
a_ = sorted(a)
a_max = a_[-1]
a_sec = a_[-2]
for i in range(n):
    if a[i] == a_max:
        print(a_sec)
    else:
        print(a_max)

Buggy python submission (verdict: Time Limit Exceeded):
import copy
n = int(input())
a = [int(input()) for _ in range(n)]

for i in range(n):
    a_ = copy.copy(a)
    a_.pop(i)
    print(max(a_))

Fixed submission:
n = int(input())
a = [int(input()) for _ in range(n)]
a_ = sorted(a)
a_max = a_[-1]
a_sec = a_[-2]
for i in range(n):
    if a[i] == a_max:
        print(a_sec)
    else:
        print(a_max)
Buggy python submission (verdict: Runtime Error):
#ttps://atcoder.jp/contests/abc134/submissions/6459172
from bisect import bisect
n = int(input())
A = [int(input()) for _ in range(n)]
dp = [1]
for a in A:
    a *= -1
    i = bisect(dp,a)   #既存に-aを挿入した時のindex
    print(dp)
    if i < len(dp):    #挿入位置が長さより小さい時（要はabsが一番小さくない時
        dp[i] = a      #-aにする
    else:
        dp.append(a)    #右端に-aを普通に追加
    print(dp)

print(len(dp))

Fixed submission:
#ttps://atcoder.jp/contests/abc134/submissions/6459172
from bisect import bisect
n = int(input())
A = [int(input()) for _ in range(n)]
dp = [1]
for a in A:
    a *= -1
    i = bisect(dp,a)   #既存に-aを挿入した時のindex

    if i < len(dp):    #挿入位置が長さより小さい時（要はabsが一番小さくない時
        dp[i] = a     #-aにする
    else:
        dp.append(a)    #右端に-aを普通に追加


print(len(dp))
Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())

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

for i in range(1,K+1):
    if N-K+1 < i:
        print(0)
        continue
    else:
        print((nCr(N-K+1,i)*nCr(K-1,i-1))%M)


Fixed submission:
N,K = map(int,input().split())
M = 10**9+7
def nCr(n, r, mod=10**9+7):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

for i in range(1,K+1):
    if N-K+1 < i:
        print(0)
        continue
    else:
        print((nCr(N-K+1,i)*nCr(K-1,i-1))%M)
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
a,b,c,d = map(int,input().split())
lcm = int(c*d/gcd(c,d))
ans = 0
syou = (b-a)//lcm
nokori = a + lcm*syou
for i in range(a,a+lcm):
    if i%c != 0 and i%d != 0:
        ans += 1
ans *= syou
for j in range(nokori,b+1):
    if j%c != 0 and j%d != 0:
        ans += 1
print(ans)

Fixed submission:
from fractions import gcd
a,b,c,d = map(int,input().split())
lcm = c*d//gcd(c,d)
ac = (a-1)//c
ad = (a-1)//d
la = (a-1)//lcm
a_ = a-(ac+ad-la)
bc = b//c
bd = b//d
lb = b//lcm
b_ = b-(bc+bd-lb)
ans = b_ - a_ + 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
Mod = 10**9+7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
b = [1]
b_append = b.append
for i in range(1,N+1):
    if i in a:
        b.append(0)
        continue
    if i == 1:
        b.append(1)
        continue
    b.append(b[i-1]+b[i-2])
    if b[i] >= Mod:
        b[i] %= Mod
print(b[N])

Fixed submission:
Mod = 10**9+7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
b = [1]*(N+1)
for j in a:
    b[j] = 0
for i in range(1,N+1):
    if b[i] == 0:
        continue
    if i == 1:
        b[1] = 1
        continue
    b[i] = b[i-1]+b[i-2]
    if b[i] >= Mod:
        b[i] %= Mod
print(b[N])

Buggy python submission (verdict: Time Limit Exceeded):
Mod = 10**9+7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
b = [1]+[0]*N
for i in range(1,N+1):
    if i in a:
        continue
    if i == 1:
        b[1] += b[0]
        continue
    b[i] += b[i-1]+b[i-2]
    if b[i] > Mod:
        b[i] %= Mod
print(b[N])

Fixed submission:
Mod = 10**9+7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
b = [1]*(N+1)
for j in a:
    b[j] = 0
for i in range(1,N+1):
    if b[i] == 0:
        continue
    if i == 1:
        b[1] = 1
        continue
    b[i] = b[i-1]+b[i-2]
    if b[i] >= Mod:
        b[i] %= Mod
print(b[N])

Buggy python submission (verdict: Time Limit Exceeded):
Mod = 10**9+7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
b = [1]+[0]*N
for i in range(1,N+1):
    if i in a:
        continue
    if i == 1:
        b[1] += b[0]
        continue
    b[i] += b[i-1]+b[i-2]
    if b[i] > Mod:
        b[i] %= Mod
print(b[N])

Fixed submission:
Mod = 10**9+7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
b = [1]*(N+1)
for j in a:
    b[j] = 0
for i in range(1,N+1):
    if b[i] == 0:
        continue
    if i == 1:
        b[1] = 1
        continue
    b[i] = b[i-1]+b[i-2]
    if b[i] >= Mod:
        b[i] %= Mod
print(b[N])

Buggy python submission (verdict: Time Limit Exceeded):
Mod = 10**9+7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
b = [1]+[0]*N
for i in range(1,N+1):
    if i in a:
        continue
    if i == 1:
        b[1] += b[0]
        continue
    b[i] += b[i-1]+b[i-2]
print(b[N]%Mod)

Fixed submission:
Mod = 10**9+7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
b = [1]*(N+1)
for j in a:
    b[j] = 0
for i in range(1,N+1):
    if b[i] == 0:
        continue
    if i == 1:
        b[1] = 1
        continue
    b[i] = b[i-1]+b[i-2]
    if b[i] >= Mod:
        b[i] %= Mod
print(b[N])
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = []
C = []
for _ in range(M):
    L_,R_ = map(int,input().split())
    B.append(L_)
    C.append(R_)
heapq.heapify(A)
for i in range(M):
    for j in range(B[i]):
        tmp = heapq.heappop(A)
        if tmp >= C[i]:
            heapq.heappush(A,tmp)
            break
        heapq.heappush(A,C[i])
print(sum(A))


Fixed submission:
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC = sorted(BC,key = lambda x:x[1],reverse=True)


heapq.heapify(A)
for i in range(M):
    for j in range(BC[i][0]):
        tmp = heapq.heappop(A)
        if tmp >= BC[i][1]:
            heapq.heappush(A,tmp)
            break
        heapq.heappush(A,BC[i][1])
print(sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
""" B = []
C = []
for _ in range(M):
    L_,R_ = map(int,input().split())
    B.append(L_)
    C.append(R_) """

heapq.heapify(A)
for i in range(M):
    for j in range(BC[i][0]):
        tmp = heapq.heappop(A)
        if tmp >= BC[i][1]:
            heapq.heappush(A,tmp)
            break
        heapq.heappush(A,BC[i][1])
print(sum(A))

Fixed submission:
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC = sorted(BC,key = lambda x:x[1],reverse=True)


heapq.heapify(A)
for i in range(M):
    for j in range(BC[i][0]):
        tmp = heapq.heappop(A)
        if tmp >= BC[i][1]:
            heapq.heappush(A,tmp)
            break
        heapq.heappush(A,BC[i][1])
print(sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = []
C = []
for _ in range(M):
    L_,R_ = map(int,input().split())
    B.append(L_)
    C.append(R_)
heapq.heapify(A)
for i in range(M):
    for j in range(B[i]):
        tmp = heapq.heappop(A)
        if tmp >= C[i]:
            heapq.heappush(A,tmp)
            break
        heapq.heappush(A,C[i])
print(sum(A))

Fixed submission:
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC = sorted(BC,key = lambda x:x[1],reverse=True)


heapq.heapify(A)
for i in range(M):
    for j in range(BC[i][0]):
        tmp = heapq.heappop(A)
        if tmp >= BC[i][1]:
            heapq.heappush(A,tmp)
            break
        heapq.heappush(A,BC[i][1])
print(sum(A))
Buggy python submission (verdict: Time Limit Exceeded):
from decimal import Decimal
N,K=map(int,input().split())
ans = 0
for i in range(1,N+1):
    tmp = i
    t_k = 1
    while tmp < K:
        tmp = tmp*2
        t_k = t_k*2
    ans += Decimal(1/t_k)
print(Decimal(ans/N))

Fixed submission:
from decimal import Decimal
N,K=map(int,input().split())
ans = 0
for i in range(1,N+1):
    if i >=K:
        ans+=N-i+1
        break
    tmp = i
    t_k = 1
    while tmp < K:
        tmp = tmp*2
        t_k = t_k*2
    ans += Decimal(1/t_k)
print(Decimal(ans/N))