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

from collections import deque
import math


h,w=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
s=[list(input()) for _ in range(h)]


def bfs():
    for y in range(h):
        for x in range(w):
            if s[y][x]=='.':
                s[y][x]=math.inf


    s[c[0]-1][c[1]-1]=0
    que=deque([[c[0]-1,c[1]-1]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1),(2,2),(2,1),(2,0),(2,-1),(2,-2),(1,2),(1,1),(1,-1),(1,-2),(0,2),(0,-2),(-1,2),(-1,1),(-1,-1),(-1,-2),(-2,2),(-2,1),(-2,0),(-2,-1),(-2,-2)]:
            if 0<=y+i<h and 0<=x+j<w:
                nexty,nextx=y+i,x+j
                dist=s[nexty][nextx]
                if dist!='#':
                    if i*i+j*j==1:
                        if dist>s[y][x]:
                            s[nexty][nextx]=s[y][x]
                            que.append([nexty,nextx])
                    elif dist>s[y][x]+1:
                        s[nexty][nextx]=s[y][x]+1
                        que.append([nexty,nextx])

    if s[d[0]-1][d[1]-1]==math.inf:
        print(-1)
    else:
        print(s[d[0]-1][d[1]-1])

bfs()


### FIXED CODE ###

from collections import deque
from sys import stdin

def bfs():
    readline=stdin.readline
    h,w=map(int,readline().split())
    sy,sx=map(int,readline().split())
    gy,gx=map(int,readline().split())
    sy-=1;sx-=1;gy-=1;gx-=1
    s=[list(readline()) for _ in range(h)]
    dict={".":10000000,"#":-1}
    s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]
    s[sy][sx]=0
    que=deque([[sy,sx]])
    temp=[i for i in range(-2,3)]
    while que:
        y,x=que.popleft()
        s1=s[y][x]
        for i in temp:
            nexty=y+i
            if 0<=nexty<h:
                s2=s[nexty]
                for j in temp:
                    nextx=x+j
                    if 0<=nextx<w and s2[nextx]>=0:
                        dist=s2[nextx]
                        if i*i+j*j<=1 and dist>s1:
                            s[nexty][nextx]=s1
                            que.appendleft([nexty,nextx])
                        elif dist>s1+1:
                            s[nexty][nextx]=s1+1
                            que.append([nexty,nextx])

    if s[gy][gx]==10000000:
        print(-1)
    else:
        print(s[gy][gx])
bfs()
### BUGGY CODE ###

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

aa = a
bb = b
nn = n

balls = ''

while n > 0:
    while aa > 0:
        balls += 'b'
        aa -= 1
    while bb > 0:
        balls += 'r'
        bb -= 1
    n -= 1
    aa = a
    bb = b

ans_balls = balls[:nn]

ans = ans_balls.count('b')

print(ans)

### FIXED CODE ###

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

blue_ball = a
red_ball = b

n_bai = n // (a + b)
n_amari = n % (a + b)

balls = []
ans = 0

balls_sum = 0

while balls_sum < n_amari:
    balls.append(a)
    balls.append(b)
    balls_sum = sum(balls)

while n_amari > 0:
    if n_amari > blue_ball:
        ans += blue_ball
    else:
        ans += n_amari
    n_amari = n_amari - blue_ball - red_ball

ans += n_bai * blue_ball

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

k = int(input())
sum =0
count = 0

def euclidean(p, q):
     if p % q == 0:
          return q
     else:
          return euclidean(q, p % q)

for a in range(1, k+1):
     for b in range(1, k+1):
          for c in range(1, k+1):
               sum += euclidean(euclidean(a, b), c)
print(sum)

### FIXED CODE ###

import math
k = int(input())
sum =0
for a in range(1, k+1):
     for b in range(1, k+1):
          for c in range(1, k+1):
               sum += math.gcd(math.gcd(a, b), c)
print(sum)
### BUGGY CODE ###

a, b = map(int,input().split())
if a < b:
    buf = a
    a = b
    b = buf
while b != 0:
    a, b = b, a % b
gcd = a
count = 1
if gcd % 2 == 0:
    count += 1
    while gcd % 2 == 0:
        gcd = int(gcd / 2)
if gcd % 3 == 0:
    count += 1
    while gcd % 2 == 0:
        gcd = int(gcd / 3)


def hantei(num):
    flag = True
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            flag = False
    return flag


if gcd < 5:
    print(count)
