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

# F
import numpy as np
from collections import deque
 
TT_list = []
# input
N, L = map(int, input().split())
T = 0.0
vt_now = 0.0
v_now = 0
que = deque()

for i in range(N):
    ti, v = map(int, input().split())
    t = float(ti)
    v_now += v
    vt_now += v*t
    # add
    if v == L:
        que.append([t, v])
    else:
        while v < L and len(que) > 0:
            t_, v_ = que.pop()
            if t_ <= t:
                que.append([t_, v_])
                que.append([t, v])
                break
            elif v + v_ >= L:
                v_ = v + v_ - L
                t = ((L - v) * t_ + v * t) / L
                v = L
                que.append([t_, v_])
                que.append([t, v])
                # break
            else:
                t = (t*v + t_*v_) / (v + v_)
                v = v + v_
    # minus
    while v_now > L:
        if que[0][1] <= v_now - L:
            v_now -= que[0][1]
            vt_now -= que[0][1]*que[0][0]
            que.popleft()
        else:
            que[0][1] -= v_now - L
            vt_now -= (v_now - L)*que[0][0]
            v_now = L
            
    TT_list.append(vt_now / L)

for i in range(N):
    print(TT_list[i])


### FIXED CODE ###

# F
from collections import deque
 
TT_list = []
# input
N, L = map(int, input().split())
T = 0.0
vt_now = 0.0
v_now = 0
que = deque()

for i in range(N):
    ti, v = map(int, input().split())
    t = float(ti)
    v_now += v
    vt_now += v*t
    # add
    if v == L:
        que.append([t, v])
    else:
        while v < L and len(que) > 0:
            t_, v_ = que[-1]
            if t_ <= t:
                que.append([t, v])
                break
            elif v + v_ >= L:
                v_ = v + v_ - L
                t = ((L - v) * t_ + v * t) / L
                v = L
                que = deque([[t, v]])
                v_now = L
                vt_now = t*L
                # break
            else:
                t = (t*v + t_*v_) / (v + v_)
                v = v + v_
                que.pop()
    # minus
    while v_now > L:
        if que[0][1] <= v_now - L:
            v_now -= que[0][1]
            vt_now -= que[0][1]*que[0][0]
            que.popleft()
        else:
            que[0][1] -= v_now - L
            vt_now -= (v_now - L)*que[0][0]
            v_now = L
            
    TT_list.append(vt_now / L)

for i in range(N):
    print(TT_list[i])
### BUGGY CODE ###

import itertools
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = []
for i in itertools.combinations(a,k):
    ans.append(max(i)-min(i))
print(sum(ans)%((10**9)+7))

### FIXED CODE ###

def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
mod = 10**9+7  
nums = 10**5 # 制約に合わせよう
g1, g2, inverse = [1, 1] , [1, 1], [0, 1]
 
