Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import math
import collections
import fractions
import itertools

def solve():
    n = int(input())
    d = list(map(int, input().split()))
    m = int(input())
    t = list(map(int, input().split()))
    t = collections.Counter(t)
    for i in t:
        if t[i] > d.count(i):
            print("NO")
            break
    else:
        print("YES")
    return 0

if __name__ == "__main__":
    solve()

Fixed submission:
import math
import collections
import fractions
import itertools

def solve():
    n = int(input())
    d = list(map(int, input().split()))
    m = int(input())
    t = list(map(int, input().split()))
    t = collections.Counter(t)
    d = collections.Counter(d)
    for i in t:
        if t[i] > d[i]:
            print("NO")
            break
    else:
        print("YES")
    return 0

if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import math
import collections
import fractions
import itertools

def solve():
    n = int(input())
    d = list(map(int, input().split()))
    m = int(input())
    t = list(map(int, input().split()))
    t = collections.Counter(t)
    for i in t:
        if t[i] > d.count(i):
            print("NO")
            break
    else:
        print("YES")
    return 0

if __name__ == "__main__":
    solve()

Fixed submission:
import math
import collections
import fractions
import itertools

def solve():
    n = int(input())
    d = list(map(int, input().split()))
    m = int(input())
    t = list(map(int, input().split()))
    t = collections.Counter(t)
    d = collections.Counter(d)
    for i in t:
        if t[i] > d[i]:
            print("NO")
            break
    else:
        print("YES")
    return 0

if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
import math
import collections
import fractions
import itertools
import functools
import  operator

def solve():
    n = int(input())
    p = []
    for _ in range(n):
        num = int(input())
        if num in p:
            del p[p.index(num)]
        else:
            p.append(num)
    print(len(p))
    return 0

if __name__ == "__main__":
    solve()

Fixed submission:
import math
import collections
import fractions
import itertools
import functools
import  operator

def solve():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    c = collections.Counter(a)
    cnt = 0
    for i in c:
        if c[i] % 2 == 1:
            cnt += 1
    print(cnt)
    return 0

if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Runtime Error):
import numpy as np
import math
import scipy
import itertools
import fractions
import functools

def gcd(nums):
    return functools.reduce(euclid, nums)

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    g = gcd(a)
    if k <= max(a) and k % g == 0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
    return 0

if __name__ == "__main__":
    solve()



Fixed submission:
import numpy as np
import functools
import math
import scipy
import fractions
import itertools

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    g = a[0]
    for i in range(1, n):
        g = fractions.gcd(g, a[i])
    if k <= max(a) and k % g == 0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
    return 0

if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Runtime Error):
def solve():
  n = int(input())
  a = list(map(int, input().split()))
  g, z = 0, 0
  cut = 1
  for i in range(n-1):
    if a[i+1] > a[i]:
      g += 1
    elif a[i+1] < a[i]:
      z += 1
    if g != 0 and z != 0:
      ans += 1
      g, z = 0, 0
  print(ans)
  return 0
 
if __name__ == "__main__":
  solve()


Fixed submission:
def solve():
  n = int(input())
  a = list(map(int, input().split()))
  g, z = 0, 0
  cut = 1
  for i in range(n-1):
    if a[i+1] > a[i]:
      g += 1
    elif a[i+1] < a[i]:
      z += 1
    if g != 0 and z != 0:
      cut += 1
      g, z = 0, 0
  print(cut)
  return 0
 
if __name__ == "__main__":
  solve()
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = 1
for i in range(1,n+1):
	p *= i
p = p % (10**9+7)
print(p)

Fixed submission:
n = int(input())
p = 1
for i in range(1,n+1):
	p *= i
	p = p % (10**9+7)
print(p)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import functools
import math
import scipy
import fractions
import itertools

def solve():
    x = input()
    le = len(x)
    while True:
        bit = 0
        for i in range(le-1):
            if x[i:i+2] == "ST":
                x = x[0:i]+x[i+2:le]
                bit = 1
                le -= 2
                break
        if bit == 0:
            print(len(x))
            break

    return 0
 
if __name__ == "__main__":
    solve()


Fixed submission:
import numpy as np
import functools
import math
import scipy
import fractions
import itertools
 
def solve():
    x = input()
    a, b = 0, 0
    for i in x:
        if i == "S":
            a += 1
        else:
            if a == 0:
                b += 1
            else:
                a -= 1
    print(a + b)
    return 0

