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

from collections import deque
import copy
H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
S=[list(str(input())) for i in range(H)]

field2=copy.deepcopy(S)
move=[[1,0],[-1,0],[0,1],[0,-1]]
ans=0
temp=deque()

def dfs2(x,y):
    field2[x][y]='#'
    temp.append([x,y])
    for i in range(4):
        nx=x+move[i][0]
        ny=y+move[i][1]
        if 0<=nx and nx<H and 0<=ny and ny<W and field2[nx][ny]=='.':
            dfs2(nx,ny)
    return temp

start=dfs2(Ch-1,Cw-1)

while True:
    if field2[Dh-1][Dw-1]=='#':
        print(ans)
        exit()
    else:
        for i in range(len(start)):
            ttemp=start.popleft()
            for hh in range(-2,3):
                for ww in range(-2,3):
                    nnx=ttemp[0]+hh
                    nny=ttemp[1]+ww
                    if 0<=nnx and nnx<H and 0<=nny and nny<W and field2[nnx][nny]=='.':
                        dfs2(nnx,nny)
        ans+=1
    if len(start)==0:
        print(-1)
        exit()


### FIXED CODE ###

from collections import deque
import copy
H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
S=[list(str(input())) for i in range(H)]

field2=copy.deepcopy(S)
move=[[1,0],[-1,0],[0,1],[0,-1]]
ans=0
temp=deque()

def dfs2(x,y):
    field2[x][y]='#'
    temp.append([x,y])
    for i in range(4):
        nx=x+move[i][0]
        ny=y+move[i][1]
        if 0<=nx and nx<H and 0<=ny and ny<W and field2[nx][ny]=='.':
            dfs2(nx,ny)
    return temp

start=dfs2(Ch-1,Cw-1)

while True:
    if field2[Dh-1][Dw-1]=='#':
        print(ans)
        exit()
    else:
        for i in range(len(start)):
            ttemp=start.popleft()
            for hh in range(-2,3):
                for ww in range(-2,3):
                    nnx=ttemp[0]+hh
                    nny=ttemp[1]+ww
                    if 0<=nnx and nnx<H and 0<=nny and nny<W and field2[nnx][nny]=='.':
                        dfs2(nnx,nny)
        ans+=1
    if len(start)==0:
        print(-1)
        exit()
### BUGGY CODE ###

S = input()
Q = int(input())

for i in range(Q):
    T = input()
    if T == '1':
        S = S[::-1]
    else:
        T = T.split()
        if T[1] == '1':
            S = T[2] + S
        else:
            S = S + T[2]

print(S)

### FIXED CODE ###

S = input()
Q = int(input())

direction = 1
head = []
tail = []
for i in range(Q):
    T = input()
    if T == '1':
        direction = direction * -1
    else:
        T = T.split()
        if T[1] == '1':
            if direction == 1:
                head.append(T[2])
            else:
                tail.append(T[2])
        else:
            if direction == 1:
                tail.append(T[2])
            else:
                head.append(T[2])

head = head[::(-1)]
head.append(S)
head.extend(tail)
S = "".join(head)[::direction]

print(S)
### BUGGY CODE ###

import collections
from itertools import combinations
N = int(input())
ab = [tuple(map(int, input().split())) for i in range(N-1)]
M = int(input())
uv = [tuple(map(int, input().split())) for i in range(M)]


def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)

    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


G = [[-1]*N for i in range(N)]
for i in range(N-1):
    a, b = ab[i]
    a -= 1
    b -= 1
    G[a][b] = i
    G[b][a] = i

q = collections.deque()

G2 = [[0 for j in range(N)] for i in range(N)]

for i in range(N):
    q.append((i, 0))
    reached = [False]*N
    reached[i] = True
    while(q):
        x, s = q.popleft()
        for y in range(N):
            if G[x][y] == -1 or reached[y]:
                continue
            else:
                G2[i][y] = s | (1 << G[x][y])
                q.append((y, s | 1 << G[x][y]))
                reached[y] = True


ans = 2**(N-1)
ans2 = 0
for i in range(1, 2**M):
    tmp = 2**(N-1) - 1
    for j in range(M):
        if (i >> j) % 2 == 1:
            u, v = uv[j]
            u -= 1
            v -= 1
            tmp &= ~G2[u][v]
    ans2 += ((-1)**(popcount(i)-1)) * (1 << popcount(tmp))
    # print(ans2, i)
