Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import defaultdict
def main():
    def popcount(n):
        i = 2
        P = [0, 1]
        while i - 1 <= n:
            P += list(map(lambda x: x + 1, P))
            i *= 2
        return P
    def f(n):
        if n == 0:
            return 0
        if d[n] != 0:
            return d[n]
        d[n] = f(n % P[n]) + 1
    def rev(i):
        if X[i] == '0':
            b = m + j
            print(d[b % (c + 1)] + 1 if b != 0 else 0)
        else:
            b = m - j
            print(d[b % (c - 1)] + 1 if b != 0 else 0)

    n = int(input())
    X = list(input())
    d = defaultdict(int)
    P = popcount(n)
    for i in range(1, n):
        f(i)
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    j = 1 << n - 1
    for i in range(n):
        rev(i)
        j = j >> 1

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    def f(n):
        if n == 0: return 0
        return f(n % bin(n).count('1')) + 1
    n = int(input())
    X = list(input())
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    mp, mm = m % (c + 1), m % (c - 1) if c - 1 != 0 else 0
    jp, jm = 1, 1
    ans = [0] * n
    for i in range(n - 1, -1, -1):
        if X[i] == '0':
            mod = c + 1
            ans[i] = f((mp + jp) % mod) + 1
        else:
            ans[i] = f((mm - jm + mod) % mod) + 1 if (mod := c - 1) != 0 else 0
        jp, jm = (jp << 1) % (c + 1), (jm << 1) % (c - 1) if c - 1 != 0 else 0
    [print(a) for a in ans]
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys,heapq

input=sys.stdin.readline

N=int(input())
node=[]
for i in range(0,N-1):
    for j in range(i+1,N):
        node.append((i,j))

_to={key:set([]) for key in node}
_from={key:set([]) for key in node}