if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
x = input()
le = len(x)
while True:
    bit = 0
    for i in range(le-1):
        if x[i:i+2] == "ST":
            x = x[0:i]+x[i+2:le]
            bit = 1
            break
    if bit == 0:
        print(len(x))
        break

Fixed submission:
import numpy as np
import functools
import math
import scipy
import fractions
import itertools
 
def solve():
    x = input()
    a, b = 0, 0
    for i in x:
        if i == "S":
            a += 1
        else:
            if a == 0:
                b += 1
            else:
                a -= 1
    print(a + b)
    return 0

if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import functools
import math
import scipy
import fractions
import itertools

def solve():
    x = input()
    le = len(x)
    while True:
        bit = 0
        for i in range(le-1):
            if x[i:i+2] == "ST":
                x = x[0:i]+x[i+2:le]
                bit = 1
                break
        if bit == 0:
            print(len(x))
            break

    return 0
 
if __name__ == "__main__":
    solve()


Fixed submission:
import numpy as np
import functools
import math
import scipy
import fractions
import itertools
 
def solve():
    x = input()
    a, b = 0, 0
    for i in x:
        if i == "S":
            a += 1
        else:
            if a == 0:
                b += 1
            else:
                a -= 1
    print(a + b)
    return 0

if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Runtime Error):
import sympy

n = int(input())
cnt = 0
for i in range(1, n):
    # print('i:', i)
    cnt += sympy.divisor_count(n - i)
print(cnt)

Fixed submission:
n = int(input())
cnt = 0
for i in range(1, n):
    cnt += (n - 1) // i
print(cnt)
Buggy python submission (verdict: Runtime Error):
s=sys.stdin
if s[len(s)-1] =="s":
	print(s + "es")
else:
	print(s + "s")

Fixed submission:
s=input()
if s[len(s)-1] =="s":
	print(s + "es")
else:
	print(s + "s")
Buggy python submission (verdict: Runtime Error):
n,q=map(int,input().split())
a=list(map(int,input().split()))
bit=[0]*(2*n+10)
def bit_update(x,v):
    while x<size:
        bit[x]+=v
        x+=(x&-x)
def bit_sum(n):
    s=0
    if n==0:return 0
    x=n
    while x>0:
        s+=bit[x]
        x-=(x&-x)
    return s
for i,j in enumerate(a,1):
    bit_update(i,j)
for i in range(q):
    a,b,c=map(int,input().split())
    if a==0:
        bit_update(b+1,c)
    else:
        print(bit_sum(c)-bit_sum(b))

Fixed submission:
n,q=map(int,input().split())
a=list(map(int,input().split()))
size=2*n+1
bit=[0]*size
def bit_update(x,v):
    while x<size:
        bit[x]+=v
        x+=(x&-x)
def bit_sum(n):
    s=0
    if n==0:return 0
    x=n
    while x>0:
        s+=bit[x]
        x-=(x&-x)
    return s
for i,j in enumerate(a,1):
    bit_update(i,j)
for i in range(q):
    a,b,c=map(int,input().split())
    if a==0:
        bit_update(b+1,c)
    else:
        print(bit_sum(c)-bit_sum(b))

Buggy python submission (verdict: Runtime Error):
n,q=map(int,input().split())
a=list(map(int,input().split()))
size=(1<<18)+1
bit=[0]*size
def bit_update(x,v):
    while x<size:
        bit[x]+=v
        x+=(x&-x)
def bit_sum(n):
    s=0
    if n==0:return 0
    x=n
    while x>0:
        s+=bit[x]
        x-=(x&-x)
    return s
for i,j in enumerate(a,1):
    bit_update(i,j)
for i in range(q):
    a,b,c=map(int,input().split())
    if a==0:
        bit_update(b+1,c)
    else:
        print(bit_sum(c)-bit_sum(b))

Fixed submission:
n,q=map(int,input().split())
a=list(map(int,input().split()))
size=2*n+1
bit=[0]*size
def bit_update(x,v):
    while x<size:
        bit[x]+=v
        x+=(x&-x)
def bit_sum(n):
    s=0
    if n==0:return 0
    x=n
    while x>0:
        s+=bit[x]
        x-=(x&-x)
    return s