print(ans-ans2)


### FIXED CODE ###

import collections
from itertools import combinations
N = int(input())
ab = [tuple(map(int, input().split())) for i in range(N-1)]
M = int(input())
uv = [tuple(map(int, input().split())) for i in range(M)]


def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


G = [[-1]*N for i in range(N)]
for i in range(N-1):
    a, b = ab[i]
    a -= 1
    b -= 1
    G[a][b] = i
    G[b][a] = i

q = collections.deque()

G2 = [[0 for j in range(N)] for i in range(N)]

for i in range(N):
    q.append((i, 0))
    reached = [False]*N
    reached[i] = True
    while(q):
        x, s = q.popleft()
        for y in range(N):
            if G[x][y] == -1 or reached[y]:
                continue
            else:
                G2[i][y] = s | (1 << G[x][y])
                q.append((y, s | 1 << G[x][y]))
                reached[y] = True


ans = 2**(N-1)
ans2 = 0
for i in range(1, 2**M):
    tmp = 2**(N-1) - 1
    for j in range(M):
        if (i >> j) % 2 == 1:
            u, v = uv[j]
            u -= 1
            v -= 1
            tmp &= ~G2[u][v]
    ans2 += ((-1)**(popcount(i)-1)) * (1 << popcount(tmp))
    # print(ans2, i)
print(ans-ans2)
### BUGGY CODE ###

S = input()
G = [1 if s == "R" else -1 for s in S]

memo = [None, None]
pos = [1] * len(G)

for i in range(10 ** 100):
  new_pos = [0] * len(G)
  for j, n in enumerate(pos):
    new_pos[j + G[j]] += n
  pos = new_pos
  if i > 1:
    if pos == memo[0]:
      if i % 2 == 1:
        print(" ".join([str(x) for x in pos]))
      else:
        print(" ".join([str(x) for x in memo[1]]))
      break
  memo[0] = memo[1]
  memo[1] = pos

### FIXED CODE ###

S = input()
l, r = 0, len(S)

memo = [0] * len(S)

for i in range(len(S) - 1):
  if S[i] == "R" and S[i + 1] == "L":
    n = (i - l) // 2
    memo[i] = n + 1
    memo[i + 1] = (i - l - n) + 1
    l = i + 2
  if S[i] == "L" and S[i + 1] == "R":
    n = (i + 1 - l) // 2
    memo[l - 1] += n
    memo[l - 2] += i + 1 - l - n
    l = i + 1
if l < r:
  n = (r - l) // 2
  memo[l - 1] += n
  memo[l - 2] += r - l - n

print(" ".join([str(x) for x in memo]))
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
max_a = max(a)
for i in range(len(a)):
    if a[i] != max_a:
        print(max_a)
        continue
    if a.count(a[i]) > 1:
        print(max_a)
        continue
    b = a.copy()
    del b[i]
    print(max(b))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
max_a = max(a)
second_a = sorted(a)[-2]
max_count = a.count(max_a) - 1
if max_count:
    [print(max_a) for _ in range(len(a))]
else:
    [print(max_a) if a[i] != max_a else print(second_a) for i in range(len(a))]
### BUGGY CODE ###

def calc(A,i,j):
    num_2 = 0
    num_10 = 0
    for k in range(i,j+1):
        num_2 = A[k] ^ num_2
        num_10 = num_10 + A[k]
    if num_10 == int(num_2):
        return True
    else:
        return False

if __name__ == '__main__':
    N = int(raw_input())
    A = map(int, raw_input().split())

    ans = 0
    for i in range(N):
        for j in range(i,N):
            if calc(A,i,j) == True:
                ans += 1
            else:
                break

    print(ans)

### FIXED CODE ###

if __name__ == '__main__':
    N = int(raw_input())
    A = map(int, raw_input().split())
    head = 0
    tail = 0
    num_2 = 0
    num_10 = 0
    ans = 0
    now_len = 0
    while(head < N):
        num_2 = num_2 ^ A[head]
        num_10 += A[head]
        if num_2 == num_10:
            head += 1
            now_len += 1
            ans += now_len
        else:
            num_2 ^= A[tail]
            num_10 -= A[tail]
            num_2 ^= A[head]
            num_10 -= A[head]
            tail += 1
            now_len -= 1

    print(ans)
