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

from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
import heapq
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]

def main():
    from builtins import int, map
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Ch, Cw, Dh, Dw = Ch - 1, Cw - 1, Dh - 1, Dw - 1
    S = [list(input()) for _ in range(H)]

    dist = defaultdict(lambda: float("inf"))
    dist[Ch, Cw] = 0
    queue = deque([(Ch, Cw)])

    while queue:
        (h, w) = queue.popleft()

        for i in range(4):
            dhi, dwi = dh[i], dw[i]
            nh, nw = h + dhi, w + dwi
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                if dist[h, w] < dist[nh, nw] :
                    dist[nh, nw] = dist[h, w]
                    queue.appendleft((nh, nw))
        
        # 5x5-grid
        for ddh in range(-2, 3):
            for ddw in range(-2, 3):
                nh, nw = h + ddh, w + ddw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                    if dist[nh, nw] > dist[h, w] + 1:
                        dist[nh, nw] = dist[h, w] + 1
                        queue.append((nh, nw))

    if dist[Dh, Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh, Dw])

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque
INF = int(1e10)

def main():
    from builtins import int, map
    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    S = [input() for _ in range(H)]

    # dist = defaultdict(lambda: float("inf"))
    dist = [[float("inf")] * W for _ in range(H)]
    queue = deque([(Ch, Cw, 0)])

    while queue:
        (h, w, d) = queue.popleft()

        if dist[h][w] == float("inf") or dist[h][w] > d:
            dist[h][w] = d
            
            # 5x5-grid
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nh, nw = h + ddh, w + ddw
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                        # cost-0 move
                        if abs(ddh) + abs(ddw) <= 1:
                            queue.appendleft((nh, nw, d))
                        # cost-1 move
                        else:
                            queue.append((nh, nw, d + 1))

    if dist[Dh][Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh][Dw])

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

from collections import Counter
N = int(input())
factors = []
i = 2
while N > 1:
  if N < i * i:
    factors.append(N)
    break
  while N % i == 0:
    factors.append(i)
  i += 1

ans = 0
for count in Counter(factors).values():
  i = 1
  while count >= i:
    count -= i
    i += 1
    ans += 1