for i,j in enumerate(a,1):
    bit_update(i,j)
for i in range(q):
    a,b,c=map(int,input().split())
    if a==0:
        bit_update(b+1,c)
    else:
        print(bit_sum(c)-bit_sum(b))
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())

U=10**6
mod=10**9+7

fact=[1]*(U+1)
fact_inv=[1]*(U+1)

for i in range(1,U+1):
    fact[i]=(fact[i-1]*i)%mod
fact_inv[U]=pow(fact[U],mod-2,mod)

for i in range(U,0,-1):
	fact_inv[i-1]=(fact_inv[i]*i)%mod

def comb(n,k):
    if k<0 or k>n:
        return 0
    x=fact[n]
    x*=fact_inv[k]
    x%=mod
    x*=fact_inv[n-k]
    x%=mod
    return x
def div(a,b):
    return (a*pow(b,mod-2,mod))%mod

def p(n,k):
    return div(fact[n],fact[n-k])
ans=0
for i in range(n+1):
    t=(comb(n,i)*p(m-i,n-i))%mod
    if i%2:ans=(ans-t)%mod
    else:ans=(ans+t)%mod
ans=(ans*p(m,n))%mod
print(ans)

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

U=10**6
mod=10**9+7

fact=[1]*(U+1)
fact_inv=[1]*(U+1)

for i in range(1,U+1):
    fact[i]=(fact[i-1]*i)%mod
fact_inv[U]=pow(fact[U],mod-2,mod)

for i in range(U,0,-1):
	fact_inv[i-1]=(fact_inv[i]*i)%mod

def comb(n,k):
    if k<0 or k>n:
        return 0
    x=fact[n]
    x*=fact_inv[k]
    x%=mod
    x*=fact_inv[n-k]
    x%=mod
    return x
def div(a,b):
    return (a*pow(b,mod-2,mod))%mod

def p(n,k):
    return div(fact[n],fact[n-k])
ans=0
for i in range(n+1):
    t=(comb(n,i)*p(m-i,n-i))%mod
    if i%2:ans=(ans-t)%mod
    else:ans=(ans+t)%mod
ans=(ans*p(m,n))%mod
print(ans)
Buggy python submission (verdict: Runtime Error):
k=int(input())
s=input()

U=10**6+1
mod=10**9+7

fact=[1]*(U+1)
fact_inv=[1]*(U+1)

for i in range(1,U+1):
    fact[i]=(fact[i-1]*i)%mod
fact_inv[U]=pow(fact[U],mod-2,mod)

for i in range(U,0,-1):
	fact_inv[i-1]=(fact_inv[i]*i)%mod

def comb(n,k):
    if k<0 or k>n:
        return 0
    x=fact[n]
    x*=fact_inv[k]
    x%=mod
    x*=fact_inv[n-k]
    x%=mod
    return x
m=len(s)
ans=0
for i in range(k+1):
    ans=(ans+pow(25,i,mod)*comb(m+i-1,m-1)*pow(26,k-i,mod))%mod
print(ans)

Fixed submission:
k=int(input())
s=input()

U=2*10**6+1
mod=10**9+7

fact=[1]*(U+1)
fact_inv=[1]*(U+1)

for i in range(1,U+1):
    fact[i]=(fact[i-1]*i)%mod
fact_inv[U]=pow(fact[U],mod-2,mod)

for i in range(U,0,-1):
	fact_inv[i-1]=(fact_inv[i]*i)%mod

def comb(n,k):
    if k<0 or k>n:
        return 0
    x=fact[n]
    x*=fact_inv[k]
    x%=mod
    x*=fact_inv[n-k]
    x%=mod
    return x
m=len(s)
ans=0
for i in range(k+1):
    ans=(ans+pow(25,i,mod)*comb(m+i-1,m-1)*pow(26,k-i,mod))%mod
print(ans)

Buggy python submission (verdict: Runtime Error):
k=int(input())
s=input()

U=2*10**5
mod=10**9+7

fact=[1]*(U+1)
fact_inv=[1]*(U+1)

for i in range(1,U+1):
    fact[i]=(fact[i-1]*i)%mod
fact_inv[U]=pow(fact[U],mod-2,mod)

for i in range(U,0,-1):
	fact_inv[i-1]=(fact_inv[i]*i)%mod