### BUGGY CODE ###

class UnionFind():
   def __init__(self, n):
       self.n = n
       self.parents = [-1] * n

   def find(self, x):
       if self.parents[x] < 0:
           return x
       else:
           self.parents[x] = self.find(self.parents[x])
           return self.parents[x]

   def union(self, x, y):
       x = self.find(x)
       y = self.find(y)

       if x == y:
           return

       if self.parents[x] > self.parents[y]:
           x, y = y, x

       self.parents[x] += self.parents[y]
       self.parents[y] = x

   def size(self, x):
       return -self.parents[self.find(x)]

   def same(self, x, y):
       return self.find(x) == self.find(y)

   def members(self, x):
       root = self.find(x)
       return [i for i in range(self.n) if self.find(i) == root]

   def roots(self):
       return [i for i, x in enumerate(self.parents) if x < 0]

   def group_count(self):
       return len(self.roots())

   def all_group_members(self):
       return {r: self.members(r) for r in self.roots()}

   def __str__(self):
       return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,k,l = map(int,input().split())
uf1 = UnionFind(n)
uf2 = UnionFind(n)

for _ in range(k):
   p,q = map(int,input().split())
   p -= 1
   q -= 1
   uf1.union(p,q)

for _ in range(l):
   r,s = map(int,input().split())
   r -= 1
   s -= 1
   uf2.union(r,s)

pair = []
for i in range(n):
   pair.append((uf1.find(i), uf2.find(i)))

for i in range(n):
   print(pair.count(pair[i]))

### FIXED CODE ###

class UnionFind():
   def __init__(self, n):
       self.n = n
       self.parents = [-1] * n

   def find(self, x):
       if self.parents[x] < 0:
           return x
       else:
           self.parents[x] = self.find(self.parents[x])
           return self.parents[x]

   def union(self, x, y):
       x = self.find(x)
       y = self.find(y)

       if x == y:
           return

       if self.parents[x] > self.parents[y]:
           x, y = y, x

       self.parents[x] += self.parents[y]
       self.parents[y] = x

   def size(self, x):
       return -self.parents[self.find(x)]

   def same(self, x, y):
       return self.find(x) == self.find(y)

   def members(self, x):
       root = self.find(x)
       return [i for i in range(self.n) if self.find(i) == root]

   def roots(self):
       return [i for i, x in enumerate(self.parents) if x < 0]

   def group_count(self):
       return len(self.roots())

   def all_group_members(self):
       return {r: self.members(r) for r in self.roots()}

   def __str__(self):
       return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,k,l = map(int,input().split())
uf1 = UnionFind(n)
uf2 = UnionFind(n)

for _ in range(k):
   p,q = map(int,input().split())
   p -= 1
   q -= 1
   uf1.union(p,q)

for _ in range(l):
   r,s = map(int,input().split())
   r -= 1
   s -= 1
   uf2.union(r,s)

from collections import defaultdict
dic = defaultdict(int)
pair = []
for i in range(n):
   pair.append((uf1.find(i), uf2.find(i)))
   dic[(uf1.find(i), uf2.find(i))] += 1

for i in range(n):
   print(dic[pair[i]])
### BUGGY CODE ###

from collections import deque
N = int(input())
A = deque(map(int, input().split()))
mod = 10**9 + 7
M = len(bin(max(A))) - 2
ans = 0
bitlist = [1]
anslist = [0 for _ in range(M)]
for k in range(M):
    bitlist.append(bitlist[-1]*2%mod)
counter = [0 for _ in range(M)]

for k in range(N):
    a = A.pop()
    c = 0
    while a:
        b = a & 1
        if b == 0:
            anslist[c] += counter[-c-1]
        else:
            anslist[c] += k - counter[-c-1]
            counter[-c-1] += 1
        c += 1
        a >>= 1
    while c < M:
        anslist[c] += counter[-c-1]
        c += 1
for k in range(M):
    ans += anslist[k]*bitlist[k]%mod
    ans %= mod
print(ans)


### FIXED CODE ###

from collections import deque
N = int(input())
A = deque(map(int, input().split()))
mod = 10**9 + 7
M = len(bin(max(A))) - 2
ans = 0
bitlist = [1]
for k in range(M):
    bitlist.append(bitlist[-1]*2%mod)
counter = [0 for _ in range(M)]