else:
    for i in range(5, gcd + 1, 2):
        if gcd % i == 0 and hantei(i) == True:
            count += 1
            while gcd % i == 0:
                gcd = int(gcd / i)
            if gcd < i+2 :
                print(count)
                exit()
    print(count)


### FIXED CODE ###

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

a, b = map(int,input().split())
g = gcd(a,b)
count = 0
for i in range(2, int(g**0.5)+2):
    if g % i == 0:
        count += 1
        while g % i == 0:
            g //= i
if g != 1:
    count += 1
print(count+1)
### BUGGY CODE ###

import sys
N = int(input())
ll=[]
ll = list(map(int, input().split()))

num =0
for i in range(N):
  for j in range(i):
    if ll[i] <= ll[j]:
      pass
    else:
      num += 1
      break

print(N-num)

### FIXED CODE ###

import sys

N = int(input())
ll=[]
ll = list(map(int, input().split()))

num =0
mi = ll[0]
for i in range(N):
  a = ll[i]
  if mi >= a:
    mi = a
    num += 1

print(num)
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  
  X, Y, Z, K = map(int,input().split())
  A = list(map(int,input().split()))
  B = list(map(int,input().split()))
  C = list(map(int,input().split()))

  AB = [a+b for a in A for b in B]
  AB.sort(reverse = True)
  res = [c+ab for ab in AB[:K] for c in C]
  res.sort(reverse = True)
  for r in res[:K]:
    print(r)

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline

  X,Y,Z,K = map(int,input().split())
  A = list(map(int,input().split()))
  B = list(map(int,input().split()))
  C = list(map(int,input().split()))
  A.sort(reverse = True)
  B.sort(reverse = True)
  C.sort(reverse = True)
  AB = [a+b for a in A for b in B]
  AB.sort(reverse = True)
  res = [c+ab for ab in AB[:min(K, len(AB))] for c in C]
  res.sort(reverse = True)
  print("\n".join(list(map(str,res[:K]))))

if __name__ == "__main__":
  main()
### BUGGY CODE ###

def resolve():
    N = int(input())
    g = {}
    edges = []
    for _ in range(N-1):
        a, b = list(map(int, input().split()))
        g.setdefault(a-1, [])
        g[a-1].append(b-1)
        g.setdefault(b-1, [])
        g[b-1].append(a-1)
        edges.append((a-1, b-1))

    nodes = [(None, 0)]
    colors = [[None for _ in range(N)] for _ in range(N)]
    maxdeg = 0
    while nodes:
        prev, node = nodes.pop()
        prevcol = None
        if prev is not None:
            prevcol = colors[prev][node]
        maxdeg = max(maxdeg, len(g[node]))
        #print(colors)
        #print(prev, node, prevcol)
        cols = [i for i in range(1, len(g[node])+1) if prevcol is None or i!=prevcol]
        #print(cols)
        idx = 0
        for nxt in g[node]:
            if nxt == prev:
                continue
            colors[node][nxt] = cols[idx]
            idx += 1
            nodes.append((node, nxt))
    
    print(maxdeg)
    for src, dst in edges:
        print(colors[src][dst])
            
            




if '__main__' == __name__:
    resolve()


### FIXED CODE ###

def resolve():
    N = int(input())
    g = {}
    edges_to_idx = {}
    edges = []
    for i in range(N-1):
        a, b = list(map(int, input().split()))
        g.setdefault(a-1, [])
        g[a-1].append(b-1)
        g.setdefault(b-1, [])
        g[b-1].append(a-1)
        edges_to_idx.setdefault("{}-{}".format(a-1, b-1), i)
        edges_to_idx.setdefault("{}-{}".format(b-1, a-1), i)
        edges.append((a-1, b-1))

    nodes = [(None, 0)]
    colors = [None for _ in range(N-1)]
    maxdeg = 0
    while nodes:
        prevcol, node = nodes.pop()
        maxdeg = max(maxdeg, len(g[node]))
        idx = 0
        for col in range(1, len(g[node])+1):
            if col == prevcol:
                continue
            nxt = g[node][idx]
            coloridx = edges_to_idx["{}-{}".format(node, nxt)] 
            if colors[coloridx] is not None:
                idx += 1
                if idx >= len(g[node]):
                    break
                nxt = g[node][idx]
                coloridx = edges_to_idx["{}-{}".format(node, nxt)] 
            colors[coloridx] = col
            nodes.append((col, nxt))
            idx += 1
            if idx >= len(g[node]):
                break
            
    
    print(maxdeg)
    for col in colors:
        print(col)
            
            




if '__main__' == __name__:
    resolve()
### BUGGY CODE ###

