Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split(' ')))
a.sort()
if n % 2 == 0:
    a_ = [[a[i],a[i+1]] for i in range(0,n,2)]
    for i,j in enumerate(a_):
        j_ = j[0]
        k_ = j[1]
        if  (i*2+1) != j_ or (i*2+1) != k_:
            print(0)
            break
    else:
        r = (2 ** (n/2))%((10**9)+7)
        print(int(r))
else:
    if a[0] == 0:
        a_ = [[a[i],a[i+1]] for i in range(1,n,2)]
        for i,j in enumerate(a_,start=1):
            j_ = j[0]
            k_ = j[1]
            if i*2 != j_ or i*2 != k_:
                print(0)
                break
        else:
            r = (2**((n-1)/2))%((10**9)+7)
            print(int(r))
    else:
        print(0)

Fixed submission:
n = int(input())
a = list(map(int, input().split(' ')))
a.sort()
if n % 2 == 0:
    a_ = [[a[i],a[i+1]] for i in range(0,n,2)]
    for i,j in enumerate(a_):
        j_ = j[0]
        k_ = j[1]
        if  (i*2+1) != j_ or (i*2+1) != k_:
            print(0)
            break
    else:
        r = (2 ** (n//2))%((10**9)+7)
        print(int(r))
else:
    if a[0] == 0:
        a_ = [[a[i],a[i+1]] for i in range(1,n,2)]
        for i,j in enumerate(a_,start=1):
            j_ = j[0]
            k_ = j[1]
            if i*2 != j_ or i*2 != k_:
                print(0)
                break
        else:
            r = (2**((n-1)//2))%((10**9)+7)
            print(int(r))
    else:
        print(0)

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split(' ')))
a.sort()
r = (10**9)+7
if n % 2 == 0:
    for i in range(0,n,2):
        if a[i] != a[i+1]:
            print(0)
            break
    else:
        r = (2 ** (n/2))%((10**9)+7)
        print(int(r))
else:
    for i in range(1,n,2):
        if a[i] != a[i+1]:
            print(0)
            break
    else:
        r = (2**((n-1)/2))%((10**9)+7)
        print(int(r))

Fixed submission:
n = int(input())
a = list(map(int, input().split(' ')))
a.sort()
if n % 2 == 0:
    a_ = [[a[i],a[i+1]] for i in range(0,n,2)]
    for i,j in enumerate(a_):
        j_ = j[0]
        k_ = j[1]
        if  (i*2+1) != j_ or (i*2+1) != k_:
            print(0)
            break
    else:
        r = (2 ** (n//2))%((10**9)+7)
        print(int(r))
else:
    if a[0] == 0:
        a_ = [[a[i],a[i+1]] for i in range(1,n,2)]
        for i,j in enumerate(a_,start=1):
            j_ = j[0]
            k_ = j[1]
            if i*2 != j_ or i*2 != k_:
                print(0)
                break
        else:
            r = (2**((n-1)//2))%((10**9)+7)
            print(int(r))
    else:
        print(0)
Buggy python submission (verdict: Runtime Error):
s = input().split(' ')[1]
print(f'A{s[0].upper()}C')

Fixed submission:
s = input().split(' ')[1]
print('A{}C'.format(s[0].upper()))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
re_t = 0
re_a = 0
for i in range(n):
    t, a = map(int, input().split(' '))
    n = 1
    while n*t < re_t or n*a < re_a:
        n += 1
    re_t = n * t
    re_a = n * a
print(re_t + re_a)

Fixed submission:
import math
n = int(input())
a,b = 1,1
for i in range(n):
    x,y = map(int, input().split(' '))
    tmp = max(-(-a//x), -(-b//y))
    a = x * tmp
    b = y * tmp
print(a+b)
Buggy python submission (verdict: Runtime Error):
import os

N, K = map(int, input().split(' '))
d_list = input().split(' ')
for i in range(10):
    for j in range(10):
        for k in range(10):
            for l in range(10):
                number =  i * 1000 + j * 100 + k * 10 + l
                result = set(list(str(number)))
                if set(d_list) & result != set():
                    continue
                if number >= N:
                    print(number)
                    os._exit(1)





Fixed submission:
N, K = map(int, input().split(' '))
d_list = input().split(' ')
for h in range(10):
    for i in range(10):
        for j in range(10):
            for k in range(10):
                for l in range(10):
                    number = h * 10000 + i * 1000 + j * 100 + k * 10 + l
                    result = set(list(str(number)))
                    if set(d_list) & result != set():
                        continue
                    if number >= N:
                        print(number)
                        break
                else:
                    continue
                break
            else:
                continue
            break
        else:
            continue
        break
    else:
        continue
    break
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))
ans = 1
ju = 0
for i in range(n):
    ans = ans*a[i]


if ans<=10**18:
    print(ans)
else:
    print(-1)


Fixed submission:
n = int(input())
a = list(map(int,input().split()))
ans = 1
ju = 0
j = 0
if 0 in a:
    ju=1

for i in range(n):
    ans = ans*a[i]
    if ans>10**18:
        j = 1
        break

if ju==1:
    print(0)
elif j==1:
    print(-1)
else:
    print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))
cir = 0
sum = 0
hantei=0

lis = [1]
for i in range(n):
    cc = lis[-1] - a[i]
    cc *=2
    if cc<=0:
        hantei=1
    lis.append(cc)

p#rint(lis)



for i in range(n+1):
    tmp = a[-1-i]+cir
    sum += tmp
    #print(tmp,cir)
    if i==n:
        break
    if tmp <= lis[-1-i] and tmp+a[-2-i]>lis[-2-i]:
        if tmp%2==0:
            cir = tmp//2
        else:
            cir = tmp//2+1
    else:
        cir = tmp
if hantei==1:
    print(-1)
else:
    print(-1)


Fixed submission:
n = int(input())
a = list(map(int,input().split()))
cir = 1
bsum = 1
hantei=0
asum = [0 for i in range(n+1)]
asum[0] = sum(a)
for i in range(1,n+1):
    asum[i] = asum[i-1]-a[i]
#print(asum)
swi = 0
for i in range(n):
    if swi == 1:
        #print(cir,a[i])
        cir = cir-a[i]
    if swi==0:
        if (cir-a[i])*2 < asum[i]:
            cir = (cir-a[i])*2
        else:
            cir = asum[i]
            swi = 1

    bsum += cir
    if cir<=0:
        hantei=1
        break


#print(cir,a[-1])


if hantei==1 or cir!=a[-1]:
    print(-1)
else:
    print(bsum)
Buggy python submission (verdict: Runtime Error):
S = input()
n = len(S)
dp = [0 for _ in range(n+1)]
count = [0 for _ in range(2019)]
count[0] = 1
for i in range(1,n+1):
    dp[i] = (dp[i-1]+int(S[n-i])*10**(i-1)) % 2019
    count[dp[i]] += 1

for i in range(2019):
    count[i] = count[i]*(count[i]-1)/2

print(int(sum(count)))

Fixed submission:
S,W = map(int, input().split())
if S<=W:
    print("unsafe")
else:
    print("safe")
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
n = len(S)
dp = [0 for _ in range(n+1)]
count = [0 for _ in range(2019)]
count[0] = 1
for i in range(1,n+1):
    dp[i] = (dp[i-1]+int(S[n-i])*10**(i-1)) % 2019
    count[dp[i]] += 1

for i in range(2019):
    count[i] = count[i]*(count[i]-1)/2

print(int(sum(count)))

Fixed submission:
S = input()
n = len(S)
dp = [0 for _ in range(n+1)]
count = [0 for _ in range(2019)]
count[0] = 1
p=1
for i in range(1,n+1):
    dp[i] = (dp[i-1]+int(S[n-i])*p) % 2019
    p = p*10%2019
    count[dp[i]] += 1

for i in range(2019):
    count[i] = count[i]*(count[i]-1)/2

print(int(sum(count)))
Buggy python submission (verdict: Runtime Error):

from collections import deque


N, M, K = map(int, input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int, input().split())) for _ in range(K)]
#sys.setrecursionlimit(2*N)
#print(friend)
#print(block)
graph = [[] for _ in range(N)]
bgraph = [[] for _ in range(N)]
cnt = []
for i in range(M):
    ii, jj = friend[i]
    graph[ii-1].append(jj-1)
    graph[jj-1].append(ii-1)

for i in range(K):
    ii, jj = block[i]
    bgraph[ii-1].append(jj-1)
    bgraph[jj-1].append(ii-1)

#print(graph)
#print(bgraph)

seen = [False for _ in range(N)]

def dfs(i):
    #if i not in bgraph[j]:
    #    seen[i]= True
    #else:
    #    seen[i]="block"
    #if graph[i]:
    #    for nec in graph[i]:
    #        if seen[nec] == False:
    #            dfs(nec,j)
    seen[i] = True
    que = deque([i])
    while que:

        neci = que.pop()
        for nec in graph[neci]:
            if seen[nec]== False:
                if nec not in bgraph[i]:
                    seen[nec]=True
                else:
                    seen[nec]="block"
                que.append(nec)

for i_n in range(N):
    seen = [False for _ in range(N)]
    dfs(i_n)
    #print(seen)
    cnt.append(seen.count(True) - 1 - len(graph[i_n]))

print(*cnt)


Fixed submission:
N = int(input())

if N%2==0:
    print(int(N/2))
else:
    print(int((N+1)/2))
Buggy python submission (verdict: Time Limit Exceeded):
n,a,b=map(int,input().split())

di = 10**9+7

def pow_k(x,nt):
    if nt==0:
        return 1
    K=1
    while nt>=2:
        if nt%2!=0:
            K=(K*x)%di
        x=(x*x)%di
        nt//=2
    return (K*x)%di

ans = pow_k(2,n)-1

mi = max(a,b)

lis = [n-i for i in range(mi)]
lisr = [i+1 for i in range(mi)]


for i in range(1,mi):
    lis[i] = (lis[i-1]*lis[i])%di
    lisr[i] = pow_k(lisr[i],di-2)

for i in range(1,mi):
    lisr[i] = (lisr[i-1]*lisr[i])%di


hik =(lis[a-1]*lisr[a-1])%di
hik2 = (lis[b-1]*lisr[b-1])%di


ans = (ans - hik - hik2)%di

#print((lis[3-1]*lisr[3-1])%di)

print(ans)


Fixed submission:
n,a,b=map(int,input().split())

di = 10**9+7

def pow_k(x,nt):
    if nt==0:
        return 1
    K=1
    while nt>=2:
        if nt%2!=0:
            K=(K*x)%di
        x=(x*x)%di
        nt//=2
    return (K*x)%di

ans = pow_k(2,n)-1

mi = max(a,b)

lis = [n-i for i in range(mi)]
lisr = [i+1 for i in range(mi)]


for i in range(1,mi):
    lis[i] = (lis[i-1]*lis[i])%di
    lisr[i] = pow_k(lisr[i],di-2)

for i in range(1,mi):
    lisr[i] = (lisr[i-1]*lisr[i])%di


hik =(lis[a-1]*lisr[a-1])%di
hik2 = (lis[b-1]*lisr[b-1])%di


ans = (ans - hik - hik2)%di

#print((lis[3-1]*lisr[3-1])%di)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N, K = map(int, input().split())
p_list = list(map(int, input().split()))
expect_list = np.array(p_list)
expect_list = (expect_list + 1)/2
sum_list = []
#print(expect_list)

for i in range(N-K+1):
    sum=0
    for j in range(K):
        sum += expect_list[i+j]

    sum_list.append(sum)

print(max(sum_list))

Fixed submission:
import numpy as np
N, K = map(int, input().split())
p_list = list(map(int, input().split()))
expect_list = np.array(p_list)
expect_list = (expect_list + 1)/2
sum_list = []
#print(expect_list)
sum=0
for i in range(K):
    sum += expect_list[i]

sum_list.append(sum)

for i in range(1,N-K+1):
    sum -= expect_list[i-1]
    sum += expect_list[i+K-1]
    sum_list.append(sum)

print(max(sum_list))
Buggy python submission (verdict: Runtime Error):
n=int(input())
k=int(input())

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r<0:return 0
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

if k==1:
    syo = int(str(n)[0])
    ans = 9*(len(str(n))-1)+syo
if k==2:
    fir = int(str(n)[0])
    sec = int(str(n)[1])
    ans = 9**2*cmb(len(str(n))-1,2)
    ans+=(fir-1)*9+sec
    ans += 9*cmb(len(str(n))-2,1)*fir

if k==3:
    fir = int(str(n)[0])
    sec = int(str(n)[1])
    thi = int(str(n)[2])
    ans = 9**3*cmb(len(str(n))-1,3)
    ans += (fir-1)*81+(sec-1)*9+thi
    ans += 9*9*cmb(len(str(n))-2,2)*fir
    ans += ((fir-1)*9+sec)*9*cmb(len(str(n))-3,1)

print(ans)


Fixed submission:
n=int(input())
k=int(input())
dp0=[[0 for i in range(4)] for i in range(len(str(n))+1)]
dp1=[[0 for i in range(4)] for i in range(len(str(n))+1)]

for i in range(1,len(str(n))+1):
    dp0[i][0]=1
dp0[1][1]=int(str(n)[0])-1
dp1[1][1]=1

for N in range(2,len(str(n))+1):
    for num in range(10):
        for K in range(1,4):
            if num!=0:
                if num<int(str(n)[N-1]):
                    dp0[N][K]+=dp0[N-1][K-1]+dp1[N-1][K-1]
                elif num==int(str(n)[N-1]):
                    dp0[N][K]+=dp0[N-1][K-1]
                    dp1[N][K]+=dp1[N-1][K-1]
                else:
                    dp0[N][K]+=dp0[N-1][K-1]
            else:
                if int(str(n)[N-1])>0:
                    dp0[N][K]+=dp0[N-1][K]+dp1[N-1][K]
                elif int(str(n)[N-1])==0:
                    dp1[N][K]+=dp1[N-1][K]
                    dp0[N][K]+=dp0[N-1][K]
#print(dp0)
#print(dp1)
print(dp1[-1][k]+dp0[-1][k])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
X = [0]*N
L = [0]*N

for i in range(N):
    X[i], L[i] = map(int, input().split())

start = -1000000000
seen = [False]*N

while True:
    min = 2000000000
    minin = None
    for i in range(N):
        if X[i]-L[i]< start or seen[i]==True:continue
        if X[i]+L[i]<min:
            min = X[i]+L[i]
            minin = i

    if minin == None:
        break
    seen[minin] = True
    start = min

print(seen.count(True))


Fixed submission:
from collections import deque
N = int(input())
X = [0]*N
L = [0]*N
lis = deque()
for i in range(N):
    X[i], L[i] = map(int, input().split())
    lis.append([i,X[i]-L[i], X[i]+L[i]])

lis = sorted(lis, key=lambda x:x[2])
lis = deque(lis)

end = lis[0][2]
start = lis[0][1]
lis.popleft()
cnt = 1
while lis:
    x, y, z = lis.popleft()
    if y < end:
        continue
    elif y >= end:
        start = y
        end = z
        cnt += 1

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a = list(map(int,input().split()))
di=10**9+7
a.sort()

maxl = a[k-1:]
minl = a[:n-k+1]

kai = [i for i in range(n+1)]
gya = [i for i in range(n+1)]
kai[0]=1
gya[0]=1
for i in range(1,n+1):
    kai[i]=kai[i-1]*kai[i]

for i in range(n+1):
    gya[i]=pow(gya[i],di-2,di)

for i in range(1,n+1):
    gya[i]*=gya[i-1]

for i in range(n-k+1):
    tmp=(kai[k-1+i]*gya[k-1]*gya[i])%di
    maxl[i]=(maxl[i]*tmp)%di

for i in range(n-k+1):
    tmp = (kai[n-1-i]*gya[k-1]*gya[n-i-k])%di
    minl[i] = (minl[i]*tmp)%di

su=0
for i in range(n-k+1):
    su = (su+maxl[i])%di
    su = (su-minl[i])%di
print(su)


Fixed submission:
n,k=map(int,input().split())
a = list(map(int,input().split()))
di=10**9+7
a.sort()

maxl = a[k-1:]
minl = a[:n-k+1]

kai = [i for i in range(n+1)]
gya = [i for i in range(n+1)]
kai[0]=1
gya[0]=1
for i in range(1,n+1):
    kai[i]=(kai[i-1]*kai[i])%di

for i in range(n+1):
    gya[i]=pow(gya[i],di-2,di)

for i in range(1,n+1):
    gya[i]=(gya[i]*gya[i-1])%di

for i in range(n-k+1):
    tmp=(((kai[k-1+i]*gya[k-1])%di)*gya[i])%di
    maxl[i]=(maxl[i]*tmp)%di

for i in range(n-k+1):
    tmp = (((kai[n-1-i]*gya[k-1])%di)*gya[n-i-k])%di
    minl[i] = (minl[i]*tmp)%di

su=0
for i in range(n-k+1):
    su = (su+maxl[i])%di
    su = (su-minl[i])%di
print(su)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10000000)
import math
import bisect
def input():
    return sys.stdin.readline()[:-1]

n,u,v = map(int,input().split())
u-=1
v-=1
g = [[]for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
seen = [-1 for i in range(n)]
taka = []
aok = []
def dfs(s,lis):
    nec = g[s]
    if len(nec)==1:
        lis.append(s)
    for i in nec:
        if seen[i]!=-1:
            continue
        seen[i] = seen[s]+1
        dfs(i,lis)

seen[u]=0
dfs(u,taka)
takadist = [i for i in seen]
seen = [-1 for i in range(n)]
seen[v]=0
dfs(v,aok)
ans = 0
for i in aok:
    if takadist[i]<seen[i]:
        ans = max(ans,seen[i])
if g[u]==[v]:
    print(0)
else:
    print(ans-1)


Fixed submission:
import sys
sys.setrecursionlimit(10000000)
import math
import bisect
def input():
    return sys.stdin.readline()[:-1]

n,u,v = map(int,input().split())
u-=1
v-=1
g = [[]for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
seen = [-1 for i in range(n)]
taka = []
aok = []
def dfs(s,lis):
    nec = g[s]
    if len(nec)==1:
        lis.append(s)
    for i in nec:
        if seen[i]!=-1:
            continue
        seen[i] = seen[s]+1
        dfs(i,lis)

seen[u]=0
dfs(u,taka)
takadist = [i for i in seen]
seen = [-1 for i in range(n)]
seen[v]=0
dfs(v,aok)
ans = 0
for i in aok:
    if takadist[i]<seen[i]:
        ans = max(ans,seen[i])
if g[u]==[v]:
    print(0)
else:
    print(ans-1)

Buggy python submission (verdict: Runtime Error):
import sys
import math
import bisect
def input():
    return sys.stdin.readline()[:-1]

n,u,v = map(int,input().split())
u-=1
v-=1
g = [[]for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
seen = [-1 for i in range(n)]
taka = []
aok = []
def dfs(s,lis):
    nec = g[s]
    if len(nec)==1:
        lis.append(s)
    for i in nec:
        if seen[i]!=-1:
            continue
        seen[i] = seen[s]+1
        dfs(i,lis)

seen[u]=0
dfs(u,taka)
takadist = [i for i in seen]
seen = [-1 for i in range(n)]
seen[v]=0
dfs(v,aok)
ans = 0
for i in aok:
    if takadist[i]<seen[i]:
        ans = max(ans,seen[i])
if g[u]==[v]:
    print(0)
else:
    print(ans-1)


Fixed submission:
import sys
sys.setrecursionlimit(10000000)
import math
import bisect
def input():
    return sys.stdin.readline()[:-1]

n,u,v = map(int,input().split())
u-=1
v-=1
g = [[]for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
seen = [-1 for i in range(n)]
taka = []
aok = []
def dfs(s,lis):
    nec = g[s]
    if len(nec)==1:
        lis.append(s)
    for i in nec:
        if seen[i]!=-1:
            continue
        seen[i] = seen[s]+1
        dfs(i,lis)

seen[u]=0
dfs(u,taka)
takadist = [i for i in seen]
seen = [-1 for i in range(n)]
seen[v]=0
dfs(v,aok)
ans = 0
for i in aok:
    if takadist[i]<seen[i]:
        ans = max(ans,seen[i])
if g[u]==[v]:
    print(0)
else:
    print(ans-1)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(20000)
N=int(input())
g = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    g[a-1].append([b-1,i])
    g[b-1].append([a-1,i])

ans=[0 for i in range(N-1)]

def dfs(i,j,col):
    k=1
    for nec in g[i]:
        if nec[0]==j:continue
        if k==col:k+=1
        ans[nec[1]]=k
        dfs(nec[0],i,k)
        k+=1

dfs(0,-1,-1)
print(max(ans))
for i in range(N-1):
    print(ans[i])


Fixed submission:
import sys
sys.setrecursionlimit(1000000)
N=int(input())
g = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    g[a-1].append([b-1,i])
    g[b-1].append([a-1,i])

ans=[0 for i in range(N-1)]

def dfs(i,j,col):
    k=1
    for nec in g[i]:
        if nec[0]==j:continue
        if k==col:k+=1
        ans[nec[1]]=k
        dfs(nec[0],i,k)
        k+=1

dfs(0,-1,-1)
print(max(ans))
for i in range(N-1):
    print(ans[i])

Buggy python submission (verdict: Runtime Error):
N=int(input())
g = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    g[a-1].append([b-1,i])
    g[b-1].append([a-1,i])

ans=[0 for i in range(N-1)]

def dfs(i,j,col):
    k=1
    for nec in g[i]:
        if nec[0]==j:continue
        if k==col:k+=1
        ans[nec[1]]=k
        dfs(nec[0],i,k)
        k+=1

dfs(0,-1,-1)
print(max(ans))
for i in range(N-1):
    print(ans[i])


Fixed submission:
import sys
sys.setrecursionlimit(1000000)
N=int(input())
g = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    g[a-1].append([b-1,i])
    g[b-1].append([a-1,i])

ans=[0 for i in range(N-1)]

def dfs(i,j,col):
    k=1
    for nec in g[i]:
        if nec[0]==j:continue
        if k==col:k+=1
        ans[nec[1]]=k
        dfs(nec[0],i,k)
        k+=1

dfs(0,-1,-1)
print(max(ans))
for i in range(N-1):
    print(ans[i])
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()))
l = -1
r = 10**13

a.sort(reverse=True)
f.sort()

while l+1<r:
    #print()
    now = (l+r)//2
    s=0
    for i in range(n):
        s += max(0,a[i]-now//f[i])
    if s<=k:
        r=now
    else:
        l=now

print(r)


Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
l = -1
r = 10**12

a.sort(reverse=True)
f.sort()

while l+1<r:
    #print()
    now = (l+r)//2
    s=0
    for i in range(n):
        s += max(0,a[i]-now//f[i])
    if s<=k:
        r=now
    else:
        l=now

print(r)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

import bisect

lis = []
for i in range(n):
    ind = bisect.bisect_left(lis,a[i])
    if ind==0:
        bisect.insort_left(lis,a[i])
    else:
        lis[ind-1] = a[i]

print(len(lis))


Fixed submission:
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

import bisect
from collections import deque

lis = deque()
for i in range(n):
    ind = bisect.bisect_left(lis,a[i])
    if ind==0:
        lis.appendleft(a[i])
    else:
        lis[ind-1] = a[i]

print(len(lis))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)

h,w=map(int,input().split())
maze = [[]for _ in range(h)]
for i in range(h):
    maze[i].extend(list(input()))

R=[[0 for i in range(w)]for i in range(h)]
L=[[0 for i in range(w)]for i in range(h)]
U=[[0 for i in range(w)]for i in range(h)]
B=[[0 for i in range(w)]for i in range(h)]

for i in range(h):
    for j in range(w):
        if maze[i][j]=="#":continue
        if j==0: L[i][j]=1
        else: L[i][j]=L[i][j-1]+1
        if i==0: U[i][j]=1
        else: U[i][j]=U[i-1][j]+1

for i in range(h):
    for j in range(w):
        if maze[h-1-i][w-1-j]=="#":continue
        if i==0:B[h-1-i][w-1-j]=1
        else: B[h-1-i][w-1-j] = B[h-i][w-1-j]+1
        if j==0:R[h-1-i][w-1-j]=1
        else: R[h-1-i][w-1-j] = R[h-1-i][w-j]+1


#print(*B,sep="\n")
#print("\n")
#print(*U,sep="\n")


ma=0
for i in range(h):
    for j in range(w):
        if maze[i][j]=="#":continue
        ma=max(ma,R[i][j]+L[i][j]+U[i][j]+B[i][j]-3)

print(ma)


Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)

h,w=map(int,input().split())
maze = [[]for _ in range(h)]
for i in range(h):
    maze[i].extend(list(input()))

R=[[0 for i in range(w)]for i in range(h)]
L=[[0 for i in range(w)]for i in range(h)]
U=[[0 for i in range(w)]for i in range(h)]
B=[[0 for i in range(w)]for i in range(h)]

for i in range(h):
    for j in range(w):
        if maze[i][j]=="#":continue
        if j==0: L[i][j]=1
        else: L[i][j]=L[i][j-1]+1
        if i==0: U[i][j]=1
        else: U[i][j]=U[i-1][j]+1

for i in range(h):
    for j in range(w):
        if maze[h-1-i][w-1-j]=="#":continue
        if i==0:B[h-1-i][w-1-j]=1
        else: B[h-1-i][w-1-j] = B[h-i][w-1-j]+1
        if j==0:R[h-1-i][w-1-j]=1
        else: R[h-1-i][w-1-j] = R[h-1-i][w-j]+1


#print(*B,sep="\n")
#print("\n")
#print(*U,sep="\n")


ma=0
for i in range(h):
    for j in range(w):
        if maze[i][j]=="#":continue
        ma=max(ma,R[i][j]+L[i][j]+U[i][j]+B[i][j]-3)

print(ma)