def comb(n,k):
    if k<0 or k>n:
        return 0
    x=fact[n]
    x*=fact_inv[k]
    x%=mod
    x*=fact_inv[n-k]
    x%=mod
    return x
m=len(s)
ans=0
for i in range(k+1):
    ans=(ans+pow(25,i,mod)*comb(m+i-1,m-1)*pow(26,k-i,mod))%mod
print(ans)

Fixed submission:
k=int(input())
s=input()

U=2*10**6+1
mod=10**9+7

fact=[1]*(U+1)
fact_inv=[1]*(U+1)

for i in range(1,U+1):
    fact[i]=(fact[i-1]*i)%mod
fact_inv[U]=pow(fact[U],mod-2,mod)

for i in range(U,0,-1):
	fact_inv[i-1]=(fact_inv[i]*i)%mod

def comb(n,k):
    if k<0 or k>n:
        return 0
    x=fact[n]
    x*=fact_inv[k]
    x%=mod
    x*=fact_inv[n-k]
    x%=mod
    return x
m=len(s)
ans=0
for i in range(k+1):
    ans=(ans+pow(25,i,mod)*comb(m+i-1,m-1)*pow(26,k-i,mod))%mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k,*a=map(int,open(0).read().split())
if n<=k:
    print(*[n]*n)
    exit()
import copy
for idx in range(k):
    table=[0]*n
    for i in range(n):
        table[max(i-a[i],0)]+=1
        if i+a[i]+1<n:
            table[i+a[i]+1]-=1
    for i in range(1,n):
        table[i]+=table[i-1]
    a=copy.deepcopy(table)
    if a==[n]*n:
        break
print(*a)

Fixed submission:
n,k=[int(j)for j in input().split()]
a=[int(j)for j in input().split()]
if n<=k:
    print(*[n]*n)
    exit()
import copy
for idx in range(k):
    table=[0]*n
    for i in range(n):
        table[max(i-a[i],0)]+=1
        if i+a[i]+1<n:
            table[i+a[i]+1]-=1
    for i in range(1,n):
        table[i]+=table[i-1]
    a=copy.deepcopy(table)
    if a==[n]*n:
        break
print(*a)
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
a=[0]+[int(j) for j in input().split()]
l=[-1]*(n+1)
ll=[]
i=1
idx=0
while True:
    if l[i]==-1:
        l[i]=idx
    else:
        ll.append(i)
        break
    ll.append(i)
    i=a[i]
    idx+=1

p=ll[-1]
nl=ll[p:-1]
print(nl[((k-l[p]+1)%(len(ll)-l[p]-1))-1])


Fixed submission:
n,k=map(int,input().split())
a=[0]+[int(j) for j in input().split()]
l=[-1]*(n+1)
ll=[]
i=1
idx=0
while True:
    if l[i]==-1:
        l[i]=idx
    else:
        ll.append(i)
        break
    ll.append(i)
    i=a[i]
    idx+=1

p=ll[-1]
nl=ll[l[p]:-1]
ml=ll[:l[p]]
n,m=len(nl),len(ml)
if k<m:
    print(ml[k])
elif nl==[]:
    print(p)
    exit()
else:
    print(nl[(k-m)%n])
Buggy python submission (verdict: Runtime Error):
n=int(input())
s=input()
from collections import Counter
l=Counter()
for j,i in enumerate(s):
    if l[i]==0:
        l[i]=[]
    l[i].append(j)
ans=0
import bisect
import itertools
ll=Counter()
ll["R"]=len(l["R"])
ll["G"]=len(l["G"])
ll["B"]=len(l["B"])
for i,j in itertools.combinations(range(n),2):
    if s[i]!=s[j]:
        c="RGB".replace(s[i],"").replace(s[j],"")
        idx=bisect.bisect_left(l[c],j)
        ans+=ll[c]-idx
        if 2*j-i<n:
            if s[2*j-i]==c:
                ans-=1
print(ans)



Fixed submission:
n=int(input())
s=input()
from collections import Counter
l=Counter()
l["R"]=[]
l["G"]=[]
l["B"]=[]
for j,i in enumerate(s):
    if l[i]==0:
        l[i]=[]
    l[i].append(j)