N=int(input())
X=list(map(int, input().split()))
median=(N//2)-1
x=[]
for i in range (N):
    x.append(X[:i] +X[i+1:])
for i in range (N):
    x[i].sort()
    print(x[i][median])

### FIXED CODE ###

N=int(input())
X=list(map(int, input().split()))
 
import copy
X_sort=copy.deepcopy(X)
X_sort.sort()
X_sort
 
median_control=(X_sort[N//2-1]+X_sort[N//2])/2
for i in range (N):
    if X[i]>median_control:
        print (X_sort[N//2-1])
    if X[i]<=median_control:
        print (X_sort[N//2])
### BUGGY CODE ###

A, B = map(int, input().split())

def make_divisors(a,b):
    ans = 1
    i = 2
    m = []
    while i <= min(A,B):
    #for i in range(1, int(min(a,b)**0.5)+1):
        if a%i == 0 and b%i == 0:
            ans += 1
            m.append(i)
        i += 1
        while i <= min(A,B):
            for mi in m:
                if i%mi == 0:
                    i += 1
                else:
                    break
            else:
                continue
            break
            #if i != n // i:
                #divisors.append(n//i)
    return ans

print(make_divisors(A,B))


### FIXED CODE ###

A, B = map(int, input().split())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

A_divisors = make_divisors(A)
ans = 1
m = []
for d in A_divisors:
    if d == 1: continue
    if B%d==0:
        for mi in m:
            if d%mi == 0:
                break
        else:
            ans += 1
            m.append(d)
            continue
        
print(ans)
### BUGGY CODE ###

H,W = map(int,input().split())
A = [list(input()) for i in range(H)]

ans = 0
Q = []
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            A[h][w]="."
            Q.append((0,h,w))
while Q:
    c,h,w = Q.pop(0)
    if min(h,w)<0 or h>=H or w>=W:continue
    if A[h][w]=="#":continue
    A[h][w] = "#"
    for i in [-1,1]:
        Q.append((c+1,h+i,w))
        Q.append((c+1,h,w+i))
    ans = max(ans,c)
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
S = [[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            S[h][w] = H*W
for h in range(H):
    a = 0
    for w in range(W):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for w in range(W)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
for w in range(W):
    a = 0
    for h in range(H):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for h in range(H)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
ans = H*W
for h in range(H):
    for w in range(W):
        ans = min(ans,S[h][w])
print(H*W-ans)
### BUGGY CODE ###

import sys
from operator import mul
from functools import reduce


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


n = int(input())
l = [int(x) for x in input().split()]

cl = [0 for i in range(n)]
ll = [x for x in set(l) if l.count(x) > 1]

sum = 0
for i in ll:
    m = l.count(i)
    nc = combinations_count(m, 2)
    sum += nc

for i in l:
    print(sum-(l.count(i)-1))

### FIXED CODE ###

import collections

def combinations_count(n, r):
    return n * (n-1) // r


n = int(input())
l = [int(x) for x in input().split()]

l1 = []
l2 = []
c = collections.Counter(l)

total = sum([combinations_count(i, 2) for i in c.values()])

for a in l:
    print(total-combinations_count(c[a], 2)+combinations_count(c[a]-1, 2))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

i = 0
flag = 0
while(i<N-1):
  for j in range(1,len(A)):
    if(A[0]==A[j]):
      flag = 1
      break
  if(flag == 1):
    break
  else:
    A.pop(0)
  i += 1
if(flag == 1):
  print("NO")
else:
  print("YES")

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

A.sort()
flag = 0
for i in range(N-1):
  if(A[i]==A[i+1]):
    flag = 1
    break
if(flag == 1):
  print("NO")
else:
  print("YES")
### BUGGY CODE ###

if __name__ == "__main__":
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    for i in range(M):
        A[A.index(max(A))] = A[A.index(max(A))] // 2
    
    print(sum(A))
    

### FIXED CODE ###

import heapq

if __name__ == "__main__":
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A = [(-x, x) for x in A]
    heapq.heapify(A)

    for i in range(M):
        tmp = heapq.heappop(A)
        v = tmp[1] // 2
        heapq.heappush(A, (-v, v))
    
    res = 0
    for i in range(len(A)):
        res += A[i][1]
    
    print(res)
### BUGGY CODE ###

N,start = [int(x) for x in input().split()]
_x = [int(y) for y in input().split()]
x = sorted(_x)
dis = [0 for z in range(N-1)]
mark = [False for z in range(N)]
if N == 1:
    print(abs(x[0]-start))
else:
    for i in range(N-1):
        dis[i] = x[i+1] - x[i]
    D = min(dis)
    ans = 1
    for d in range(1,D+1):
        cite = start
        while True:
            if cite > x[N-1]:
                break
            if cite in x:
                mark[x.index(cite)] = True
            cite += d
        cite = start
        while True:
            if cite < x[0]:
                break
            if cite in x:
                mark[x.index(cite)] = True
            cite -= d
        if all(mark):
            ans = d
        mark = [False for z in range(N)]
    print(ans)


### FIXED CODE ###

import math
N,start = [int(x) for x in input().split()]
_x = [int(y) for y in input().split()]
x = [0 for y in range(N)]
for i in range(N):
    x[i] = abs(_x[i] - start)
g = x[0]
for i in range(N):
    g = math.gcd(g,x[i])
print(g)
ans = 1
### BUGGY CODE ###

from itertools import product

N = int(input())
added = set()
ans = []
a = [[i for i in range(j)] for j in range(1,N+1)]
for x in product(*a):
    count = 0
    appeared = set()
    temp = []
    order = [float('inf')] * N
    for y in x:
        if y not in appeared:
            order[y] = 97 + count
            count += 1
            appeared.add(y)
            temp.append(chr(order[y]))
        else:
            temp.append(chr(order[y]))
    s = ''.join(temp)
    if s not in added:
        ans.append(s)
        added.add(s)
print('\n'.join(ans))

### FIXED CODE ###

def dfs(s,n):
    if len(s) == n:
        print(s)
    else:
        for i in range(len(set(s))+1):
            dfs(''.join([s,chr(97+i)]),n)

N = int(input())
dfs('a',N)
### BUGGY CODE ###

# import numpy as np
from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]
# Cost = np.full((H,W),MAX_COST)

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

# used = set()
five_five = [ (i,j) for i in range(-2,3,1) for j in range(-2,3,1) ]
ffCosts = {}
for i,j in five_five:
	# print(i,j)
	if (j == 0 and (i==1 or i==-1)) or (i==0 and (j==1 or j==-1)):
		ffCosts[(i,j)] = 0
	else:
		ffCosts[(i,j)] = 1
# print(five_five)

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in five_five:
		# print(i,j)
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.':
				cAdd = ffCosts[(i,j)]
				if c + cAdd < Cost[h+i][w+j]:
					Cost[h+i][w+j] = c + cAdd
					if cAdd == 0:
						deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
					else:
						deq.append((h+i,w+j,Cost[h+i][w+j]))

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])

### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

walk=[(1,0),(0,1),(-1,0),(0,-1)]

# used = set()

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in walk:
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.' and c < Cost[h+i][w+j]:
				Cost[h+i][w+j] = c
				# print("updl ", i,j,h+i,w+j,c)
				deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
	for i in range(-2,3,1):
		for j in range(-2,3,1):
			# print(i,j)
			if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
				if S[h+i][w+j] == '.':
					if c + 1 < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c + 1
						deq.append((h+i,w+j,Cost[h+i][w+j]))
						# print("updr ", h+i,w+j,Cost[h+i][w+j])

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])
### BUGGY CODE ###

import itertools
import numpy as np

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]
ans = 0
A = [1 for i in range(N)]
for A in np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N))):
  score = 0
  for i in range(Q):
    if A[abcd[i][1]-1] - A[abcd[i][0]-1] == abcd[i][2]:
      score += abcd[i][3]
  ans = max(ans,score)