for num in range(2, nums + 1):
    g1.append((g1[-1] * num) % mod)
    inverse.append((-inverse[mod % num] * (mod//num)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

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

ans = 0
for i in range(n):
    res = cmb(n-i-1, k-1, mod)
    ans += res*a[n-i-1] - res*a[i]
    ans %= mod
print(ans)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

def intersection(p, q, eps = 10**-7):
    x1, y1, r1 = p
    x2, y2, r2 = q
    X = x2 - x1; Y = y2 - y1
    d = X**2 + Y**2
    c1 = r1**2; c2 = r2**2

    rc = (d + c1 - c2) / 2
    rs = d * c1 - rc ** 2
    
    if rs < eps: return list()
    
    rs **= .5
    p1x = x1 + (rc * X + rs * Y) / d
    p1y = y1 + (rc * Y - rs * X) / d
    p2x = x1 + (rc * X + rs * Y) / d
    p2y = y1 + (rc * Y + rs * X) / d
    return [(p1x, p1y), (p2x, p2y)]

eps = 10**-7
n,k = nm()
if k == 1: print(0); exit(0)
niku = [tuple(nm()) for _ in range(n)]
l = [c*(x**2+y**2)**.5 for x,y,c in niku]
l.sort()
hi = l[k-1]
lo = 0
for _ in range(50):
  mid = (hi+lo)/2
  l = [(x,y,mid/c) for x,y,c in niku]
  p = [(x,y) for x,y,c in niku]
  for i in range(n-1):
    for j in range(i+1,n):
      p.extend(intersection(l[i], l[j]))
  for x,y in p:
    f = sum((v-x)**2 + (w-y)**2 <= r**2 + eps for v,w,r in l)
    if f >= k:
      hi = mid
      break
  else:
    lo = mid
print(hi)


### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

def intersection(p, q, eps = 10**-7):
    x1, y1, r1 = p
    x2, y2, r2 = q
    X = x2 - x1; Y = y2 - y1
    d = X**2 + Y**2
    c1 = r1**2; c2 = r2**2

    rc = (d + c1 - c2) / 2
    rs = d * c1 - rc ** 2
    
    if rs < eps: return list()
    
    rs **= .5
    p1x = x1 + (rc * X + rs * Y) / d
    p1y = y1 + (rc * Y - rs * X) / d
    p2x = x1 + (rc * X + rs * Y) / d
    p2y = y1 + (rc * Y + rs * X) / d
    return [(p1x, p1y), (p2x, p2y)]

eps = 10**-7
n,k = nm()
if k == 1: print(0); exit(0)
niku = [tuple(nm()) for _ in range(n)]
l = [c*(x**2+y**2)**.5 for x,y,c in niku]
l.sort()
hi = l[k-1]
lo = 0
for _ in range(50):
  mid = (hi+lo)/2
  l = [(x,y,mid/c) for x,y,c in niku]
  p = [(x,y) for x,y,c in niku]
  for i in range(n-1):
    for j in range(i+1,n):
      p.extend(intersection(l[i], l[j]))
  for x,y in p:
    f = sum((v-x)**2 + (w-y)**2 <= r**2 + eps for v,w,r in l)
    if f >= k:
      hi = mid
      break
  else:
    lo = mid
print(hi)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
s = [1 for i in range(n)]
import copy 
for q in range(min(k,35)):
    ans = copy.deepcopy(s)
    for i in range(n):
        if a[i] != 0:
            ans[i] -= 1
            for j in range(2*a[i]+1):
                if 0 <= i-a[i]+j <= n-1:
                    ans[i-a[i]+j] += 1
    a = ans
g = [0]*n
if k > 34:
    for i in range(n):
        print(g[i], end = ' ')
else:
    for i in range(n):
        print(a[i], end = ' ')

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
si = [0 for i in range(n+1)]
p = [1 for i in range(n)]
import copy 
for q in range(min(k,50)):
    v = 0
    s = copy.deepcopy(si)
    for i in range(n):
        if a[i] != 0:
            s[max(i-a[i],0)] += 1
            s[min(i+a[i]+1,n)] -= 1
            a[i] = 0
        else:
            a[i] = 1
    for i in range(n):
        v += s[i]
        a[i] += v
for i in range(n):
    print(a[i], end = ' ')
### BUGGY CODE ###

ii = lambda:int(input())
mi = lambda:list(map(int,input().split()))
ix = lambda x:list(input() for _ in range(x))
mix = lambda x:list(mi() for _ in range(x))
iix = lambda x:list(int(input()) for _ in range(x))
##########
def main(n,q,s,l):
    res = []
    for i in l:
        c = 0
        tar = s[i[0]-1:i[1]]
        for j in range(len(tar)-1):
            if tar[j]=="A" and tar[j+1]=="C":
                c += 1
        res.append(c)
    for ans in res:
        print(ans)

def resolve():
    n,q = mi()
    s = input()
    l = mix(q)
    main(n,q,s,l)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

ii = lambda:int(input())
mi = lambda:list(map(int,input().split()))
ix = lambda x:list(input() for _ in range(x))
mix = lambda x:list(mi() for _ in range(x))
iix = lambda x:list(int(input()) for _ in range(x))
##########
def main(n,q,s,l):
    lst_ac = [0]*(len(s))
    for i in range(len(s)-1):
        if s[i]+s[i+1] == "AC":
            lst_ac[i+1] = lst_ac[i]+1
        else:
            lst_ac[i+1] = lst_ac[i]
    for item in l:
        print(lst_ac[item[1]-1] - lst_ac[item[0]-1])

def resolve():
    n,q = mi()
    s = input()
    l = mix(q)
    main(n,q,s,l)

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

import sys
input = sys.stdin.readline

ans = 0
n = int(input())
A = list(map(int,input().split()))
B = [0] * (10**6+3)
for i in range(n):
    B[A[i]] += 1

for i in range(n):
    Y = []
    Z = []
    for j in range(1, int(A[i]**0.5)+1):
        if A[i] % j == 0:
            Y.append(j)
            if j != A[i]//j:
                Z.append(A[i]//j)
    Y = [A[i]] + Y + Z[::-1]
    # print(Y)
    ok = 1
    for j in range(len(Y)):
        if (Y[j] != A[i] and B[Y[j]] > 0) or (Y[j] == A[i] and B[Y[j]] > 1):
            ok = 0
            break
    # print(ok)
    ans += ok
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

ans = 0
n = int(input())
A = list(map(int,input().split()))
B = [0] * (10**6+3)
ans = 0
A.sort()
for i in range(n):
    if (i == 0 or A[i] != A[i-1]) and (i == n-1 or A[i] != A[i+1]) and B[A[i]] == 0:
        ans += 1
    if (i == 0 or A[i] != A[i-1]):
        m = A[i]
        while m < len(B):
            B[m] = 1
            m += A[i]
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for i in range(N)]

dp=[[0]*(W+1) for i in range(N+1)]

for w in range(W+1):
    for n in range(N):
        if wv[n][0] <= w:
            dp[n+1][w] = max(dp[n][w-wv[n][0]] + wv[n][1], dp[n][w])
        else:
            dp[n+1][w] = dp[n][w]


print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for i in range(N)]
 
dp=[[0]*(W+1) for i in range(N+1)]
 
for w in range(W+1):
    for n in range(N):
        if wv[n][0] <= w:
            dp[n+1][w] = max(dp[n][w-wv[n][0]] + wv[n][1], dp[n][w])
        else:
            dp[n+1][w] = dp[n][w]
 
 
print(dp[N][W])
### BUGGY CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
kouho=[]
def saikorokitaiti(A):
    return ((P[A]*(1+P[A])/2)/P[A])
kari=[]
hako=[]
kitaiti=0
if K==1:
    print(saikorokitaiti(P.index(max(P))))
    exit()
for i in range(K):
    hako.append(saikorokitaiti(i))
    kitaiti+=saikorokitaiti(i)
for j in range(N-K+1):
    if j==0:
        kouho.append(kitaiti)
    elif j+K-1<N:
        hako.append(saikorokitaiti(j+K-1))
        kitaiti+=saikorokitaiti(j+K-1)
        kitaiti-=hako.pop(0)
        kouho.append(kitaiti)
#print(kouho)
print(max(kouho))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
P=list(map(int,input().split()))
kouho=0
def saikorokitaiti(A):
    return ((P[A]*(1+P[A])/2)/P[A])
kari=[]
hako=[]
kitaiti=0
if K==1:
    print(saikorokitaiti(P.index(max(P))))
    exit()
for i in range(K):
    hako.append(saikorokitaiti(i))
    kitaiti+=saikorokitaiti(i)
    kouho=kitaiti
b=0
for j in range(N-K+1):
    if j==0:
        continue
    elif j+K-1<N:
        hako.append(saikorokitaiti(j+K-1))
        kitaiti+=saikorokitaiti(j+K-1)
        kitaiti-=hako[b]
        b+=1
        kouho=max(kouho,kitaiti)
#print(kouho)
print(kouho)
### BUGGY CODE ###

k,s = map(int,input().split())

cnt = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                cnt += 1

print(cnt)


### FIXED CODE ###

k,s = map(int,input().split())

cnt = 0
for x in range(k+1):
    for y in range(k+1):
        if 0 <= s-x-y <=k:
            cnt += 1

print(cnt)
### BUGGY CODE ###

from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
N,A,B,C=map(int,input().split())
L=[int(input()) for i in range(N)]
value=10**10
itelst=[list(permutations(L,i)) for i in range(3,N+1)]
for a,b,c in list(permutations([A,B,C])):
    for n in range(N-2):
        for lst in itelst[n]:
            for i1 in range(1,len(lst)-1):
                for i2 in range(i1+1,len(lst)):
                    value=min(value, (len(lst)-3)*10+\
                            round(abs(a-sum(lst[  :i1])))+\
                            round(abs(b-sum(lst[i1:i2])))+\
                            round(abs(c-sum(lst[i2:  ]))))

print(value)


### FIXED CODE ###

from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
N,A,B,C=map(int,input().split())
L=[int(input()) for i in range(N)]
value=10**10
itelst=[list(permutations(L,i)) for i in range(3,N+1)]
for n in range(N-2):
    for lst in itelst[n]:
        lstsum=sum(lst)
        a=0
        for i1 in range(len(lst)-2):
            a+=lst[i1]
            b=0
            for i2 in range(i1+1,len(lst)-1):
                b+=lst[i2]
                c=lstsum-a-b
                c1,b1,a1=sorted([a,b,c])
                a1=A-a1 if A-a1>0 else a1-A
                b1=B-b1 if B-b1>0 else b1-B
                c1=C-c1 if C-c1>0 else c1-C
                value=min(value, (len(lst)-3)*10 + a1+b1+c1)





print(value)
### BUGGY CODE ###

s = input()
keta = len(s) + 1
n = int(s)

ans = 0
while n > 0:
    keta -= 1
    hoge = 10 ** (keta-1)
    t = n // (hoge)
    pre_t = n // (hoge//10) if hoge >= 10 else 0
    if t == 0:
        continue
    #print(n, t, pre_t, keta, hoge)
    if t < 5 or (t == 5 and pre_t <= 54):  # 555 の時とか1000円だすと14枚で行けてしまう。。
        ans += t
        n = n - t * hoge
        #print(t * hoge,'払った,残り', n, ans)
    else:
        ans += 1
        keta += 1
        n = hoge*10 - n  # どちらがお金を払うかが入れ替わる
        #print(hoge*10,'払った,お釣り', n, ans)
print(ans)


### FIXED CODE ###

n = input()
lenn = len(n)

dp = [0, 10000]
for d in reversed(n):
    d = int(d)
    dp = [min(d + dp[0], d + 1 + dp[1]), min(10 - d + dp[0], 9 - d + dp[1])]

print(min(dp[0], 1 + dp[1]))
### BUGGY CODE ###

N = int(input())

alist = map(int,input().split())

checklist = []

for item in alist:
    if item not in checklist:
        checklist.append(item)
    else:
        print('NO')
        exit(0)

print('YES')

### FIXED CODE ###

N = int(input())

alist = input().split()

checklist = {}

for ite in alist:
    if checklist.get(ite) == '1':
        print('NO')
        exit(0)
    else:
        checklist[ite] = '1'

print('YES')
### BUGGY CODE ###

# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math, fractions, collections
# ===================================
x, y = [int(x) for x in input().split()]
if x == y or y == 1:
	print(-1)
else:
	temp = x
	while(temp%y == 0):
		temp += x
	print(temp)

### FIXED CODE ###

# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math, fractions, collections
# ===================================
x, y = [int(x) for x in input().split()]
if x == y or y == 1 or x%y == 0:
	print(-1)
else:
	temp = x
	while(temp%y == 0):
		temp += x
	print(temp)
### BUGGY CODE ###

def main():
    n=int(input())
    s=[input() for _ in [0]*n]
    s=[i+i[:-1] for i in s]+[i+i[:-1] for i in s][:-1]
    ans=[[0]*n for _ in [0]*n]
    for i in range(1,2*n-1):
        for j in range(2*n-2):
            for k in range(1,min(i+1,n,2*n-1-j)):
                if s[i][j]!=s[i-k][j+k]:
                    width=min(n-k+1,i-k,j)-max(-1,i-k-n,j-n)
                    if width<1:
                        continue
                    l=min(n-k+1,i-k,j)
                    ans[i-k-l][j-l]=max(ans[i-k-l][j-l],width)
    for i in range(n-1):
        for j in range(n-1):
            ans[i+1][j+1]=max(ans[i+1][j+1],ans[i][j]-1)
    print(sum([sum([i==0 for i in a]) for a in ans]))
main()

### FIXED CODE ###

def main():
    n=int(input())
    nn=2*n-1
    s=[input() for _ in [0]*n]
    s=[i+i[:-1] for i in s]+[i+i[:-1] for i in s][:-1]
    ans=[[0]*n for _ in [0]*n]
    for i in range(1,nn):
        m=min(i+1,n)
        for j in range(nn-1):
            for k in range(max(i-j-n,0)+1,min(m,nn-j,i-j+n)):
                ii=i-k
                if s[i][j]!=s[ii][j+k]:
                    l=min(n-k+1,ii,j)
                    width=l-max(-1,ii-n,j-n)
                    ans[ii-l][j-l]=max(ans[ii-l][j-l],width)
    for i in range(1,n):
        for j in range(1,n):
            ans[i][j]=max(ans[i][j],ans[i-1][j-1]-1)
    print(sum([sum([i==0 for i in a]) for a in ans]))
main()
### BUGGY CODE ###

s = input()
a = int(s)
mods = [a%2019]
for i in range(len(s)):
  a = a-int(s[i])*10**(len(s)-i-1)
  mods.append(a%2019)
mod_N = {}
smod = set(mods)
for i in smod:
  mod_N[i] = 0
for i in mods:
  mod_N[i] += 1
ans = 0
for i in mod_N:
  ans += mod_N[i]*(mod_N[i]-1)/2
print(int(ans))

### FIXED CODE ###

s = input()
a = 0
mods = [0]*2019
mods[a] += 1
r = 1
for i in s[::-1]:
  a = (a+int(i)*r)%2019
  r = r*10%2019
  mods[a] += 1
ans = 0
for i in mods:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

import collections

N=int(input())
S=[]
for i in range(N):
    S.append(input())

ans = 0
for j in range(N-1):
    for k in range(j+1, N):
        if (collections.Counter(S[j]) == collections.Counter(S[k])):
            ans += 1

print(ans)


### FIXED CODE ###

N = int(input())

S = []
for i in range(N):
    S.append(input())

count = {}
ans = 0

for s in S:
    s=str(sorted(s))
    if s in count:
        count[s] += 1
    else:
        count[s] = 1

ans = 0
for c in count.values():
    ans += c*(c-1)//2
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a)
mod=10**9+7
from operator import mul
from functools import reduce

def cmb(n,r):
    r=min(n-r,r)
    if r==0:
        return 1
    else:
        over=reduce(mul,range(n,n-r,-1))
        under=reduce(mul,range(1,r+1))
        return over//under
ans=0
for i in range(n-k+1):
    ans+=cmb(k+i-1,k-1)*(a[k-1+i]-a[n-k-i])
print(ans%mod)

                

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a)
mod=10**9+7
ans=0
f=[1]
for i in range(1,n+1):
    f.append((f[-1]*i)%mod)