for i in range(0,N):
    A=list(map(int,input().split()))
    for j in range(0,N-2):
        if A[j]-1>i:
            if A[j+1]-1>i:
                _to[(i,A[j]-1)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((i,A[j]-1))
            else:
                _to[(i,A[j]-1)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((i,A[j]-1))
        else:
            if A[j+1]-1>i:
                _to[(A[j]-1,i)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((A[j]-1,i))
            else:
                _to[(A[j]-1,i)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((A[j]-1,i))

day=0
conduct=set([])
subconduct=set([])
q=set([])
for key in node:
    if not _from[key]:
        conduct.add(key)
        q.add(key)
sub=set([])
while q:
    while q:
        x=q.pop()
        for n in _to[x]:
            if conduct>=_from[n]:
                subconduct.add(n)
                sub.add(n)
        if not q:
            q=sub
            sub=set([])
            for i in subconduct:
                conduct.add(i)
            subconduct=set([])
            day+=1
            break

if conduct==set(node):
    print(day)
else:
    print(-1)


### FIXED CODE ###

N=int(input())
A=[[] for i in range(0,N)]
nodes=[]
for i in range(0,N-1):
    for j in range(i+1,N):
        nodes.append((i,j))

order={i:[0 for j in range(0,N)] for i in range(0,N)}
for i in range(0,N):
    A[i]=list(map(int,input().split()))
    for j in range(0,N-1):
        order[i][A[i][j]-1]=j
        #i番目の人がj番目の人と戦うのが何番目か


q=set([])
for battle in nodes:
    i,j=battle
    if order[i][j]==0 and order[j][i]==0:
        q.add(battle)

flag=[0 for i in range(0,N)]

day=0
sub=set([])
while q:
    while q:
        i,j=q.pop()
        flag[i]+=1
        flag[j]+=1
        if flag[i]!=N-1:
            s=A[i][order[i][j]+1]-1
            if flag[s]>=order[s][i]:
                sub.add((i,s))
        if flag[j]!=N-1:
            t=A[j][order[j][i]+1]-1
            if flag[t]>=order[t][j]:
                sub.add((j,t))

        if not q:
            day+=1
            q=sub
            sub=set([])
            break

able=True
for i in range(0,N):
    if flag[i]!=N-1:
        able=False

if able:
    print(day)
else:
    print(-1)
### BUGGY CODE ###

N = int(input())
v = [[]for i in range(N+1)]
d = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    v[a].append(b)
    v[b].append(a)
    d[a][b] = c
    d[b][a] = c
Q,K = map(int,input().split())
#p is parent
#pcd is parent-child distance
reached = [0 for i in range(N+1)]
def f(p,pcd):
    global v,d,K,reached
    reached[p] = 1
    d[K][p] = pcd
    for c in v[p]:
        if reached[c] == 0:
            f(c,pcd+d[p][c])
f(K,0)
for i in range(Q):
    x,y = map(int,input().split())
    print(d[K][x]+d[K][y])

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
N = int(input())
T = [[]for i in range(N+1)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    T[a].append((b,c))
    T[b].append((a,c))
Q,K = map(int,input().split())
D = [0]*(N+1)
def f(v,p,cost):
    global T,K,D
    for C in T[v]:
        if C[0]!=p:
            D[C[0]] = cost+C[1]
            f(C[0],v,cost+C[1])
f(K,0,0)
for i in range(Q):
    x,y = map(int,input().split())
    print(D[x]+D[y])
### BUGGY CODE ###

N = int(input())
J = list(map(int,input().split()))
K = list(map(int,input().split()))
L = list(map(int,input().split()))
J.sort()
K.sort()
L.sort()
S = 0
k = 0
l = 0
for i in range(N):
  for p in range(N):
    if K[i] > J[p]:
      k += 1
    else:
      break
  for q in range(N):
    if K[i] < L[N-q-1]:
      l += 1
    else:
      break
  S += k*l
  k = 0
  l = 0
print(S)

### FIXED CODE ###

import bisect
N = int(input())
J = list(map(int,input().split()))
K = list(map(int,input().split()))
L = list(map(int,input().split()))
J.sort()
K.sort()
L.sort()
S = 0
for i in range(N):
  k = bisect.bisect_left(J,K[i])
  l = N - bisect.bisect_right(L,K[i])  
  S += k*l
print(S)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
list_s = list(s)
list_score = [ list(map(int,input().split(" "))) for i in range(q)]
list_c = []
for i in range(n-1):
    if list_s[i] == "A" and list_s[i+1] == "C":
        list_c.append([i+1, i+2])


ans = 0

for i in range(q):
    g = list_score[i]
    ans = 0
    for j in range(len(list_c)):
        f = list_c[j]
        if g[0] <= f[0] and f[1] <= g[1]:
            ans += 1

    print(ans)




### FIXED CODE ###

n, q = map(int, input().split())
s = input()
list_s = list(s)
list_score = [ list(map(int,input().split(" "))) for i in range(q)]
list_c = [0]
a = 0
for i in range(n-1):
    if list_s[i] == "A" and list_s[i+1] == "C":
        a += 1
        list_c.append(a)
    else:
        list_c.append(a)

for i in range(q):
    g = list_score[i]
    print(list_c[g[1]-1]-list_c[g[0]-1])
### BUGGY CODE ###

def min_mult(a, b):
    result = max(a, b)
    while result % min(a, b) != 0:
        result += max(a, b)
    return result
N = int(input())
multiple = 1
for _ in range(N):
    multiple = min_mult(multiple, int(input()))
print(multiple)

### FIXED CODE ###

def min_mult(a, b):
    result = max(a, b)
    while result % min(a, b) != 0:
        result += max(a, b)
    return result
N = int(input())
multiple = 1
for _ in range(N):
    multiple = min_mult(multiple, int(input()))
print(multiple)
### BUGGY CODE ###

n,m=map(int,input().split())
data=[]
p=[0]*n
y=[[] for _ in range(n)]
for i in range(m):
    p_i,y_i=map(int,input().split())
    data.append([p_i,y_i])
    p[p_i-1]+=1
    y[p_i-1].append(y_i)
for i in range(n):
    y[i].sort()
for i in range(m):
    ans_p=data[i][0]
    ans_y=y[ans_p-1].index(data[i][1])+1
    ans_p=(str(ans_p)).zfill(6)
    ans_y=(str(ans_y)).zfill(6)
    print(ans_p+ans_y)

### FIXED CODE ###

from operator import itemgetter
n,m=map(int,input().split())
data=[]
for i in range(m):
    p_i,y_i=map(int,input().split())
    data.append([p_i,y_i,i])
data.sort()
data.append([n+1,0,m])
buf=1
for i in range(m):
    data[i].append(buf)
    if data[i][0]==data[i+1][0]:
        buf+=1
    else:
        buf=1
data.sort(key=itemgetter(2))
for i in range(m):
    ans_p=data[i][0]
    ans_y=data[i][3]
    ans_p=(str(ans_p)).zfill(6)
    ans_y=(str(ans_y)).zfill(6)
    print(ans_p+ans_y)
### BUGGY CODE ###

X, Y, A, B, C = map(int, input().split())

pList = list(map(int, input().split()))
qList = list(map(int, input().split()))
rList = list(map(int, input().split()))

pList.sort(reverse=True)
qList.sort(reverse=True)
rList.sort(reverse=True)

pList = pList[:X]
qList = qList[:Y]

value = 0

for indx in range(X+Y):
    if (pList[0] >= qList[0]) and (pList[0] >= rList[0]):
        value += pList[0]
        pList.pop(0)

        if len(pList) == 0:
            pList.append(-1)

    elif (qList[0] > pList[0]) and (qList[0] > rList[0]):
        value += qList[0]
        qList.pop(0)

        if len(qList) == 0:
            qList.append(-1)

    else:
        value += rList[0]
        rList.pop(0)

        if len(rList) == 0:
            rList.append(-1)


print(value)


### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())

pList = list(map(int, input().split()))
qList = list(map(int, input().split()))
rList = list(map(int, input().split()))

pList.sort(reverse=True)
qList.sort(reverse=True)
rList.sort(reverse=True)

pList = pList[:X]
qList = qList[:Y]

appleList = pList + qList + rList
appleList.sort(reverse=True)
appleList = appleList[:X+Y]

print(sum(appleList))
### BUGGY CODE ###

substrs = set()
string = input()
k = int(input())

def solve(string):
	if len(string) == 0:
		return
	if string in substrs:
		return
	substrs.add(string)
	for i in range(1,len(string)+1):
		solve(string[:i])
	solve(string[1:])

solve(string)
substrs = sorted(list(substrs))
for i,s in enumerate(substrs):
	if i == k-1:
		print(s)
		break


### FIXED CODE ###

substrs = set()
string = input()
k = int(input())

for i in range(len(string)):
	for j in range(i, i+5):
		substrs.add(string[i:j+1])

substrs = sorted(list(substrs))
for i,s in enumerate(substrs):
	if i == k-1:
		print(s)
		break
### BUGGY CODE ###

N,W=map(int,input().split())
dp=[ [0]*(W+1) for i in range(N+1) ]
#print(dp)
Wl=[]
Vl=[]
for i in range(N):
  w,v=map(int,input().split())
  Wl.append(w)
  Vl.append(v)

for i in range(1,N+1):
  for w in range(W+1):
    #print(i,w)
    if w>=Wl[i-1]:
      dp[i][w]=max(dp[i-1][w-Wl[i-1]]+Vl[i-1],dp[i-1][w])
    else:
      dp[i][w]=dp[i-1][w]
print(dp[-1][-1])

### FIXED CODE ###

N,W=map(int,input().split())
dp=[ [0]*(W+1) for i in range(N+1) ]
#print(dp)
Wl=[]
Vl=[]
for i in range(N):
  w,v=map(int,input().split())
  Wl.append(w)
  Vl.append(v)

for i in range(1,N+1):
  for w in range(W+1):
    #print(i,w)
    if w>=Wl[i-1]:
      dp[i][w]=max(dp[i-1][w-Wl[i-1]]+Vl[i-1],dp[i-1][w])
    else:
      dp[i][w]=dp[i-1][w]
print(dp[-1][-1])
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=pL=0

#積がx以下になる組み合わせの数
def f(x):
    global pR,pL
    ret=0
    if x<0:
        pR=len(pA)
        for na in nA:
            ret+=g2(pA,na,x)
        pR=len(nA)
        for pa in pA:
            ret+=g2(nA,pa,x)
    elif x==0:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
    else:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
        pR=len(nA)
        for na in nA:
            ret+=g1(nA,na,x)-(1 if na*na<=x else 0)
        pR=len(pA)
        for pa in pA:
            ret+=g1(pA,pa,x)-(1 if pa*pa<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    l=0
    over=pR
    while over-l>1:
        m=(over+l)//2
        if L[m]*n<=x: l=m
        else: over=m
    pR=over
    return l+1

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    global pL
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    under=-1
    r=pR
    while r-under>1:
        m=(under+r)//2
        if L[m]*n<=x: r=m
        else: under=m
    pL=under
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=0
neg=len(nA)*len(pA)*2
zzz=len(zero)*(N-len(zero)+N-1)

#積がx以下になる組み合わせの数
def f(x):
    global pR
    ret=0
    if x<0:
        pR=len(pA)-1
        for na in nA:
            while pR>=0:
                if na*pA[pR]>x: break
                pR-=1
            ret+=len(pA)-pR-1
    elif x==0:
        ret+=neg
        ret+=zzz
        ret//=2
    else:
        ret+=neg
        ret+=zzz
        pR=len(nA)-1
        for na in nA:
            while pR>=0:
                if na*nA[pR]<=x: break
                pR-=1
            ret+=pR+1
            ret-=1 if na*na<=x else 0
        pR=len(pA)-1
        for pa in pA:
            while pR>=0:
                if pa*pA[pR]<=x: break
                pR-=1
            ret+=pR+1
            ret-=1 if pa*pa<=x else 0
        ret//=2
    return ret
#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)
### BUGGY CODE ###

N = int(input())
min = N
max_i = 0
max_j = 0
for i in range(1,N // 2 + 1):
    if N % i == 0:
        j = N // i
        if abs(i - j) < min:
            min = abs(i - j)
            max_i = i
            max_j = j

print(max_i + max_j - 2)

### FIXED CODE ###

N = int(input())
min = N
max_i = 0
max_j = 0
for i in range(1,1000000):
    if N % i == 0:
        j = N // i
        if abs(i - j) < min:
            min = abs(i - j)
            max_i = i
            max_j = j
for i in range(1000000,N // 1000000 + 1):
    if N % i == 0:
        j = N // i
        if abs(i - j) < min:
            min = abs(i - j)
            max_i = i
            max_j = j

print(max_i + max_j - 2)
### BUGGY CODE ###

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
C=[]

for _ in range(H):
    C.append(list(input()))

def keiro(x,y,cn,k):
    nx=[]

    i=1
    while y+i<=W-1 and i<=k:
        A=C[x][y+i]
        if A=='.' or A==str(cn+1):
            C[x][y+i]=str(cn+1)
            nx.append([x,y+i])
            i+=1
        else:
            break
    
    i=1
    while y-i>=0 and i<=k:
        A=C[x][y-i]
        if A=='.' or A==str(cn+1):
            C[x][y-i]=str(cn+1)
            nx.append([x,y-i])
            i+=1
        else:
            break
    
    i=1
    while x+i<=H-1 and i<=k:
        A=C[x+i][y]
        if A=='.' or A==str(cn+1):
            C[x+i][y]=str(cn+1)
            nx.append([x+i,y])
            i+=1
        else:
            break
    
    i=1
    while x-i>=0 and i<=k:
        A=C[x-i][y]
        if A=='.' or A==str(cn+1):
            C[x-i][y]=str(cn+1)
            nx.append([x-i,y])
            i+=1
        else:
            break

    return nx

C[x1-1][y1-1]=str(0)
taisho=keiro(x1-1,y1-1,0,K)
result=1

while C[x2-1][y2-1]=='.':
    next_taisho=[]
    if len(taisho)==0:
        result=-1
        break
    for l in taisho:
        m=keiro(l[0],l[1],result,K)

        for n in m:
            next_taisho.append(n)
    result+=1
    taisho=next_taisho.copy()

print(result)

### FIXED CODE ###

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
C=[]
nx=set([])

for _ in range(H):
    C.append(list(input()))

def keiro(x,y,k):
    i=1
    while True:
        if y+i>W-1 or C[x][y+i]!='.' or i>k:
            break
        else:
            if (x,y+i) not in nx:
                nx.add((x,y+i))
            i+=1
    
    i=1
    while True:
        if y-i<0 or C[x][y-i]!='.' or i>k:
            break
        else:
            if (x,y-i) not in nx:
                nx.add((x,y-i))
            i+=1
    
    i=1
    while True:
        if x+i>H-1 or C[x+i][y]!='.' or i>k:
            break
        else:
            if (x+i,y) not in nx:
                nx.add((x+i,y))
            i+=1
    
    i=1
    while True:
        if x-i<0 or C[x-i][y]!='.' or i>k:
            break
        else:
            if (x-i,y) not in nx:
                nx.add((x-i,y))
            i+=1

    return 0

C[x1-1][y1-1]=0
keiro(x1-1,y1-1,K)
taisho=nx.copy()
result=1
for j in nx:
    C[j[0]][j[1]]=result

while C[x2-1][y2-1]=='.':
    nx=set([])
    if len(taisho)==0 or result>10**6:
        result=-1
        break
    for l in taisho:
        keiro(l[0],l[1],K)
    result+=1
    for j in nx:
        C[j[0]][j[1]]=result
    taisho=nx.copy()

print(result)
### BUGGY CODE ###

from collections import deque


user_num,rer_num=map(int,input().split())
graph=[[] for loop in range(user_num)]

for loop in range(rer_num):
    user1,user2=map(int,input().split())
    graph[user1].append(user2)
    graph[user2].append(user1)

#group[user1]はuser1が属するグループ.同じグループに属するuser同士は互いに到達可能
group=[-1]*user_num

que=deque([])
que.append(0)
tmp_group=0
for user in range(user_num):
    if(group[user]==-1):
        que.append(user)
        group[user]=tmp_group
        while(1):
            user1=que.popleft()
            for user2 in graph[user1]:
                if(group[user2]!=-1):
                    que.append(user2)
                    group[user2]=tmp_group
            if(len(que)==0):
                tmp_group+=1
                break


for loop in range(int(input())):
    user1,user2=map(int(input()))
    if(group[user1]==group[user2]):
        print("yes")
    else:
        print("no")


### FIXED CODE ###

from collections import deque


user_num,rer_num=map(int,input().split())
graph=[[] for loop in range(user_num)]

for loop in range(rer_num):
    user1,user2=map(int,input().split())
    graph[user1].append(user2)
    graph[user2].append(user1)

#group[user1]はuser1が属するグループ.同じグループに属するuser同士は互いに到達可能
group=[-1]*user_num

que=deque([])
que.append(0)
tmp_group=0
for user in range(user_num):
    if(group[user]==-1):
        que.append(user)
        group[user]=tmp_group
        while(1):
            user1=que.popleft()
            for user2 in graph[user1]:
                if(group[user2]==-1):
                    que.append(user2)
                    group[user2]=tmp_group
            if(len(que)==0):
                tmp_group+=1
                break

for loop in range(int(input())):
    user1,user2=map(int,input().split())
    if(group[user1]==group[user2]):
        print("yes")
    else:
        print("no")
### BUGGY CODE ###

n, x, y = map(int,input().split())

ans = []
for i in range(1,n+1):
    for j in range(i+1,n+1):
        ans.append(min(j-i,abs(x-i)+1+abs(y-j)))
for k in range(1,n):
    print(ans.count(k))

### FIXED CODE ###

n, x, y = map(int,input().split())

ans = [0]*(n-1)
for i in range(1,n+1):
    for j in range(i+1,n+1):
        ans[min(j-i,abs(x-i)+1+abs(y-j))-1] += 1
        #ans.append(min(j-i,abs(x-i)+1+abs(y-j)))
for k in range(n-1):
    print(ans[k])
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n = int(input())
    a = list(map(int, input().split()))
    b = [a.index(_) for _ in range(1,n+1)]
    r = (b[0]+1) * (n-b[0])
    c = [b[0]]
    m = 2
    for i in b[1:]:
        ri = bisect.bisect(c, i)
        if ri == 0:
            r += (i+1) * (c[ri]-i) * m
        elif ri == m-1:
            r += (i-c[ri-1]) * (n-i) * m
        else:
            r += (i-c[ri-1]) * (c[ri]-i) * m
        m += 1
        bisect.insort(c, i)

    return r

print(f())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n = int(input())
    a = list(map(int, input().split()))
    l = list(range(n+2))
    r = list(range(n+2))
    b = [0]*(n+2)
    for i, x in enumerate(a, 1):
        b[x] = i
    c = 0
    for i in range(n,0,-1):
        bi = b[i]
        c += i * (r[bi] - bi + 1) * (bi - l[bi] + 1)
        r[l[bi]-1] = r[bi]
        l[r[bi]+1] = l[bi]
    return c

print(f())
### BUGGY CODE ###

# -*- coding: utf-8 -*-

class Node(object):
    def __init__(self, key, prev=None, nex=None):
        self.key = key
        self.prev = prev
        self.next = nex
    
class DoublyLinkedLiset(object):
    def __init__(self):
        self.nil = Node(None)
        self.nil.next = self.nil
        self.nil.prev = self.nil
    
    def insert(self, x):
        X = Node(x)
        X.next = self.nil.next
        self.nil.next.prev = X
        self.nil.next = X
        X.prev = self.nil

    def listSearch(self, x):
        cur = self.nil.next
        while (cur != self.nil and cur.key != x):
            cur = cur.next
        
        return cur

    def deleteNode(self, X):
        if X == self.nil:
            return
        X.prev.next = X.next
        X.next.prev = X.prev
        #del X

    def deleteFirst(self):
        self.deleteNode(self.nil.next)

    def deleteLast(self):
        self.deleteNode(self.nil.prev)

    def deleteKey(self, x):
        self.deleteNode(self.listSearch(x))

    def printList(self):
        cur = self.nil.next
        ret = []
        
        while cur.key is not None:
            ret.append(cur.key)
            cur = cur.next
  
        print(' '.join(ret))

if __name__ == '__main__':

    n = int(input())
    dll = DoublyLinkedLiset()

    for i in range(n):
        command = input().split(" ")
        if command[0] == "insert":
            dll.insert(command[1])
        elif command[0] == "delete":
            dll.deleteKey(command[1])
        elif command[0] == "deleteFirst":
            dll.deleteFirst()
        elif command[0] == "deleteLast":
            dll.deleteLast()

    dll.printList()
    



### FIXED CODE ###

# -*- coding: utf-8 -*-

from collections import deque

if __name__ == '__main__':
    n = int(input())
    L = deque()

    for _ in range(n):
        command = input().split(" ")
        if command[0] == "insert":
            L.appendleft(command[1])
        elif command[0] == "delete":
            try:
                L.remove(command[1])
            except:
                pass
        elif command[0] == "deleteFirst":
            L.popleft()
        elif command[0] == "deleteLast":
            L.pop()

    print(" ".join(L))
### BUGGY CODE ###

import math
import numpy as np


def main():
    s = input().split(" ")
    N = int(s[0])
    K = int(s[1])
    A = [int(a) for a in input().split(" ")]
    F = [int(a) for a in input().split(" ")]
    A.sort()
    F.sort()
    F.reverse()
    AF = [A[i] * F[i] for i in range(N)]
    idx = np.argsort(AF)[::-1]

    A = [A[idx[i]] for i in range(N)]
    F = [F[idx[i]] for i in range(N)]
    AF = [AF[idx[i]] for i in range(N)]
    m = np.max(AF)

    if(func(0, AF, F, N, K)):
        print(0)
        return
    a = 0
    b = m
    for aaa in range(m):
        if(abs(b - a) <= 1):
            print(b)
            return
        mid = int((b - a) / 2.) + a
        if(func(mid, AF, F, N, K)):
            b = mid
        else:
            a = mid
    print("???????")


def func(saidai, AF, F, N, K):
    count = 0
    for n in range(N):
        if(AF[n] <= saidai):
            return True
        count += math.ceil((AF[n] - saidai) / F[n])
        if(count > K):
            return False
    return True


if(__name__ == "__main__"):
    main()


### FIXED CODE ###

import math
import numpy as np


def main():
    s = input().split(" ")
    N = int(s[0])
    K = int(s[1])
    A = np.array([int(a) for a in input().split(" ")])
    F = np.array([int(a) for a in input().split(" ")])
    A = np.sort(A)
    F = np.sort(F)[::-1]
    AF = A * F
    m = np.max(AF)

    if(func(0, AF, F, N, K)):
        print(0)
        return
    a = 0
    b = m
    for aaa in range(m):
        if((b - a) <= 1):
            print(b)
            return
        mid = int((b - a) / 2.) + a
        if(func(mid, AF, F, N, K)):
            b = mid
        else:
            a = mid
    print("???????")


def func(saidai, AF, F, N, K):
    count = np.sum(np.ceil((AF[(AF - saidai) > 0] - saidai) / F[(AF - saidai) > 0]))
    return count <= K


if(__name__ == "__main__"):
    main()