for k in range(N):
    a = A.pop()
    c = 0
    while c < M:
        b = a & 1
        if b == 0:
            ans += counter[-c-1]*bitlist[c]%mod
            ans %= mod
        else:
            ans += (k-counter[-c-1])*bitlist[c]%mod
            ans %= mod
            counter[-c-1] += 1
        c += 1
        a >>= 1
print(ans)
### BUGGY CODE ###

n,k,*t=map(int,open(0).read().split())
*z,=zip(*[iter(t)]*2)
ok=10**20
ng=-1
while ok-ng>1:
  mid=(ok+ng)//2
  if sum(max(0,0--(mid-w)//d)for w,d in z)<k:ng=mid
  else:ok=mid
print(ng)

### FIXED CODE ###

n,k,*t=map(int,open(0).read().split())
*z,=zip(*[iter(t)]*2)
ok=10**20
ng=-1
while ok-ng>1:
  mid=(ok+ng)//2
  if sum(max(0,0--(mid-w)//d)for w,d in z)<k:ng=mid
  else:ok=mid
print(ng)
### BUGGY CODE ###

def check(x, y, K, S):
  if x + y > S:
    return False
  for z in range(K+1):
    if x + y + z == S:
      return True
  return False

K, S = list(map(int, input('').split()))
count = 0
for x in range(K+1):
  for y in range(K+1):
    if check(x, y, K, S):
      count += 1
print(count)

### FIXED CODE ###

K, S = list(map(int, input('').split()))
count = 0
for x in range(K+1):
  for y in range(K+1):
    if x + y <= S and x + y + K >= S:
      count += 1
print(count)
### BUGGY CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
# n = int(input())
mod = 10 ** 9 + 7
a.sort()
# print(a)
mx,mn = 0, 0

def C(n, k, mod):
    x,y = 1,1
    while k > 0:
        x *= n ; y *= k
        n, k = n-1, k-1
        x %= mod ; y %= mod
    return x * pow(y, mod-2, mod)


for i in range(k-1,n):
    mx += (a[i] * C(i, k-1, mod)) % mod

for i in range(0,n-k+1):
    mn += (a[i] * C(n-i-1, k-1, mod)) % mod

ans = (mx - mn) % mod

print(ans)


### FIXED CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
# n = int(input())
mod = 10 ** 9 + 7
p = mod
a.sort(reverse = True)
# print(a)
ans = 0

#
# def C(n, k):
#     if k == 0:
#         return 1
#     elif n < k or k < 0:
#         return 0
#     else:
#         x,y = 1,1
#         while k > 0:
#             x *= n
#             y *= k
#             n, k = n-1, k-1
#
#         return x * pow(y, mod-2, mod) % mod
#

fac = [0] * (n + 1)
fac[0] = 1
for i in range(n):
    fac[i + 1] = fac[i] * (i + 1) % mod


def C(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], p - 2, p) * pow(fac[k], p - 2, p) % p


for i in range(0,n-k+1):
    ans += a[i] * C(n-i-1, k-1)
    ans %= mod

a.reverse()
for i in range(0,n-k+1):
    ans -= a[i] * C(n-i-1, k-1)
    ans %= mod



print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
res = 0
for i in range(n-1):
    res += max(0,max(a[:-(i+1)])-a[-(i+1)])
print(res)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
res = 0
temp_max = 0
for x in a:
    if temp_max > x:
        res += temp_max - x
    temp_max = max(temp_max,x)

print(res)
### BUGGY CODE ###

N=int(input())
UVW=[list(map(int,input().split())) for i in range(N-1)]
UVW.sort(key=lambda x:x[1])
UVW.sort()
L=[-1]*(N+1)
L[1]=0

while -1 in L[1:]:
    for i in range(N-1):
        if L[UVW[i][0]]==0:
            if UVW[i][2]%2==0:
                L[UVW[i][1]]=0
            else:
                L[UVW[i][1]]=1
        elif L[UVW[i][0]]==1:
            if UVW[i][2]%2==0:
                L[UVW[i][1]]=1
            else:
                L[UVW[i][1]]=0
        else:
            if L[UVW[i][1]]==0:
                if UVW[i][2]%2==0:
                    L[UVW[i][0]]=0
                else:
                    L[UVW[i][0]]=1
            elif L[UVW[i][1]]==1:
                if UVW[i][2]%2==0:
                    L[UVW[i][0]]=1
                else:
                    L[UVW[i][0]]=0

L.pop(0)
for i in L:
    print(i)

### FIXED CODE ###

N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    u-=1; v-=1; w%=2
    G[u].append([v,w])
    G[v].append([u,w])
col=[-1 for i in range(N)]
col[0]=0

from collections import deque
dq=deque([0])

while len(dq)>0:
    p=dq.popleft()
    for i in range(len(G[p])):
        if col[G[p][i][0]]==-1:
            dq.append(G[p][i][0])
            col[G[p][i][0]]=(col[p]+G[p][i][1])%2
        
for i in col:
    print(i)
### BUGGY CODE ###

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
a1=[int(s) for s in a0]
for f in range(k):
    for x in range(n):
        c=0
        for i in range(n):
            if a1[i]-abs(x-i)>=0:
                c=c+1
        a[x]=c
    a1=[int(s) for s in a]
    if sum(a)==n**n:
        break
a=[str(s) for s in a]
a=" ".join(a)
print(a)

### FIXED CODE ###

from numba import njit

@njit(cache=True)
def aaa(n,k,a):
    for f in range(k):
        a1=[0]*(n+1)
        for x in range(n):
            y=max(0,x-a[x])
            a1[y]=a1[y]+1    
            z=min(n-1,x+a[x])
            a1[z+1]=a1[z+1]-1
        a[0]=a1[0]
        for x in range(1,n):    
            a[x]=a[x-1]+a1[x]
        if a==[n]*n:
            break
    return a

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]

b=aaa(n,k,a)
for i in range(n):
    print(b[i])
### BUGGY CODE ###

n,m=map(int,input().split())

if n==1:
  print(m)
else:
  a=int(m**0.5)

  for i in range(int(m/n),0,-1):
    
    if m%i==0 and i*n<=m:
      print(i)
      break

### FIXED CODE ###

n,m=map(int,input().split())

ans=0

if n==1:
  print(m)
else:
  a=int(m**0.5)

  for i in range(1,a):
    if m%i==0:
      if i*n<=m:
        ans=max(ans,i)
      if (m//i)*n<=m:
        ans=max(ans,m//i)
  print(ans)
### BUGGY CODE ###

N = int(input())
count = 0
counter = []

for i in range(1, N+1):
    while i % 2 == 0:
        count += 1
    counter.append([count, i])
    count = 0

counter.sort()
counter.reverse()

print(counter[0][1])


### FIXED CODE ###

N = int(input())
count = 0
counter = []

for i in range(1, N+1):
    num = i
    while num % 2 == 0:
        count += 1
        num /= 2
    counter.append([count, i])
    count = 0

counter.sort()
counter.reverse()

print(counter[0][1])
### BUGGY CODE ###

import heapq
def SME(Whole,start,end,L,ANS):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0 and idx < end:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > K * 0.9  : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [0]*N
start = 0
K = L * int(N ** 0.3 + 2 )
if K > N : K = N
end = K
while (end <= N):
    ANS = SME(A, start, end, L, ANS)
    start = end
    end += K 
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import heapq
import sys

input = sys.stdin.readline


class AtCoder:
    def __lt__(self, other):
        return self[0] < other[0]

    def main(self):
        N, K = map(int, input().split())
        A = list(map(int, input().split()))
        F = list(map(int, input().split()))

        A.sort()
        F.sort(reverse=True)

        hq = []
        heapq.heapify(hq)
        for i in range(N):
            heapq.heappush(hq, (-1 * A[i] * F[i], (F[i], A[i])))

        while K > 0:
            score = heapq.heappop(hq)
            if score[1][1] == 0:
                print(0)
                exit()
            else:
                K -= 1
                new_A = score[1][1] - 1
                heapq.heappush(hq, (-1 * new_A * score[1][0], (score[1][0], new_A)))

        print(-1 * heapq.heappop(hq)[0])


# Run main
if __name__ == '__main__':
    AtCoder().main()


### FIXED CODE ###

import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        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, r = -1, 10 ** 12
        while l + 1 < r:
            mid = (l + r) // 2

            s = 0
            for i in range(N):
                s += max(0, A[i] - mid // F[i])
            if s <= K:
                r = mid
            else:
                l = mid
        print(r)


# Run main
if __name__ == '__main__':
    AtCoder().main()