print(ans)


### FIXED CODE ###

import itertools
import numpy
N, M, Q = map(int,input().split())
abcd = []*Q
d_list = []
sum_d = 0
for _ in range(Q):
  abcd.append(list(map(int,input().split())))

A = [1 for i in range(N)]
for A in itertools.combinations_with_replacement(range(1, M+1), N):
  for i in range(Q):
    if A[abcd[i][1]-1]-A[abcd[i][0]-1] == abcd[i][2]:
      d_list.append(abcd[i][3])
  if sum_d <= sum(d_list):
    sum_d = sum(d_list)
  d_list.clear()
print(sum_d)
### BUGGY CODE ###

S = input()
N = len(S)

W = [i for i, x in enumerate(S) if x == 'W']
B = [i for i, x in enumerate(S) if x == 'B']

print(sum([len([b for b in B if b < w]) for w in W]))


### FIXED CODE ###

S = input()
N = len(S)

# W = [i for i, x in enumerate(S) if x == 'W']
# B = [i for i, x in enumerate(S) if x == 'B']
#
# print(sum([len([b for b in B if b < w]) for w in W]))

dp = [0] * (N + 1)
ans = 0
for i in range(1, N + 1):
    if S[i-1] == 'B':
        dp[i] = dp[i-1] + 1
    else:
        dp[i] = dp[i-1]
        ans += dp[i]

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

