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

N, K = map(int,input().split())
p = list(map(int,input().split()))

mev = 0
idx = 0

for i in range(N-K+1):
    ev = sum(p[i:i+K])

    if ev > mev:
        idx = i
        mev = ev

ev = 0

for i in range(idx, idx+K):
    ev += ((p[i] + 1.0) / 2.0)

print(ev)

### FIXED CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))

#累積和を前計算
sum_list = [0 for _ in range(300000)]
sum = 0

for i in range(len(p)):
    sum += p[i]
    sum_list[i] = sum

#答えを計算
mev = 0
idx = 0
for i in range(N-K+1):
    ev = sum_list[i+K]-sum_list[i]
    if ev > mev:
        idx = i
        mev = ev

mev = 0.0
if N != K:
    for i in range(idx+1,idx+1+K):
        mev += (p[i] + 1.0) / 2.0

else:
    for i in range(len(p)):
        mev += (p[i] + 1.0) / 2.0

print(mev)
### BUGGY CODE ###

N = int(input())

for n in range(1, N+1):
  count = 0
  for i in range (1, 101):
    for j in range(1, 101):
      for k in range(1, 101):
        if i*i+j*j+k*k+i*j+j*k+k*i == n:
          count += 1

  print(count)



### FIXED CODE ###

N = int(input())
ans = [0] * (N + 1)
for i in range (1, 101):
  for j in range(1, 101):
    for k in range(1, 101):
      n = i*i+j*j+k*k+i*j+j*k+k*i
      if n <= N:
        ans[n] += 1

print(*ans[1:], sep='\n')
### BUGGY CODE ###

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

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        s.append(b)
    elif b == n:
        g.append(a)

for i in s:
    if i in g:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')



### FIXED CODE ###

n, m = map(int, input().split())
l = [0]*n

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        l[b] += 1
    elif b == n:
        l[a] += 1

for i in l:
    if i >= 2:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')
### BUGGY CODE ###

from collections import deque
n = int(input())
edges = {}
lst = [set()for i in range(n)]
vert = [set() for i in range(n)]
ans = [0 for i in range(n-1)]
for i in range(n-1):
    a,b = map(int,input().split())
    lst[a-1].add(b)
    lst[b-1].add(a)
    if a > b:
        a,b = b,a
    edges[(a,b)] = i
q = deque([1])
while q:
    x = q.popleft()
    q.extend(lst[x-1])
    while lst[x-1]:
        i = lst[x-1].pop()
        lst[i-1].discard(x)
        a = min(x,i)
        b = max(x,i)
        for j in range(1,n):
            if not (j in vert[x-1] or j in vert[i-1]):
                vert[x-1].add(j)
                vert[i-1].add(j)
                ans[edges[(a,b)]] = j
                break
print(max(ans))
for i in range(len(ans)):
    print(ans[i])


### FIXED CODE ###

n = int(input())
graph = [[] for _ in range(n+1)]
for i in range(1,n):
    a,b = map(int,input().split())
    graph[a].append((i,b))
    graph[b].append((i,a))
colors = [0 for _ in range(n)]
parents = [0]*(n+1)
stack = [(1,0)]
while stack:
    x,c = stack.pop()
    color = 1
    for i,y in graph[x]:
        if parents[x] == y:
            continue
        else:
            parents[y] = x
            if color == c:
                color += 1
            colors[i] = color
            stack.append((y,color))
            color += 1
print(max(colors))
for i in range(1,n):
    print(colors[i])
### BUGGY CODE ###

n = int(input())
hantei_list = [1 for _ in range(n)]
moji_list = [str(input()) for _ in range(n)]
prime_number = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
for i in range(n):
  for j in range(10):
    hantei_list[i] *= prime_number[ord(moji_list[i][j])- ord('a')]

unique = set(hantei_list)

counter = 0
for i in unique:
  temp = hantei_list.count(i)
  counter += temp * (temp - 1) * 0.5 
print(int(counter))

### FIXED CODE ###

n = int(input())
hantei_list = [1 for _ in range(n)]
moji_list = [str(input()) for _ in range(n)]
prime_number = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
for i in range(n):
  for j in range(10):
    hantei_list[i] *= prime_number[ord(moji_list[i][j])- ord('a')]

# unique = set(hantei_list)
appeared = dict()

counter = 0
for i in hantei_list:
  if not i in appeared:
    appeared[i] = 1
  else:
    counter += appeared[i]
    appeared[i] += 1