print(ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
factors = []
i = 2
while N > 1:
  if N < i * i:
    factors.append(N)
    break
  while N % i == 0:
    factors.append(i)
    N //= i
  i += 1

ans = 0
for count in Counter(factors).values():
  i = 1
  while count >= i:
    count -= i
    i += 1
    ans += 1
print(ans)
### BUGGY CODE ###

import sys

def longestcommonsubsequence(seq1, seq2):
    a,b = len(seq1), len(seq2)
    length = [[0 for i in range(b+1)] for j in range(a+1)]

    for i in range(a):
        e1 = seq1[i]
        tmp = length[i]
        x = [0 for i2 in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x[j+1]=tmp[j] + 1
            else:
                x[j+1]=max(tmp[j+1], x[j])
        length[i+1]=x
    return length[a][b]

n = input()
for i2 in range(n):
    seq1 = raw_input()
    seq2 = raw_input()

    print longestcommonsubsequence(seq1, seq2)

### FIXED CODE ###

import sys

def longestcommonsubsequence():
    seq1 = raw_input()
    seq2 = raw_input()

    a, b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1+[]
        #x1 = [0 for i2 in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1]<x1[j]:
                x1[j+1] = x1[j]
    return x1[-1]

n = input()
for i2 in range(n):

    print longestcommonsubsequence()
### BUGGY CODE ###

from collections import Counter
n = int(input())
a=list(map(int,input().split()))
c=Counter(a)
for i in range(n):
    ans = 0
    tmp = a[i]
    for b,j in c.items():
        if b == tmp:
            ans += ((j-1)*(j-2))//2
        else:
            ans += (j*(j-1))//2
    print(ans)
    

### FIXED CODE ###

from collections import Counter
n = int(input())
a=list(map(int,input().split()))
c=Counter(a)
sum = 0
for i in c.values():
    sum += i*(i-1)//2

for i in a:
    if c[i] > 0:
        print(sum-(c[i]-1))
### BUGGY CODE ###

ab=[]
n,m = map(int,input().split())


for i in range(m):
    ab.append(tuple(map(int,input().split())))

enabled=set()
remain=set([i for i in range(m)])

res=0
for i in range(1,n+1):
    for j in remain-enabled:
        if i == ab[j][0]:
            enabled.add(j)
    for j in enabled:
        if i == ab[j][1]-1 and j in remain:
            res+=1
            remain-=enabled
            enabled=set()
            break

print(res)

### FIXED CODE ###

ab=[]

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

for i in range(m):
    ab.append(tuple(map(int,input().split())))

ab.sort(key=lambda x:x[1])

res=0
for z in range(len(ab)):
    x=ab[0][1]
    for j in range(len(ab)):
        if x > ab[0][0]:
            del ab[0]
        else:
            res+=1
            break
    if len(ab)==0:
        res+=1
        break
    
print(res)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n):
    b.append(a[i])
    b.reverse()
print(*b)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
if n%2==1:
    print(*(a[::-2]+a[1::2]))
if n%2==0:
    print(*(a[::-2]+a[0::2]))
### BUGGY CODE ###


S = input()
l = len(S)
S = S[::-1]
dp =[[0 for _ in range(13) ] for _ in range(l + 1)]
amari = dict(zip( list(range(0,13)),[0] *13 ))
kurai = 1
MOD = (10 ** 9) + 7
dp[0][0] = 1

for keta,c in  enumerate(S):

    if c == "?":
        for j in range(0,10):
            temp = (j * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13] += dp[keta][i]
                dp[keta + 1][(temp + i) % 13] %= MOD
    else:
        temp = (int(c) * kurai) % 13
        for i in range(13):
            dp[keta + 1][(temp + i) % 13]  += dp[keta][i]
            dp[keta + 1][(temp + i) % 13] %= MOD
    kurai *= 10
    keta %= MOD
print(dp[-1][5] % MOD)

### FIXED CODE ###


import sys

S =  sys.stdin.readline()[:-1]
l = len(S)
# S = S[::-1]
S = list(reversed(S))

dp =[[0 ] * 13 for _ in range(l + 1)]
kurai = 1
MOD = (10 ** 9) + 7
dp[0][0] = 1

for keta in range(len(S)):
    c =S[keta]

    if c == "?":
        for j in range(0,10):
            kurai %= 13
            temp = (j * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13] += (dp[keta][i] )
                dp[keta + 1][(temp + i) % 13] %= MOD
    else:
        kurai %= 13

        temp = (int(c) * kurai) % 13
        for i in range(13):
            dp[keta + 1][(temp + i) % 13]  += (dp[keta][i] )
            dp[keta + 1][(temp + i) % 13] %= MOD
    kurai *= 10
    keta %= MOD
print(dp[-1][5] )
### BUGGY CODE ###

def main():
    from fractions import gcd
    import sys
    input = sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    # n,*a=map(int,open(0).read().split())
    mod=10**9+7
    b=a[0]
    for i in a:
        if b%i!=0:
            b=b*i//gcd(b,i)
    ans=0
    for i in a:
        ans+=b//i
        ans%=mod
    print(ans)    
    # print(sum(b//i%mod for i in a)%mod)    
if __name__ == '__main__':
    main()

### FIXED CODE ###

from fractions import *
n,*a=map(int,open(0).read().split())
b=1
for i in a:b*=i//gcd(b,i)
print(sum(b//i for i in a)%(10**9+7))
### BUGGY CODE ###

import bisect
def main():
    n,m,l=map(int,input().split(' '))
    g=[[float('inf')if i != j  else 0  for i in range(n)] for j in range(n)]
    for i in range(m):
        a,b,c=map(int,input().split(' '))
        if c <=l:
            g[a-1][b-1]=c
            g[b-1][a-1]=c
    q=int(input())
    q_list=[tuple(map(int,input().split(' '))) for i in range(q)]
    for k in range(n):
        for i in range(n):
            for j in range(i,n):
                g[i][j]= min(g[i][j],g[i][k]+g[k][j])
                g[j][i]=g[i][j]

    for i in range(n):
        for j in range(n):
            if g[i][j]<=l:
                if g[i][j] != 0:
                    g[i][j] = 1
                else:
                    g[i][j] = 0
            else:
                g[i][j] = float('inf')

    for k in range(n):
        for i in range(n):
            for j in range(n):
                g[i][j] = min(g[i][j],g[i][k]+g[k][j])
    for i,j in q_list:
        if g[i-1][j-1] != float('inf'):
            print(g[i-1][j-1]-1)
        else:
            print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import bisect
def main():
    n,m,l=map(int,input().split(' '))
    g=[[float('inf')if i != j  else 0  for i in range(n)] for j in range(n)]
    for i in range(m):
        a,b,c=map(int,input().split(' '))
        if c <=l:
            g[a-1][b-1]=c
            g[b-1][a-1]=c
    q=int(input())
    q_list=[tuple(map(int,input().split(' '))) for i in range(q)]
    for k in range(n):
        for i in range(n):
            for j in range(i,n):
                g[i][j]= min(g[i][j],g[i][k]+g[k][j])
                g[j][i]=g[i][j]

    for i in range(n):
        for j in range(n):
            if g[i][j]<=l:
                if g[i][j] != 0:
                    g[i][j] = 1
                else:
                    g[i][j] = 0
            else:
                g[i][j] = float('inf')

    for k in range(n):
        for i in range(n):
            for j in range(n):
                g[i][j] = min(g[i][j],g[i][k]+g[k][j])
    for i,j in q_list:
        if g[i-1][j-1] != float('inf'):
            print(g[i-1][j-1]-1)
        else:
            print(-1)


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

n, k = map(int, input().split())
scores = list(map(int, input().split()))

evals = []
eval = scores[0:k]
for i in range(k, n, 1):
    new = scores[i-k+1:i+1]
    if eval[0] < new[-1]:
        evals.append('Yes')
    else:
        evals.append('No')
    eval = new

for ans in evals:
    print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
scores = list(map(int, input().split()))

evals = []
cnt = 0

for i in range(k, n, 1):
    edge = scores[cnt]
    new_edge = scores[i]
    if edge < new_edge:
        print('Yes')
    else:
        print('No')
    cnt += 1
### BUGGY CODE ###

MOD = 10 ** 9 + 7

N, M = map(int, input().strip().split())
S = [int(i) for i in input().strip().split()]
T = [int(i) for i in input().strip().split()]

sdp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

for i, s in enumerate(S):
  for j, t in enumerate(T):
    v = sdp[i][j + 1] + sdp[i + 1][j]
    if s == t:
      v += 1
    else:
      v -= sdp[i][j]
    sdp[i + 1][j + 1] = v % MOD

print(sdp[-1][-1] + 1)

### FIXED CODE ###

MOD = 10 ** 9 + 7


def main(S, T):
  l = len(T) + 1
  dp = [0] * l
  # sdp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

  # for i, s in enumerate(S):
  #  for j, t in enumerate(T):
  #    v = sdp[i][j + 1] + sdp[i + 1][j] + (1 if s == t else -sdp[i][j])
  #    sdp[i + 1][j + 1] = v % MOD
  for i, s in enumerate(S):
    tmp = [0] * l
    for j, t in enumerate(T):
      v = dp[j + 1] + tmp[j] + (1 if s == t else -dp[j])
      tmp[j + 1] = v % MOD
    dp = tmp

  # return (sdp[-1][-1] + 1)
  return dp[-1] + 1


if __name__ == '__main__':
  if True:
    _, _ = map(int, input().strip().split())
    S = input().strip().split()
    T = input().strip().split()
  else:
    S = range(1000)
    T = range(1000)
  print(main(S, T))
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
counter = 0
r_max = N//R+1
g_max = N//G+1
for r in range(r_max+1):
  for g in range(g_max+1):
    if (N - R*r - G*g)% B == 0 and (N - R*r -G*g)//B >= 0:
      counter +=1
print(counter)
  

### FIXED CODE ###

R, G, B, N = map(int, input().split())
counter = 0
r_max = N//R+1
for r in range(r_max+1):
  temp = N - R*r
  for g in range(temp//G+1):
    now = temp - G*g
    if now% B == 0 and now//B >= 0:
      counter +=1
print(counter)
### BUGGY CODE ###

NKQ = input().split(' ')
N = int(NKQ[0])
K = int(NKQ[1])
Q = int(NKQ[2])

An = [K] * N

for _ in range(Q):
    A = int(input()) 
    for i in range(N):
        An[i] -= 1
    An[A-1] += 1

for i in range(N):
    if An[i] > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

NKQ = input().split(' ')
N = int(NKQ[0])
K = int(NKQ[1])
Q = int(NKQ[2])

Bn = [0] * N
for _ in range(Q):
    A = int(input()) 
    Bn[A-1] += 1

for i in range(N):
    if K - Q + Bn[i]  > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
AGC028 C
"""

import itertools

n = int(input())
abli0 = [tuple(map(int, input().split())) for i in range(n)]
eabli0 = enumerate(abli0)
abli1 = list(map(lambda t: ((t[1][0], t[0], 0), (t[1][1], t[0], 1)), eabli0))
abli = list(itertools.chain.from_iterable(abli1))
abli.sort(key=lambda t: t[0])
tmpans0 = sum(map(lambda t: t[0], abli[:n]))
alist = []
blist = []
for x, i, aorb in abli[:n]:
    if not aorb:
        alist.append(i)
    else:
        blist.append(i)

flag = False
for i in range(n):
    if i in alist and i in blist:
        flag = True
        break

y, j, arob2 = abli[n]
z, k, arob3 = abli[n+1]
if flag:
    tmpans = tmpans0
else:
    tmpans = 2**62
    for x, i, aorb in abli[:n]:
        if j != i:
            tmp = tmpans0-x+y
        else:
            tmp = tmpans0-x+z
        if tmpans > tmp:
            tmpans = tmp

leftsum = sum(map(lambda x: x[0], abli0))
rightsum = sum(map(lambda x: x[1], abli0))

print(min(leftsum, rightsum, tmpans))


### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
AGC028 C
"""

from operator import itemgetter

n = int(input())
abli = []
for i in range(n):
    a, b = map(int, input().split())
    abli.append((a, i, 0))
    abli.append((b, i, 1))

abli.sort(key=itemgetter(0))
tmpans0 = sum(map(itemgetter(0), abli[:n]))
aiset = set([i for x, i, aorb in abli[:n] if not aorb])
biset = set([i for x, i, aorb in abli[:n] if aorb])
flag = bool(set.intersection(aiset, biset))


y, j, arob2 = abli[n]
z, k, arob3 = abli[n+1]

if flag:
    tmpans = tmpans0
else:
    min1 = y-max([x for x, i, aorb in abli[:n] if j != i])
    min2 = z-max([x for x, i, aorb in abli[:n] if j == i])
    tmpans = tmpans0 + min(min1, min2)

leftsum = sum([aa for aa, i, aorb in abli if not aorb])
rightsum = sum([bb for bb, i, aorb in abli if aorb])

print(min(leftsum, rightsum, tmpans))
### BUGGY CODE ###

from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra
import numpy as np

N,M = map(int,input().split())
#V=[[] for _ in range(N)]
row=[]
col=[]
data=[1]*(M)
for _ in range(M):
    a,b = map(int, input().split())
    row.append(a-1)
    col.append(b-1)

s=0
graph=coo_matrix((data, (row, col)), shape=(N,N))
dist_matrix,predecessors = dijkstra(csgraph=graph, directed=False, indices = s, unweighted=True, return_predecessors=True)
#print(dist_matrix)
#print(predecessors)
print('Yes')
print(*[e+1 for e in predecessors[1:]],sep='\n')

### FIXED CODE ###

from collections import deque

N,M = map(int,input().split())
V=[[] for _ in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    V[a-1].append(b-1)
    V[b-1].append(a-1)
state=[0]*N
q=deque()
ans=[0]*(N)

state[0]=1
q.append(0)
while len(q) > 0:
    v=q.popleft()
    for u in V[v]:
        if state[u]==0:
            state[u]=1
            ans[u]=v+1
            q.append(u)
print('Yes')
print(*ans[1:],sep='\n')
### BUGGY CODE ###

from collections import Counter


n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
a = set(a)

cnt = 0
while a:
    min_val = min(a)
    a.remove(min_val)

    if c[min_val] == 1:
        cnt += 1

    if not a:
        break

    max_val = max(a)

    del_a = set()
    mul = 2
    while True:
        mul_val = min_val * mul

        if mul_val > max_val:
            break

        if mul_val in a:
            del_a.add(min_val * mul)

        mul += 1

    a -= del_a

print(cnt)


### FIXED CODE ###

from collections import Counter


n = int(input())
a = list(map(int, input().split()))
a.sort()
c = Counter(a)

flags = [True] * (a[-1] + 1)

for e in a:
    for mul in range(2, a[-1] // e + 1):
        flags[e * mul] = False

print(sum([flags[a[i]] and c[a[i]] == 1 for i in range(n)]))
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[6]:


N = int(input())
S = input()


# In[8]:


ans = N
for i in range(N+1):
    left = S[:i].count("#")
    right = S[i:].count(".")
    ans = min(ans, left+right)
print(ans)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[6]:


N = int(input())
S = input()


# In[9]:


w = S.count(".")
b = 0
ans = min(w,N-w)
for i in range(N):
    if S[i] == ".":
        w -= 1
    else:
        b += 1
    ans = min(ans, w+b)
print(ans)


# In[ ]:
### BUGGY CODE ###

h, w = map(int, input().split())
mat = []
for i in range(h):
  a = list(map(int, input().split()))
  mat.append(a)
for i in range(h):
  b = list(map(int, input().split()))
  for j in range(w):
    mat[i][j] = abs(mat[i][j]-b[j])

dp = [[[False]*(80*80*80) for i in range(w)] for k in range(h)]
dp[0][0][mat[0][0]] = True
for y in range(h):
  for x in range(w):
    if x > 0:
      for k in range(80**3):
        if dp[y][x-1][k]:
          dp[y][x][k+mat[y][x]] = True
          dp[y][x][abs(k-mat[y][x])] = True
    if y > 0:
      for k in range(80**3):
        if dp[y-1][x][k]:
          dp[y][x][k+mat[y][x]] = True
          dp[y][x][abs(k-mat[y][x])] = True
for k in range(80**3):
  if dp[h-1][w-1][k]:
    print(k)
    exit()


### FIXED CODE ###

h, w = map(int, input().split())
mat = []
for i in range(h):
  a = list(map(int, input().split()))
  mat.append(a)
for i in range(h):
  b = list(map(int, input().split()))
  for j in range(w):
    mat[i][j] = abs(mat[i][j]-b[j])
m = max(map(max, mat))
dp = [[0b0 for i in range(w)] for k in range(h)]
dp[0][0] |= 0b1 << mat[0][0]
for y in range(h):
  for x in range(w):
        if x > 0:
          dp[y][x] |= dp[y][x-1] << mat[y][x]
          dp[y][x] |= dp[y][x-1] >> mat[y][x]
          anded = dp[y][x-1] & int('1'*(mat[y][x]+1), 2)
          reverse = format(anded, "0"+str(mat[y][x]+1)+"b")[::-1]

          dp[y][x] |= int(reverse, 2)
        if y > 0:
          dp[y][x] |= dp[y-1][x] << mat[y][x]
          dp[y][x] |= dp[y-1][x] >> mat[y][x]
          anded = dp[y-1][x] & int('1'*(mat[y][x]+1), 2)
          reverse = format(anded, "0"+str(mat[y][x]+1)+"b")[::-1]

          dp[y][x] |= int(reverse, 2)
        #print(bin(dp[y][x]))

keta = 0
while dp[h-1][w-1] % 2 == 0:
  keta += 1
  dp[h-1][w-1] //= 2
print(keta)
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))

ans = 0
for i in range(n):
    count = -1
    for j in range(i+1):
        if p[i] <= p[j]:
            count += 1
    if count == i:
        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))

ans = 0
n_min = 0
for i in range(0,n):
    if i == 0:
        ans += 1
        n_min = p[i]
        continue
    if p[i] <= n_min:
        ans += 1
        n_min = p[i]
print(ans)
### BUGGY CODE ###

n,k,q = map(int,input().split())
d = [int(input()) for i in range(q)]

p=[k]*n

for a in range(0,q):
  for x in range(0,n):
    p[x]-=1
  p[d[a]-1]+=1

for l in range(0,n):
  if p[l]>0:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

import numpy as np

n,k,q = map(int,input().split())
d = [int(input()) for i in range(q)]
 
p=np.full(n,k)
z=np.full(n,-1*q)

p=p+z

for a in range(0,q):
  p[d[a]-1]+=1
 
for l in range(0,n):
  if p[l]>0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

n = int(input())
s = input()
ret = 0
for d in range(1, n - 1):
    l = 0
    for i in range(n - d):
        if s[i] == s[i + d]:
            l += 1
        else:
            l = 0
        ret = max(ret, min(l, d))
print(ret)

### FIXED CODE ###

n = int(input())
s = input()
ret = 0
for d in range(1, n - 1):
    l = 0
    for i in range(n - d):
        if s[i] == s[i + d]:
            l += 1
        else:
            l = 0
        ret = max(ret, min(l, d))
print(ret)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
def check(tmp):
    k = 0
    for x, y in zip(A, F):
        k += max(0, x - (tmp // y))
    return(K >= k)
A.sort()
F.sort(reverse=True)

r = A[-1]*F[0]
l = -1

while(r-l > 1):
    tmp = (l+r)//2
    if check(tmp):
        r = tmp
    else:
        l = tmp
print(r)


### FIXED CODE ###

import sys
import bisect
import math
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

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

B = [(A[i]*F[i], F[i]) for i in range(N)]
B.sort(reverse=True)
L = 0
R = B[0][0]
if sum(A) <= K:
    print(0)
    exit(0)
while(1):
    ans = (L+R) // 2
    flag = True
    tmp = 0
    for i in range(N):
        tmp += math.ceil(max(B[i][0] - ans, 0) / B[i][1])
        if tmp > K:
            flag = False
            break
    if flag:
        R = ans
    else:
        L = ans
    if L == R or L+1 == R:
        print(R)
        break
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [False] * n
for i in range(n):
    for j in range(i+1, i+k+1):
        if j == n:
            break
        if dp[j] == False:
            dp[j] = dp[i] + abs(h[j] - h[i])
        else:
            dp[j] = min(dp[j], dp[i] + abs(h[j] - h[i]))
print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [pow(10, 9)] * n
dp[0] = 0
for i in range(n):
    for j in range(i+1, i+k+1):
        if j == n:
            break
        dp[j] = min(dp[j], dp[i] + abs(h[j] - h[i]))
print(dp[-1])
### BUGGY CODE ###

N = int(input())
lst = sorted(list(map(int, input().split())))
ret = 0
for idx_a, a in enumerate(lst[:-2]):
    for idx_b, b in enumerate(lst[idx_a + 1:-1]):
        for idx_c, c in enumerate(lst[idx_a + idx_b + 2:]):
            if a < b + c and b < c + a and c < a + b:
                ret += 1
            else:
                break
print(ret)

### FIXED CODE ###

import bisect

N = int(input())
lst =list(map(int, input().split()))
lst.sort()
ret = 0
for i in range(N):
    for j in range(i + 1, N):
        n = lst[i] + lst[j]
        idx = bisect.bisect_left(lst, n)
        ret += max(0, idx - j - 1)
print(ret)
### BUGGY CODE ###

N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
for i in range(N):
    w[i], v[i] = [int(i) for i in input().split()]

dp = [[-float('inf')]*(W+1) for i in range(N+1)]
for i in range(W+1):
    dp[0][i] = 0

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

### FIXED CODE ###

N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
for i in range(N):
    w[i], v[i] = [int(i) for i in input().split()]

dp = [[-float('inf')]*(W+1) for i in range(N+1)]
for i in range(W+1):
    dp[0][i] = 0

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