for i in range(n-k+1):
    ans+=(f[k+i-1]*pow(f[i],mod-2,mod)*pow(f[k-1],mod-2,mod))*(a[k-1+i]-a[n-k-i])
print(ans%mod)
### BUGGY CODE ###

A, B, C = map(int, input().split())
x, y = abs(A-B), abs(B-C)
ans = 0
if x == 0 and y == 0 and A % 2 == 0:
  print(-1)
  exit()

while x % 2 == 0 and y % 2 == 0:
  x, y = x // 2, y // 2
  ans += 1
print(ans)

### FIXED CODE ###

A, B, C = map(int, input().split())
x, y = abs(A-B), abs(B-C)
ans = 0
if x == 0 and y == 0 and A % 2 == 0:
  print(-1)
  exit()

if x == 0 and y == 0 and A % 2 == 1:
  print(0)
  exit()
  
while x % 2 == 0 and y % 2 == 0:
  x, y = x // 2, y // 2
  ans += 1
print(ans)
### BUGGY CODE ###

def divisors(n):
    ds = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ds.append(i)
            if i != n // i:# and i != 1:
                ds.append(n//i)
    # divisors.sort()
    return ds

n = int(input())
aa = list(map(int, input().split()))
counts = {}
balls = {}


for i in range(len(aa)):
    if aa[i] == 1:
        counts[i + 1] = 1
    else:
        counts[i + 1] = 0

for i in range(n, 0, -1):
    #print(f'i = {i}, counts={counts}')
    if counts[i] % 2 == 0:
        continue
    # put ball in i
    balls[i] = True
    ds = divisors(i)
    for d in ds:
        counts[d] += 1
balls = list(balls.keys())
print(len(balls))
if len(balls) > 0:
    print(' '.join(map(str, balls)))





### FIXED CODE ###

def divisors(n):
    ds = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ds.append(i)
            if i != n // i:# and i != 1:
                ds.append(n//i)
    # divisors.sort()
    return ds

n = int(input())
aa = list(map(int, input().split()))
counts = {}
balls = {}


for i in range(len(aa)):
    if aa[i] == 1:
        counts[i + 1] = 1
    else:
        counts[i + 1] = 0

for i in range(n, 0, -1):
    #print(f'i = {i}, counts={counts}')
    if counts[i] % 2 == 0:
        continue
    # put ball in i
    balls[i] = True
    ds = divisors(i)
    for d in ds:
        counts[d] += 1
balls = list(balls.keys())
print(len(balls))
if len(balls) > 0:
    print(' '.join(map(str, balls)))
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
maze=[input() for i in range(h)]
visited=[[float('inf')]*w for i in range(h)]
ans,b,q=0,[],deque()
for i in range(h):
  for j in range(w):
    if maze[i][j]=='#':
      q.append([i,j])
      visited[i][j]=0
while q:
  x,y=q.popleft()
  for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
    newx,newy=x+i,y+j
    if 0<=newx<h and 0<=newy<w:
      if maze[newx][newy]!='#' and visited[newx][newy]==float('inf'):
        visited[newx][newy]=visited[x][y]+1
        q.append([newx,newy])
        ans=max(ans,visited[newx][newy])
print(ans)


### FIXED CODE ###

from collections import deque
def main():
  h,w=map(int,input().split())
  hw=h*w
  maze=[list(input()) for i in range(h)]
  visited=[[hw]*w for i in range(h)]
  ans,q=0,deque()
  for i in range(h):
    for j in range(w):
      if maze[i][j]=='#':
        q.append((i,j))
        visited[i][j]=0
  while q:
    x,y=q.popleft()
    for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if maze[newx][newy]!='#' and visited[newx][newy]==hw:
          visited[newx][newy]=visited[x][y]+1
          q.append((newx,newy))
          ans=max(ans,visited[newx][newy])
  return print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

def msf(s,q,ql):
    len_ql = len(ql)
    for i in range(1,len_ql-1):
        t1 = ql[i][0]
        if t1 == "1":
            s = list(reversed(s))
        elif t1 == "2":
            f = ql[i][1]
            c = list(ql[i][2])
            if f == "1":
                s = c + s
            elif f == "2":
                s = s + c
    return s
    
if __name__ == '__main__':
    s = list(input())
    q = int(input())
    ql = [list(input().split()) for _ in range(q)]

    ql = [['0']] + ql + [['0']]
    len_ql = len(ql)

    for i in range(1,len_ql-1):
        if len_ql <= i:
            break
        elif ql[i][0] == "1" and ql[i-1][0] == "1" :
            ql = ql[0:i-1] + ql[i+1:]
            len_ql -= 2
        else:
            pass

    print(''.join(msf(s,q,ql)))


### FIXED CODE ###

from collections import deque

def msf(s,queries):
    queue = deque(s)
    addl = queue.appendleft
    addr = queue.append
    is_reversed = 0

    for query in queries:
        if query[0] == '1':
            is_reversed ^= 1
            addl,addr = addr,addl
        elif query[0] == '2':
            f = query[1]
            c = query[2]
            if f == '1':
                addl(c)
            elif f == '2':
                addr(c)
    return ''.join(queue) if not is_reversed else ''.join(reversed(queue))

if __name__ == '__main__':
    s = list(input())
    q = int(input())
    ql = [input().split() for i in range(q)]
    print(msf(s,ql))
### BUGGY CODE ###

import numpy as np

N, M=map(int, input().split())
A=np.array(list(map(int, input().split())))
for i in range(M):
  B, C=map(int, input().split())
  A=np.r_[A, np.ones(B)*C]
  
A=np.sort(A)
print(int(np.sum(A[-N:])))

### FIXED CODE ###

from collections import defaultdict

cnt=defaultdict(int)

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

for i in range(N):
  cnt[A[i]]+=1

tmp=[0]*M
for i in range(M):
  B, C=map(int, input().split())
  cnt[C]+=B
  tmp[i]=C
A+=tmp

tmp=list(cnt.keys())
tmp.sort()
j=-1
out=0
while N>0:
  if cnt[tmp[j]]<=N:
    out+=tmp[j]*cnt[tmp[j]]
    N-=cnt[tmp[j]]
  else:
    out+=tmp[j]*N
    N=0
    
  j-=1
print(out)
### BUGGY CODE ###

import heapq

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

F = sorted(F, reverse = True)
A = sorted(A)
flg = 0
heap = []

for i in range(N):
	if A[i] == 0 or F[i] == 0:
		break
	else:
		heapq.heappush(heap, [- A[i] * F[i], A[i], F[i]])
	
for i in range(K):
	score, tmp_A, tmp_F = heapq.heappop(heap)
	if tmp_A > 0:
		tmp_A -= 1
		heapq.heappush(heap, [- tmp_A * tmp_F, tmp_A, tmp_F])
	else:
		flg = 1
		break
		
if flg:
	print(0)
else:
	ret = heapq.heappop(heap)
	print(-1 * ret[0])	


### FIXED CODE ###

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

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

ng = -1
ok = 10 ** 12

while ok - ng > 1:
	mid = (ok + ng) // 2
	ctr = 0
	for i in range(N):
		ctr += max(0, A[i] - mid // F[i])
	if ctr <= K:
		ok = mid
	else:
		ng = mid

print(ok)