ans=0
import bisect
import itertools
ll=Counter()
ll["R"]=len(l["R"])
ll["G"]=len(l["G"])
ll["B"]=len(l["B"])
for i,j in itertools.combinations(range(n),2):
    if s[i]!=s[j]:
        c="RGB".replace(s[i],"").replace(s[j],"")
        idx=bisect.bisect_left(l[c],j)
        ans+=ll[c]-idx
        if 2*j-i<n:
            if s[2*j-i]==c:
                ans-=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
x,y,a,b,c=[int(j) for j in input().split()]
p=[int(j) for j in input().split()]
q=[int(j) for j in input().split()]
r=[int(j) for j in input().split()]

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
l=p[:x]+q[:y]
l.sort()
ans=sum(l)
for i in l:
    if r!=[]:
        if i<r[0]:
            ans+=r[0]-i
            del r[0]
        else:
            break
    else:
        break
print(ans)







Fixed submission:
x,y,a,b,c=[int(j) for j in input().split()]
p=[int(j) for j in input().split()]
q=[int(j) for j in input().split()]
r=[int(j) for j in input().split()]
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

p=p[:x]
q=q[:y]
l=p+q
l.sort()
ans=sum(l)
for i in l:
    if i<r[0]:
        ans+=r[0]-i
        del r[0]
        if r==[]:
            break
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
x,y,a,b,c=[int(j) for j in input().split()]
p=[int(j) for j in input().split()]
q=[int(j) for j in input().split()]
r=[int(j) for j in input().split()]

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
l=p[:x]+q[:y]
l.sort()
ans=0
for i in l:
    if r!=[]:
        if i<r[0]:
            ans+=r[0]
            del r[0]
        else:
            ans+=i
    else:
        ans+=i
print(ans)

Fixed submission:
x,y,a,b,c=[int(j) for j in input().split()]
p=[int(j) for j in input().split()]
q=[int(j) for j in input().split()]
r=[int(j) for j in input().split()]
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

p=p[:x]
q=q[:y]
l=p+q
l.sort()
ans=sum(l)
for i in l:
    if i<r[0]:
        ans+=r[0]-i
        del r[0]
        if r==[]:
            break