import math

N, P = list(map(int, input().split()))

now_max = 1

for i in range(round(math.pow(P, 1 / N)) + 1, 0, -1):
    if P % (i ** N) == 0:
        now_max = i
        break

print(now_max)

### FIXED CODE ###

n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    for i in range(1, round(p**(1/n))+1):
        if p % i**n ==0:
            res = i
    print(res)
### BUGGY CODE ###

N = int(input())

A = [list(map(int, input().split())) for _ in range(N)]

# check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
check = [0] * N #i番目の次の相手のindex

ans = 0
i = 0
tmp = 0
count = 0
while tmp < 2 * N + 5:
    if i % N == 0:
        ans += 1
        flag  = [True] * N #試合をしたかどうかチェック
        i = 0
    if check[i] >= N - 1:
        i += 1
        tmp += 1
        continue
    if flag[i] == False: #試合済みのとき
        i += 1
        tmp += 1
        continue
    b = A[i][check[i]]
    # print (b)
    if A[b - 1][check[b - 1]] - 1 == i and flag[b - 1] == True: #試合できる時
        check[i] += 1
        check[b - 1] += 1
        flag[i] = False
        flag[b - 1] = False
        tmp = 0
        count += 1
    i += 1
    tmp += 1
    if count == (N * (N - 1))//2:
        break
    # print (check)

# print (check)
for i in check:
    if i != N - 1:
        print (-1)
        exit()

print (ans)
        



### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
B = {i: row for i, row in enumerate(A)}

# print (A)
# print (B)

end = 0

for k in range(8000):
    used = set()
    dels = []
    for i, q in B.items():
        if not q:
            continue
        if i in used:
            continue
        j = q[-1]
        if j in used:
            continue
        if A[j][-1] == i:
            A[j].pop()
            A[i].pop()
            used.add(i)
            used.add(j)
            if not A[i]:
                end += 1
                dels.append(i)
            if not A[j]:
                end += 1
                dels.append(j)
    if not used:
        print (-1)
        exit()
    
    if end == N:
        print (k + 1)
        exit()
    
    for i in dels:
        del B[i]
        
print (N * (N - 1) // 2)
### BUGGY CODE ###

import sys
def solve(mid):
    l=k
    for b,g in zip(a,f):
        if b*g>mid:
            l-=b-mid//g
            if l<0:return False
    return True
input=sys.stdin.buffer.readline
n,k=map(int,input().split())
a=sorted(map(int,input().split()))[::-1]
f=sorted(map(int,input().split()))
ok=10**12
ng=-1
while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if solve(mid):ok=mid
    else:ng=mid
print(ok)

### FIXED CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    a,f=sorted(a[:n])[::-1],sorted(a[n:])
    ok=10**12
    ng=-1
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        l=k
        for b,g in zip(a,f):
            if b*g>mid:
                l-=b-mid//g
        if l<0:ng=mid
        else:ok=mid
    print(ok)
main()
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N, K = MAP()
	A = LIST()
	F = LIST()

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

	time = [A[i]*F[i] for i in range(N)]
	# print(F)
	# print(time)
	upper = max(time)

	def is_ok(x):  # 時間をx以下にできるか？
		tmp = 0
		for i in range(N):
			if time[i] <= x:
				continue
			else:
				tmp += ceil((time[i]-x)/F[i])
			if tmp > K:
				return False
		else:
			return True

	min_ = -1
	max_ = upper
	while min_ + 1 != max_:
		search = (min_+max_)//2
		# print(min_, max_, search)
		if is_ok(search):
			max_ = search
		else:
			min_ = search

	print(max_)


if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()
F = LIST()

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

time = [A[i]*F[i] for i in range(N)]
# print(F)
# print(time)

def is_ok(x):  # 時間をx以下にできるか？
	tmp = 0
	for i in range(N):
		if time[i] <= x:
			pass
		else:
			tmp += ceil((time[i]-x)/F[i])
	if tmp > K:
		return False
	else:
		return True

min_ = -1
max_ = 10**18
while min_ + 1 != max_:
	search = (min_+max_)//2
	# print(min_, max_, search)
	if is_ok(search):
		max_ = search
	else:
		min_ = search

print(max_)