print(counter)
### BUGGY CODE ###

def GCD(a:int , b: int) -> int:
    return a if b == 0 else GCD(b, a % b)

from collections import defaultdict
def factorize(n: int) -> dict:
    f = defaultdict(int)
    p = 2
    while n > 1:
        while n % p == 0:
            f[p] += 1
            n = n // p
        p += 1 if p == 2 else 2
    return f

a, b = map(int, input().split())
factors = factorize(GCD(a, b))

ans = len(factors) + 1

print(ans)


### FIXED CODE ###

def GCD(a:int , b: int) -> int:
    return a if b == 0 else GCD(b, a % b)

def get_divisor(n: int) -> list:
    divisor = []
    for i in range(1, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            divisor.append(i)
            if i != n // i:
                divisor.append(n // i)
    divisor.sort()
    return divisor

a, b = map(int, input().split())
divisor =  get_divisor(GCD(a, b))

ans = 1
used = [0] * len(divisor)
used[0] = 1
for i in range(1, len(divisor)):
    if used[i] == 0:
        ans += 1
        for j in range(i+1, len(divisor)):
            if used[j] == 0 and divisor[j] % divisor[i] == 0:
                used[j] = 1

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

s = input()

ans = 0

z = [[0]*4 for i in range(len(s))]

for i in range(1,len(s)-1):
    z[i][0] = z[i - 1][0]
    z[i][1] = z[i - 1][1]
    if s[i-1]=='A':
        z[i][0] +=1
    elif s[i-1]=='?':
        z[i][1] += 1

for i in range(1,len(s)-1):
    z[-i-1][2] = z[-i][2]
    z[-i-1][3] = z[-i][3]
    if s[-i]=='C':
        z[-i-1][2] += 1
    elif s[-i] =='?':
        z[-i-1][3] += 1


for i in range(1,len(s)-1):
    if s[i]=='B' or s[i]=='?':
        x = z[i][1]
        a = z[i][0]
        a1 = 3*a+x
        a2 = 3**(x-1)%(10**9+7)
        y = z[i][3]
        c = z[i][2]
        c1 = 3*c+y
        c2 = 3**(y-1)%(10**9+7)
        ans += (a1*a2*c1*c2)%(10**9+7)
    ans %=(10**9+7)

print(int(ans))

### FIXED CODE ###

s = input()

ans = 0

rc = [0]
rq = [0]
la = [0]
lq = [0]
q3 = [1]
t = 10**9+7

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
        rq.append(rq[-1])
    elif s[len(s)-i-1]=='?':
        rc.append(rc[-1])
        rq.append(rq[-1]+1)
    else:
        rc.append(rc[-1])
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
        lq.append(lq[-1])
    elif s[i]=='?':
        la.append(la[-1])
        lq.append(lq[-1]+1)
    else:
        la.append(la[-1])
        lq.append(lq[-1])
    q3.append(q3[-1] * 3 % t)
rc.reverse()
rq.reverse()

q3.append(1/3)

for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        l = q3[lq[i]-1]
        r = q3[rq[i]-1]
        ans += l*r*(3*la[i]+lq[i])*(3*rc[i]+rq[i]) % t

print(round(ans%t))
### BUGGY CODE ###

n = int(input())
a = [int(i)-1 for i in input().split()]
ans = []
for i in range(n):
    ans.append(str(a.index(i)+1))
print(" ".join(ans))

### FIXED CODE ###

n = int(input())
a = [[int(i)] for i in input().split()]
for i in range(n):
    a[i].append(i)
a.sort()
ans = ""
for i in range(n):
    ans += str(a[i][1]+1) + " "
print(ans)
### BUGGY CODE ###

A,B=map(int,input().split())
ans=A
for i in range(1,B-A+1):
    ans=ans^(A+i)
print(ans)

### FIXED CODE ###

A,B=map(int,input().split())
if A%2==0:
    d=B-A
    if d%4==0:
        print(B)
    elif d%4==1:
        print(1)
    elif d%4==2:
        print(1^B)
    else:
        print(0)
else:
    d=B-A-1
    if d%4==0:
        print(A^B)
    elif d%4==1:
        print(A^1)
    elif d%4==2:
        print(A^1^B)
    else:
        print(A^0)
### BUGGY CODE ###

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB = sorted(sorted(AB, key=lambda x: x[0], reverse=False), key=lambda x: x[1], reverse=True)
x = [0] * M
cnt = 0
cntIN = M
preB = 0
for a, b in AB:
    if preB != b:
        k = M
    i = min(M-a, k)
    while i>=0 and x[i] != 0:
        i -= 1
    else:
        if i >= 0:
            x[i] = b
            k = i - 1
            cntIN -= 1
            if cntIN <= 0:
                break

print(sum(x))


### FIXED CODE ###

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB = sorted(sorted(AB, key=lambda x: x[0], reverse=False), key=lambda x: x[1], reverse=True)
x = [0] * M
p = [x for x in range(M)]

cnt = 0
cntIN = M
for a, b in AB:
    i = M-a

    s = []
    while i >= 0 and p[i] != i:
        s.append(i)
        i = p[i]
    for j in s:
        p[j] = i - 1

    if i >= 0:
        x[i] = b
        p[i] = i - 1
        cntIN -= 1            
        if cntIN <= 0:
            break

print(sum(x))
### BUGGY CODE ###

def main():
    n, p = map(int, input().split())
    s = input()
    u = [int(s[i:]) for i in range(n)]
    mu = [None]*n
    ans = 0
    c = [0]*10000
    if 10%p == 0:
        for i in range(n):
            if int(s[i])%p == 0:
                ans += i+1
        print(ans)
        return
    for i, v in enumerate(u):
        m = v%p
        mu[i] = m
        c[m] += 1
    c[0] += 1
    for i in mu:
        c[i] -= 1
        ans += c[i]
        
    print(ans)
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    if 10%p == 0:
        ss = map(int, s)
        ss = list(ss)
        for i in range(n):
            if ss[i]%p == 0:
                ans += i+1
        print(ans)
        return
    sr = s[::-1]
    ssr = map(int, sr)
    tens = 1
    v = 0
    for i, si in enumerate(ssr):
        v = (v + (si%p)*tens)%p
        mu[i] = v
        c[v] += 1
        tens *= 10
        tens %= p
    c[0] += 1
    for i in c:
        if i:
            ans += ((i-1)*i)//2
        
    print(ans)
    

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

import itertools
import math
import functools

K = int(input())

ans = 0

for i in itertools.product(range(1,K+1),repeat=3):
    ans += functools.reduce(math.gcd,i)

print(ans)

### FIXED CODE ###

import itertools
import math
import functools

K = int(input())

ans = 0

for i in itertools.product(range(1,K+1),repeat=3):
    ans += functools.reduce(math.gcd,i)
print(ans)
### BUGGY CODE ###

import sys
n,m=map(int,input().split())
l=[[int(i) for i in l.split()] for l in sys.stdin]
s=[[0] for i in range(10**5+1)]
for i in l:
  s[i[0]].append(i[1])
for i in range(len(s)):
  if len(s[i])>2:
    s[i].sort()
for i in l:
  print('{:06}{:06}'.format(i[0],s[i[0]].index(i[1])))

### FIXED CODE ###

import sys
import bisect
n,m=map(int,input().split())
l=[[int(i) for i in l.split()] for l in sys.stdin]
s=[[0] for i in range(10**5+1)]
for i in l:
  s[i[0]].append(i[1])
for i in range(len(s)):
  s[i].sort()
for i in l:
  print('{:06}{:06}'.format(i[0],bisect.bisect_left(s[i[0]],i[1])))
### BUGGY CODE ###

N=int(input())
A=[int(input()) for _ in range(N)]
B=list(set(A))
ct=0
for i in range(len(B)):
    if A.count(B[i])%2==0:
        ct+=1
print(len(B)-ct)


### FIXED CODE ###

from collections import Counter
N=int(input())
A=[int(input()) for _ in range(N)]
X=Counter(A)
ans=0
for i in X.values():
    if i%2==1:
        ans+=1
print(ans)
### BUGGY CODE ###

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

for i in range(N):
    x = X[:]
    x.pop(i)
    x.sort()
    print(x[(N-1)//2])

### FIXED CODE ###

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

x_sort = sorted(X)
m = N//2 - 1
for i in range(N):
    if X[i] <= x_sort[m]:
        print(x_sort[m + 1])
    else:
        print(x_sort[m])
### BUGGY CODE ###

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

min_ = float('inf')
combi = itertools.combinations(p, k)
for c in combi:
    min_ = min(min_, sum(c))
    
print(min_)

### FIXED CODE ###

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

p = sorted(p)
ans = sum(p[:k])
print(ans)
### BUGGY CODE ###

N=int(input())
S=[int(input()) for i in range(N)]
mod=998244353
def add(a,b):
    return (a+b)%mod
def sub(a,b):
    return (a-b)%mod
def mul(a,b):
    return ((a%mod)*(b%mod))%mod
def pow(x,y):
    if y==0:
        return 1
    elif y==1:
        return x%mod
    elif y%2==0:
        return pow(x,y//2)**2 % mod
    else:
        return pow(x,y//2)**2 * x % mod
def div(a,b):
    return mul(a,pow(b,mod-2))

sum_S=sum(S)
dp=[[0]*(sum_S+1) for i in range(N)]
dp2=[[0]*(sum_S//2+1) for i in range(N)]

dp[0][0]=2
dp[0][S[0]]=1
dp2[0][0]=1
dp2[0][S[0]]=1
for i in range(1,N):
    for j in range(sum_S+1):
        dp[i][j]=mul(dp[i-1][j],2)
        if j-S[i]>=0 and dp[i-1][j-S[i]]!=0:
            dp[i][j]=add(dp[i][j],dp[i-1][j-S[i]])

        if j<=sum_S//2:
            dp2[i][j]=dp2[i-1][j]
            if j-S[i]>=0 and dp2[i-1][j-S[i]]!=0:
                dp2[i][j]=add(dp2[i][j],dp2[i-1][j-S[i]])

if sum_S%2==0:
    print((pow(3,N)-sum(dp[N-1][sum_S//2:])*3+dp2[N-1][-1]*3)%mod)
else:
    print((pow(3,N)-sum(dp[N-1][sum_S//2+1:])*3)%mod)


### FIXED CODE ###

N=int(input())
S=[int(input()) for i in range(N)]
mod=998244353
def add(a,b):
    return (a+b)%mod
def sub(a,b):
    return (a-b)%mod
def mul(a,b):
    return ((a%mod)*(b%mod))%mod
def pow(x,y):
    if y==0:
        return 1
    elif y==1:
        return x%mod
    elif y%2==0:
        return pow(x,y//2)**2 % mod
    else:
        return pow(x,y//2)**2 * x % mod
def div(a,b):
    return mul(a,pow(b,mod-2))

sum_S=sum(S)
dp=[[0]*(sum_S+1) for i in range(N)]
dp2=[[0]*(sum_S//2+1) for i in range(N)]

dp[0][0]=2
dp[0][S[0]]=1
dp2[0][0]=1
dp2[0][S[0]]=1
for i in range(1,N):
    for j in range(sum_S+1):
        dp[i][j]=mul(dp[i-1][j],2)
        if j-S[i]>=0 and dp[i-1][j-S[i]]!=0:
            dp[i][j]=add(dp[i][j],dp[i-1][j-S[i]])

        if j<=sum_S//2:
            dp2[i][j]=dp2[i-1][j]
            if j-S[i]>=0 and dp2[i-1][j-S[i]]!=0:
                dp2[i][j]=add(dp2[i][j],dp2[i-1][j-S[i]])

if sum_S%2==0:
    print((pow(3,N)-sum(dp[N-1][sum_S//2:])*3+dp2[N-1][-1]*3)%mod)
else:
    print((pow(3,N)-sum(dp[N-1][sum_S//2+1:])*3)%mod)
### BUGGY CODE ###

K , S = map(int, input().split())
pattern = 0

for i in range(0, K+1):
  for j in range(0, K+1):
    if ((S - (i+j)) <= K) & (S - (i+j) >= 0):
      pattern = pattern+1
print(pattern)

### FIXED CODE ###

K , S = map(int, input().split())
pattern = 0

for i in range(0, K+1):
  for j in range(0, K+1):
    if ((S - (i+j)) <= K) & (S - (i+j) >= 0):
      pattern = pattern+1
print(pattern)
### BUGGY CODE ###

S = str(input())
s = S
res = True
while res == True:
    s = s.replace('01','',1)
    s = s.replace('10','',1)
    res0 = s.find('01')
    res1 = s.find('10')
    if res0 == -1 and res1 == -1:
        res = False
print(len(S) - len(s))

### FIXED CODE ###

S = str(input())
s = S
cont0 = s.count('0')
cont1 = s.count('1')
if cont0 > cont1:
    print(cont1 * 2)
else:
    print(cont0 * 2)
### BUGGY CODE ###

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

for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            if i + j + k == n and 10000*i + 5000*j + 1000*k == y:
                print(i, j, k)
                exit()

print(-1, -1, -1)


### FIXED CODE ###

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

for i in range(n+1):
    for j in range(n+1):
        k = n - i - j
        if 0 <= k <= n and 10000*i + 5000*j + 1000*k == y:
            print(i, j, k)
            exit()

print(-1, -1, -1)
### BUGGY CODE ###

x = int(input(''))

can = []
for a in range(10**4):
    if not a in can:
        can.append(a**5)

result = []
for a in can:
    for b in can:
        if a - b == x:
            ans = "{} {}".format(int(a**(1/5)),int(b**(1/5)))
            if not ans in result:
                result.append(ans)
        if a + b == x and a > b:
            ans = "{} {}".format(int(a**(1/5)),int(-1 * b**(1/5)))
            if not ans in result:
                result.append(ans)

for r in result:
    print(r)

### FIXED CODE ###

x = int(input(''))

can = []
for a in range(10**3):
    a5 = a**5
    if not a5 in can:
        can.append(a5)

result = []
for a in can:
    for b in can:
        if a - b == x:
            ans = "{} {}".format(int(a**(1/5)),int(b**(1/5)))
            if not ans in result:
                result.append(ans)
        if a + b == x and a > b:
            ans = "{} {}".format(int(a**(1/5)),int(-1 * b**(1/5)))
            if not ans in result:
                result.append(ans)

for r in result:
    print(r)
### BUGGY CODE ###

n,m = map(int,input().split())
li = list(map(int,input().split()))
for _ in range(m):
    b,c = map(int,input().split())
    li += [c]*b
li.sort(reverse=True)
tmp = li[:n]
print(sum(tmp))

### FIXED CODE ###

n,m = map(int,input().split())
li = list(map(int,input().split()))
tmp_li = []
for _ in range(m):
    b,c = map(int,input().split())
    tmp_li.append((c,b))
tmp_li.sort(reverse=True)
#print(tmp_li)
for c,b in tmp_li:
    li.extend([c]*b)
    if len(li)>= 2*n:
        break
li.sort(reverse=True)
print(sum(li[:n]))
### BUGGY CODE ###

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

dp = [[[0] * ((H+W)*80) for _ in range(W)] for _ in range(H)]
dp[0][0][abs(A[0][0]-B[0][0])] = 1

for i in range(H):
    for j in range(W):
        dif = abs(A[i][j] - B[i][j])
        if i > 0:
            for k in range((H+W)*80):
                if dp[i-1][j][k] == 1:
                    dp[i][j][k+dif] = 1
                    if k >= dif:
                        dp[i][j][k-dif] = 1
                    else:
                        dp[i][j][dif-k] = 1
        if j > 0:
            for k in range((H+W)*80):
                if dp[i][j-1][k] == 1:
                    dp[i][j][k+dif] = 1
                    if k >= dif:
                        dp[i][j][k-dif] = 1
                    else:
                        dp[i][j][dif-k] = 1

for k in range(H*W*80):
    if dp[H-1][W-1][k] == 1:
        ans = k
        break

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
B = [list(map(int, input().split())) for i in range(H)]
center = 80 * (H+W)
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

dp = [[0] * W for i in range(H)]
dp[0][0] = (1 << (center + C[0][0])) | (1 >> (center - C[0][0]))

for i in range(H):
    for j in range(W):
        if i:
            dp[i][j] |= dp[i-1][j] << C[i][j]
            dp[i][j] |= dp[i-1][j] >> C[i][j]
        if j:
            dp[i][j] |= dp[i][j-1] << C[i][j]
            dp[i][j] |= dp[i][j-1] >> C[i][j]

ans = center * 2
for i in range(center*2):
    if (dp[H-1][W-1] >> i) & 1:
        ans = min(ans, abs(i-center))

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

from collections import deque

def main():
    H, W = map(int, input().split())
    field = "#"*(W+2)
    field += "#" + "##".join([input() for _ in range(H)]) + "#"
    field += "#"*(W+2)

    INF = 10**9
    cost = [INF]*len(field)
    move = [-1, 1, -(W+2), W+2]
    def bfs(s):
        q = deque()

        cost[s] = 0
        q.append(s)

        while q:
            now = q.popleft()
            now_cost = cost[now]
            for dx in move:
                nv = now + dx

                if field[nv] == "#" or cost[nv] < INF:
                    continue
                else:
                    cost[nv] = now_cost + 1
                    q.append(nv)
    
    ans = 0
    s_flag = False
    for si in range(H):
        for sj in range(W):
            s_flag = False
            for gi in range(H):
                if s_flag:
                    break
                for gj in range(W):
                    start = (si+1)*(W+2)+sj+1
                    goal = (gi+1)*(W+2)+gj+1
                    if field[start] == "#":
                        s_flag = True
                        break
                    if field[goal] == "#":
                        continue
                    if start == goal:
                        continue
                    cost = [INF] * len(field)
                    bfs(start)
                    ans = max(ans, cost[goal])
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque

def main():
    H, W = map(int, input().split())
    field = "#"*(W+2)
    field += "#" + "##".join([input() for _ in range(H)]) + "#"
    field += "#"*(W+2)

    INF = 10**9
    cost = [INF]*len(field)
    move = [-1, 1, -(W+2), W+2]
    def bfs(s, g):
        q = deque()
        dequeue = q.popleft
        enqueue = q.append
        cost[s] = 0
        enqueue(s)

        while q:
            now = dequeue()
            now_cost = cost[now]
            for dx in move:
                nv = now + dx
                if nv == g:
                    cost[g] = now_cost + 1
                    return
                if field[nv] == "#" or cost[nv] < INF:
                    continue
                else:
                    cost[nv] = now_cost + 1
                    q.append(nv)
    
    ans = 0
    for si in range(H):
        for sj in range(W):
            for gi in range(H):
                for gj in range(W):
                    start = (si+1)*(W+2)+sj+1
                    goal = (gi+1)*(W+2)+gj+1
                    if field[start] == "#" or  field[goal] == "#" or start == goal:
                        continue
                    cost = [INF] * len(field)
                    bfs(start, goal)
                    ans = max(ans, cost[goal])
    print(ans)

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

N,K = map(int,input().split())
h = list(map(int,input().split()))
DP = [float('inf')]*N
DP[0] = 0
for i in range(N):
    for j in range(K):
        if i+j+1 < N:
            DP[i+1+j] = min(DP[i+j+1],DP[i]+abs(h[i]-h[i+j+1]))
print(DP[-1])

### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
DP = [float('inf')]*N
DP[0] = 0
for i in range(N):
    for j in range(K):
        if i+j+1 < N:
            DP[i+1+j] = min(DP[i+j+1],DP[i]+abs(h[i]-h[i+j+1]))
print(DP[-1])
### BUGGY CODE ###

N, M = map(int, input().split())
S = str(input())
T = str(input())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
 
def lcm(x, y):
    return (x * y) // gcd(x, y)
X = lcm(N ,M)
 
if S[0] != T[0]:
    print(-1)
elif X == N*M:
    print(N*M)
else:
    for i in range(1,(N*M//X)+1):
        L = X * i
        m = lcm(  L // N,  L // M)
        for j in range(1, (L // m) ):
            if S[j * N * m // L] != T[ j * M * m // L]:
                L = -1
                break
        if L == X * i:
            break
    print(L)

### FIXED CODE ###

N, M = map(int, input().split())
S = str(input())
T = str(input())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
 
def lcm(x, y):
    return (x * y) // gcd(x, y)
X = lcm(N ,M)
 
if S[0] != T[0]:
    print(-1)
elif X == N*M:
    print(N*M)
else:
        L = X
        match = lcm(  L // N,  L // M)
        for j in range(1, (L // match) ):
            if S[j * N * match // L] != T[ j * M * match // L]:
                L = -1
                break
        if L == X :
            print(L)
        else:
            print(-1)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a.sort(reverse=True)
f.sort()
#print(a);print(f)

from heapq import *
q=[]
for i,j in zip(a,f):
  #print(i*j,i,j)
  heappush(q,(-i*j,str(j)))
#print(q)
for i in range(k):
  temp,key=heappop(q)
  heappush(q,(temp+int(key),key))
  
#print(q)

ans,tag=heappop(q)
print(-ans)

### FIXED CODE ###

n,k=map(int,input().split())
abilities=sorted(list(map(int,input().split())))
foods=sorted(list(map(int,input().split())),reverse=True)

if sum(abilities)<=k:
  print(0)
  exit()
  
def check(score):
  ret=0
  for a,f in zip(abilities,foods):
    ret+=max(0,(a*f-score+f-1)//f)
  return ret<=k

ok=10**12+1
ng=0
for _ in range(50):
  mid=(ok+ng)//2
  if check(mid):
    ok=mid
  else:
    ng=mid
print(ok)