print(ans)
Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split())
print(a*(a-1)//2+b(b-1)//2)

Fixed submission:
a,b=map(int,input().split())
print(a*(a-1)//2+b*(b-1)//2)
Buggy python submission (verdict: Runtime Error):
n=int(input())
s=input()
from collections import Counter
l=Counter()
for i,c in enumerate(list(s)):
    if not l[c]:
        l[c]=[]
    l[c].append(i)

for j in l:
    l[j].append(10**18)
q=int(input())
import bisect
for i in range(q):
    a,b,c=input().split()
    if a=="1":
        b=int(b)-1
        idx=bisect.bisect_left(l[s[b]],b)
        del l[s[b]][idx]
        if not l[c]:
            l[c]=[]
        idx=bisect.bisect_left(l[c],b)
        l[c].insert(idx,b)
        l[c].append(10**18)
    else:
        ans=0
        left,right=int(b)-1,int(c)-1
        for j in l:
            p=bisect.bisect_left(l[j],left)
            q=bisect.bisect_left(l[j],right)
            if p!=q:
                ans+=1
            else:
                if l[j]!=[]:
                    if left<=l[j][p]<=right:
                        ans+=1
        print(ans)

Fixed submission:
n=int(input())+1
data=[0]*n*2
def update(i,x):
    i+=n
    data[i]=x
    i//=2
    while i:
        data[i]=data[i*2]|data[i*2+1]
        i//=2
def query(l,r):
    l+=n
    r+=n
    s=0
    while l<r:
        if l&1:
            s|=data[l]
            l+=1
        if r&1:
            r-=1
            s|=data[r]
        l//=2
        r//=2
    return sum(map(int,bin(s)[2:]))
s=input()
for i,c in enumerate(s,n):
    data[i]=1<<(ord(c)-97)
for i in range(n-1,0,-1):
    data[i]=data[2*i]|data[2*i+1]
for _ in range(int(input())):
    q,a,b=input().split()
    if q=="2":
        print(query(int(a)-1,int(b)))
    else:
        update(int(a)-1,1<<(ord(b)-97))

Buggy python submission (verdict: Runtime Error):
n=int(input())
s=input()
from collections import Counter
l=Counter()
for i,c in enumerate(list(s)):
    if not l[c]:
        l[c]=[]
    l[c].append(i)

for j in l:
    l[j].append(10**18)
q=int(input())
import bisect
for i in range(q):
    a,b,c=input().split()
    if a=="1":
        b=int(b)-1
        idx=bisect.bisect_left(l[s[b]],b)
        del l[s[b]][idx]
        if not l[c]:
            l[c]=[]
        idx=bisect.bisect_left(l[c],b)
        l[c].insert(idx,b)
        l[c].append(10**18)
    else:
        ans=0
        left,right=int(b)-1,int(c)-1
        for j in l:
            p=bisect.bisect_left(l[j],left)
            q=bisect.bisect_left(l[j],right)
            if p!=q:
                ans+=1
            else:
                if l[j]!=[]:
                    if left<=l[j][p]<=right:
                        ans+=1
        print(ans)

Fixed submission:
n=int(input())+1
data=[0]*n*2
def update(i,x):
    i+=n
    data[i]=x
    i//=2
    while i:
        data[i]=data[i*2]|data[i*2+1]
        i//=2
def query(l,r):
    l+=n
    r+=n
    s=0
    while l<r:
        if l&1:
            s|=data[l]
            l+=1
        if r&1:
            r-=1
            s|=data[r]
        l//=2
        r//=2
    return sum(map(int,bin(s)[2:]))
s=input()
for i,c in enumerate(s,n):
    data[i]=1<<(ord(c)-97)
for i in range(n-1,0,-1):
    data[i]=data[2*i]|data[2*i+1]
for _ in range(int(input())):
    q,a,b=input().split()
    if q=="2":
        print(query(int(a)-1,int(b)))
    else:
        update(int(a)-1,1<<(ord(b)-97))
Buggy python submission (verdict: Time Limit Exceeded):
n,k=[int(j) for j in input().split()]
a=[int(j) for j in input().split()]
a.sort()
lm=[]
lp=[]
lz=[]
for i in a:
    if i<0:
        lm.append(i)
    elif i==0:
        lz.append(i)
    else:
        lp.append(i)
np=len(lp)
nm=len(lm)
nz=len(lz)
import bisect
import math
def f(x):
    c=0
    if x>=0:
        c+=nz*n
    for i in lp:
        c+=bisect.bisect_right(a,x//i)
    for i in lm:
        c+=n-bisect.bisect_right(a,(-x-1)//(-i))
    for i in a:
        if i**2<=x:
            c-=1
    return c//2

left=-10**20
right=10**20
while right-left>1:
    mid=(left+right)//2
    if f(mid)>=k:
        right=mid
    else:
        left=mid
print(right)





Fixed submission:
n,k=[int(j) for j in input().split()]
from numpy import *
a=array([int(j) for j in input().split()])
a.sort()
lm=a[a<0]
lp=a[a>0]
lz=a[a==0]
np=len(lp)
nm=len(lm)
nz=len(lz)

import bisect
import math
def f(x):
    c=0
    if x>=0:
        c+=nz*n
    c+=searchsorted(a,x//lp,side="right").sum()
    c+=(n-searchsorted(a,(-x-1)//(-lm),side="right")).sum()
    c-=count_nonzero(a*a<=x)
    return c//2

left=-10**20
right=10**20
while right-left>1:
    mid=(left+right)//2
    if f(mid)>=k:
        right=mid
    else:
        left=mid
print(right)
Buggy python submission (verdict: Time Limit Exceeded):
h,n=[int(j) for j in input().split()]
ab=[[int(j) for j in input().split()] for i in range(n)]
dp=[10**18]*(h+1)
dp[0]=0
ans=10**18
for a,b in ab:
    for i in range(h+1):
        if dp[i]!=10**18:
            if i+a<h:
                if dp[i]+b<dp[i+a]:
                    dp[i+a]=dp[i]+b
            else:
                if dp[i]+b<ans:
                    ans=dp[i]+b

print(ans)







Fixed submission:
h,n=[int(j) for j in input().split()]
ab=[[int(j) for j in input().split()] for i in range(n)]
dp=[10**18]*(h+1)
dp[0]=0
ans=10**18
for a,b in ab:
    for i in range(h+1):
        if dp[i]!=10**18:
            if i+a<h:
                if dp[i]+b<dp[i+a]:
                    dp[i+a]=dp[i]+b
            else:
                if dp[i]+b<ans:
                    ans=dp[i]+b

print(ans)