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

N, M = map(int, input().split())
INF = 10**9
A = []
B = []

for i in range(N):
  a,b = map(int, input().split())
  A.append(a)
  B.append(b)

ans = 0
count = 0
while(count < M):
  min_A = min(A)
  min_Ai = A.index(min_A)
  B_min = B[min_Ai]
  if count + B_min > M:
    ans += min_A * (M - count)
    count = M
  else:
    ans += min_A * B_min
    count += B_min
  del A[min_Ai]
  del B[min_Ai]

print(ans)


### FIXED CODE ###

def unzip(li):
  return map(list, zip(*li))

N, M = map(int, input().split())
tmp_C = [0 for i in range(N)]

for i in range(N):
  a,b = map(int, input().split())
  tmp_C[i] = (a,b)
  
C = sorted(tmp_C)
A, B = unzip(C)
ans = 0
count = 0
cur = 0
while(count < M):
  min_A = A[cur]
  B_min = B[cur]
  if count + B_min >= M:
    print(ans + min_A * (M - count))
    break
  else:
    ans += min_A * B_min
    count += B_min
    cur += 1
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
L = []
R = []
# ans = []
for _ in range(Q):
	l, r = map(int, input().split())
	L.append(l)
	R.append(r)
flag = [0, 0]
for i in range(N-1):
	if S[i] == 'A' and S[i+1] == 'C':
		flag.append(1)
	else:
		flag.append(0)
# print(flag)
ans = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(N):
	for j in range(1,N+1):
		ans.append(0)
		
for i in range(N):
	for j in range(i,N):
		ans[i][j+1] = ans[i][j] + flag[j+1]
		ans[i+1][j] = ans[i][j] - flag[i+1]

for i in range(Q):
	print(ans[L[i]][R[i]])

# for i in range(Q):
# 	print(ans[i])

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
L = []
R = []
# ans = []
for _ in range(Q):
	l, r = map(int, input().split())
	L.append(l)
	R.append(r)
sum = [0] * (N+1)
for i in range(1, N):
	if S[i-1] == 'A' and S[i] == 'C':
		sum[i+1] = sum[i] + 1
	else:
		sum[i+1] = sum[i]
# print(sum)


for i in range(Q):
	print(sum[R[i]] - sum[L[i]])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
s=0
if sorted(a) == a:
    print(s)
    exit()
while len(a)>0:
    x=max(a)
    k=a.index(x)
    s=s+x*(len(a)-1-k)-sum(a[k+1:])
    a=a[:k]
print(s)





### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
mx=a[0]
for x in a:
    if mx>x:ans+=mx-x
    else:mx=x
print(ans)
### BUGGY CODE ###

K = int(input())
X,Y = map(int,input().split())

ans = [(X,Y)]
x,y = ans[-1]
while abs(x)>=2*K:
    x,y = ans[-1]
    if x>=K:
        x -= K
    elif x<=-K:
        x += K
    ans.append((x,y))
dx = abs(x)

while abs(y)>2*K-dx:
    x,y = ans[-1]
    if y>0:
        y -= K
    else:
        y += K
    ans.append((x,y))

x,y = ans[-1]
if abs(y)+abs(x)!=K:
    if (x+y)%2==0 and K%2==0:
        d2 = (abs(x)+abs(y))//2
        if abs(x)>abs(y):
            x -= d2 * (1 if x>0 else -1)
            y += (K-d2) * (1 if y>0 else -1)
        else:
            x += (K-d2) * (1 if x>0 else -1)
            y -= d2 * (1 if y>0 else -1)
        ans.append((x,y))
    else:
        if (x+y+K)%2 == 0:
            y -= K if y>0 else (-K)
            ans.append((x,y))
        d = abs(x)+abs(y)
        if abs(x)>abs(y):
            x -= d//2 * (1 if x>0 else -1)
            y += (K-d//2) * (1 if y>0 else -1)
        else:
            x += (K-d//2) * (1 if x>0 else -1)
            y -= d//2 * (1 if y>0 else -1)
        ans.append((x,y))
x,y = ans[-1]

if abs(x)+abs(y)!=K:
    print(-1)
else:
    ans = ans[::-1]
    print(len(ans))
    for out in ans:
        print(*out)

### FIXED CODE ###

K = int(input())
X,Y = map(int,input().split())

ans = [(X,Y)]
x,y = ans[-1]
while abs(x)>=3*K//2:
    x,y = ans[-1]
    if x>=K:
        x -= K
    elif x<=-K:
        x += K
    ans.append((x,y))
dx = abs(x)

while abs(y)>2*K-dx:
    x,y = ans[-1]
    if y>0:
        y -= K
    else:
        y += K
    ans.append((x,y))

x,y = ans[-1]
if abs(y)+abs(x)!=K:
    if (x+y)%2==0 and K%2==0:
        d2 = (abs(x)+abs(y))//2
        if abs(x)>abs(y):
            x -= d2 * (1 if x>0 else -1)
            y += (K-d2) * (1 if y>0 else -1)
        else:
            x += (K-d2) * (1 if x>0 else -1)
            y -= d2 * (1 if y>0 else -1)
        ans.append((x,y))
    else:
        if (x+y+K)%2 == 0:
            y -= K if y>0 else (-K)
            ans.append((x,y))
        d = abs(x)+abs(y)
        if abs(x)>abs(y):
            x -= d//2 * (1 if x>0 else -1)
            y += (K-d//2) * (1 if y>0 else -1)
        else:
            x += (K-d//2) * (1 if x>0 else -1)
            y -= d//2 * (1 if y>0 else -1)
        ans.append((x,y))
x,y = ans[-1]

if abs(x)+abs(y)!=K:
    print(-1)
else:
    ans = ans[::-1]
    print(len(ans))
    for out in ans:
        print(*out)
### BUGGY CODE ###

N,M = map(int,input().split())
AB = []
ans = 0
for i in range(N):
    A,B = map(int,input().split())
    t = A,B
    AB.append(t)    
AB.sort()
l = []
for i in range(len(AB)):
    for x in range(AB[i][1]):
        l.append(AB[i][0])
i = 0
while M > 0:
    ans += l[i]
    M -= 1
    i += 1

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,M=[int(x) for x in input().strip().split()]
AN=[]
BN=[]
val={}
for i in range(N):
    Ai,Bi=[int(x) for x in input().strip().split()]
    val[Ai]=Bi+val.get(Ai,0)
    AN.append(Ai)
 
AN=sorted(set(AN))
m=0
ans=0
for Ai in AN:
    ans+=Ai*min(M-m,val[Ai])
    m+=min(M-m,val[Ai])
    if m==M:
        break
print(ans)
### BUGGY CODE ###

n = int(input())
lis = [0] + list(map(int, input().split())) + [0]
tmp = []
for j in range(len(lis)-1):
    tmp.append(lis[j+1] - lis[j])
for i in range(len(tmp)-1):
    a = tmp[:i] + [tmp[i]+tmp[i+1]] + tmp[i+2:]
    print(sum(map(abs,a)))


### FIXED CODE ###

n = int(input())
lis = [0] + list(map(int, input().split())) + [0]
tmp = []
for j in range(len(lis)-1):
    tmp.append(lis[j+1] - lis[j])
lis = list(map(abs,tmp))
preans = sum(lis)
for i in range(len(tmp)-1):
    print(preans - lis[i] - lis[i+1] + abs(tmp[i] + tmp[i+1]))
### BUGGY CODE ###

# 組み合わせの数を出力
n = int(input())
s = [sorted(input()) for _ in range(n)]
count = 0
for i in range(n-1):
    for j in range(i+1, n):
        if s[i] == s[j]:
            count += 1

print(count)


### FIXED CODE ###

import sys
import collections
input = sys.stdin.readline

n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
dup = collections.Counter(s).values()

ans = sum(c*(c-1)//2 for c in dup)
print(ans)
### BUGGY CODE ###

n=int(input())
for i in range(1,n+1):
    k=int(i**0.5)+1
    a=0
    for x in range(1,k):
        for y in range(1,k):
            for z in range(1,k):
                if (x+y)**2+(y+z)**2+(z+x)**2==2*i:
                    #print(i,x,y,z,end=' ')
                    a+=1
                if (x+y)**2+(y+z)**2+(z+x)**2>2*i:
                    break
    print(a)

### FIXED CODE ###

n=int(input())
k=int(n**0.5)+1
a=[0 for i in range(n+1)]
for x in range(1,k):
    for y in range(1,k):
        for z in range(1,k):
            g=x*x+y*y+z*z+x*y+y*z+x*z
            if g<=n:
                a[g]+=1
print(*a[1:],sep='\n')
### BUGGY CODE ###

# encoding: utf-8
import math
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# define search range
p_max = M // 2 # M is prime if M has a factor p (> p_max)
ip_up = max((1, int(math.log2(M)))) # MDE

#### O(MlogM) below (if M has a very large prime factor)
M_tmp = M
ips = []
for p in range(2, p_max + 1):
    if M_tmp % p > 0: continue
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_up + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # calculate later
    ips.append(i_p)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break
#### O(Mlog M) above

#### O(N) below
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        p_memo[N - 1 - j] = sum_tmp
#### O(N) above
        
# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7)

if M == 1: print(1)
elif ip_max < 1: print(N)
else: print(ans)

### FIXED CODE ###

# encoding: utf-8
import math
N, M = map(int, input().split())

ips = []
M_tmp = M
for p in range(2, int(math.sqrt(M)) + 1):
    if M_tmp % p > 0: continue
    for i_p in range(1, 33):
        if M_tmp % (p ** (i_p + 1)) > 0: break
    ips.append(i_p)
    M_tmp = M_tmp // (p ** i_p)
    if M_tmp == 1: break
else:
    ips.append(1)

#### O(NlogM) below ?
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    ptr_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        ptr_memo[N - 1 - j] = sum_tmp
#### O(NlogM) above ?
        
# calculate ans
ans = 1
for i_p in ips:
    ans = (ans * memo[i_p][0]) % (10 ** 9 + 7)

if M == 1: print(1)
elif ip_max < 1: print(N)
else: print(ans)
### BUGGY CODE ###

import numpy as np

mod=10**9+7
s=input()
rev=reversed(s)
d=np.array([0 for i in range(13)])
d[0]=1
keep=np.array([0 for _ in range(13)])
mul=1
cal=0
t=np.array([i for i in range(13)])
for v in rev:
    if v!="?":
        cal+=mul*int(v)%13
    else:
        t_d=keep.copy()
        for j in range(1,10):
            t_d[(t+mul*j)%13]+=d
        d+=t_d
        d%=mod
        
    mul*=10
    mul%=13

cal%=13
if cal<=5:
    cal=5-cal
else:
    cal=18-cal
print(d[cal]%mod)



### FIXED CODE ###

#%%time
mod=10**9+7
s=input()


#p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=reversed(s)
d=[0 for i in range(13)]
d[0]=1
keep=[0 for _ in range(13)]
mul=1
cal=0
for v in rev:
    #print(i+num+1)
    if v=="?":
        t_d=[0 for _ in range(13)]
        #print("i,tmp:",i+num+1,",",tmp)
        for k in range(0,13):
            for j in range(0,10):
                t_d[(mul*j+k)%13]+=d[k]
            t_d[k]%=mod
        d=t_d
    else:
        cal+=mul*int(v)%13
    mul*=10
    mul%=13
        #print(t_d)
cal%=13
if cal<=5:
    cal=5-cal
else:
    cal=18-cal
print(d[cal]%mod)
#print(d)
#h=d
#print([i%mod for i in h])
### BUGGY CODE ###

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

from functools import lru_cache
@lru_cache(maxsize=None)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

ans = 1
for i in range(N):
    if i != 0:
        a = A[0]
    else:
        a = A[1]
    for j in range(N):
        if i == j:
            continue
        a = gcd(a, A[j])
    ans = max(ans, a)
print(ans)

### FIXED CODE ###

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

from fractions import gcd
left = [A[0]]
right = [A[-1]]

for i in range(1, N-1):
    left.append(gcd(left[-1], A[i]))
    right.append(gcd(right[-1], A[-1-i]))

ans = 1
for i in range(N):
    if i == 0:
        tmp = right[-1]
    elif i == N-1:
        tmp = left[-1]
    else:
        tmp = gcd(left[i-1], right[N-2-i])
    ans = max(ans, tmp)

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

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

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

print((K+M)/2)

### FIXED CODE ###

import sys

N,K=map(int,input().split())
P=list(map(int,input().split()))
Q=[(1+p)/2 for p in P]
temp=sum(Q[:K])
ans=temp
for i in range(N):
  try:
    temp=temp-Q[i]+Q[i+K]
    ans=max(ans,temp)
  except:
    pass
else:
  print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
BC = [[int(x) for x in input().split()] for _ in range(M)]
for i in BC:
    B, C = i
    A += [C] * B
A.sort()
print(sum(A[len(A) - N:]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
BC = [[int(x) for x in input().split()] for _ in range(M)]
BC = sorted(BC, reverse = True, key = lambda x:x[1])
N2 = N
D = []
for i in BC:
    temp = min(N2,i[0])
    D += [i[1]] * temp
    N2 -= temp
    if not N2:
        break
A += D
A.sort()
print(sum(A[len(A) - N:]))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = 0
if a[0] < 0:
    flag = -1
else:
    flag = 1
for i in range(1,n):
    if flag == -1:
        if sum(a[0:i]) + a[i] <= 0:
            cnt += -(sum(a[0:i]) + a[i]) + 1
            a[i] = -sum(a[0:i]) + 1
        flag = 1
    elif flag == 1:
        if sum(a[0:i]) + a[i] >= 0:
            cnt += sum(a[0:i]) + a[i] + 1
            a[i] = -sum(a[0:i]) - 1
        flag = -1
print(cnt)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans1,ans2 = 0,0
sum1,sum2 = 0,0
for i in range(n):
    sum1 += a[i]
    if i%2 == 1 and sum1 >= 0:
        ans1 += sum1 + 1
        sum1 = -1
    elif i%2 == 0 and sum1 <= 0:
        ans1 += -sum1 + 1
        sum1 = 1
for i in range(n):
    sum2 += a[i]
    if i%2 == 0 and sum2 >= 0:
        ans2 += sum2 + 1
        sum2 = -1
    elif i%2 == 1 and sum2 <= 0:
        ans2 += -sum2 + 1
        sum2 = 1
print(min(ans1,ans2))
### BUGGY CODE ###

import math

g = 1000000007
N, A, B, C = map(int, input().split())


fr = [1] * (2 * N)
for i in range(2, 2*N):
    fr[i] = i * fr[i-1] % g

def dot(A, B):
    return A * B % g

def po(A, B):

    return pow(A, B, g)

def add(A, B):
    return (A + B) % g

def combi(a, b):
    return fr[a] * div(1, fr[b]) * div(1, fr[a-b]) % g

def div(a, b):
    return a * pow(b, g-2, g) % g



AB = A+B
A = div(A, AB)
B = div(B, AB)
C = div(C, 100)


s = 0
for M in range(N, 2 * N):
    w = dot(add(dot(po(A, N), po(B, M - N)), dot(po(A, M-N), po(B, N))), combi(M-1, N-1) * M * div(1, add(1, -C)))
    s = add(s, w)

print(s)


### FIXED CODE ###

import math

g = 1000000007
N, A, B, C = map(int, input().split())


fr = [1] * (2 * N)
for i in range(2, 2*N):
    fr[i] = i * fr[i-1] % g

def dot(A, B):
    return A * B % g

def po(A, B):

    return pow(A, B, g)

def add(A, B):
    return (A + B) % g

def combi(a, b):
    return fr[a] * div(1, fr[b]) * div(1, fr[a-b]) % g

def div(a, b):
    return a * pow(b, g-2, g) % g



AB = A+B
A = div(A, AB)
B = div(B, AB)
C = div(C, 100)


s = 0
for M in range(N, 2 * N):
    w = dot(add(dot(po(A, N), po(B, M - N)), dot(po(A, M-N), po(B, N))), combi(M-1, N-1) * M * div(1, add(1, -C)))
    s = add(s, w)

print(s)
### BUGGY CODE ###

n = int(input())
text = []
cout = 0
for i in range(n):
  s = input()
  if s in text:
    continue
  else:
    text.append(s)
    cout += 1
print(cout)

### FIXED CODE ###

import collections

n = int(input())
text = []
for i in range(n):
  s = input()
  text.append(s)
print(len(collections.Counter(text)))
### BUGGY CODE ###

import sys
from functools import reduce
mod=10**9+7
input=sys.stdin.readline
def f(A,B):
 if B==0:
  den=1
  num=1
 else:
  den=reduce(lambda x,y:x*y%mod,range(A,A-B,-1))
  num=reduce(lambda x,y:x*y%mod,range(1,B+1))
    
 return den*pow(num,mod-2,mod)%mod

n,k=map(int,input().split())
ans=0
for i in range(min(n-1,k)+1):
 ans+=f(n,i)*f(n-1,i)%mod
print(ans%mod)


### FIXED CODE ###

mod=10**9+7
n,k=map(int,input().split())
ans=0
comb1=1 #初期値はNC0=1
comb2=1 #初期値は(N-1)C0=1
for i in range(min(k+1,n)): #0人の部屋は高々N-1個しか
 # 存在しないので操作回数は高々min(K,N-1)回となる
 ans+=comb1*comb2 #0人の部屋がi個のときの場合の数は
 # NCi*(N-1)Ci
 ans%=mod
 comb1*=(n-i)*pow(i+1,mod-2,mod) #NC(i+1)はNC
 # i*(N-i)/(i+1)で求められる
 comb1%=mod
 comb2*=(n-1-i)*pow(i+1,mod-2,mod) #(N-1)C(i+1
 # )は(N-1)Ci*((N-1)-i)/(i+1)で求められる
 comb2%=mod
print(ans)
### BUGGY CODE ###

s = str(input())

s = [_ for _ in s]
for i in range(0, len(s)-1):
    if i+2 <= len(s)-1:
        if s[i] == s[i+1]:
            s[i+1] = ''.join([s[i+1], s.pop(i+2)])

if s[-1] == s[-2]:
    print(len(s) - 1)
else:
    print(len(s))

### FIXED CODE ###

s = str(input())

j = 0
count = len(s)

s = [_ for _ in s]
for i in range(0, len(s)-1):
    if j+1 <= len(s)-1:
        if s[j] == s[j+1]:
            j = j + 3
            count -= 1
        else:
            j = j + 1
            continue

print(count)
### BUGGY CODE ###

N, A, B, K = map(int, input().split())
mod = 998244353

fac = [1]
inv = [1]
for i in range(1, N + 1) :
    fac.append(fac[-1] * i % mod)
    inv.append(pow(fac[-1], mod - 2, mod))

ret = 0
for na in range(N + 1) :
    if (K - na * A) % B != 0 :
        continue
        
    nb = (K - na * A) // B
    for ng in range(min(na, nb) + 1) :
        if not 0 <= na + nb - ng <= N :
            continue
        ret += fac[N] * inv[na-ng] * inv[nb-ng] * inv[ng] * inv[N-na-nb+ng] % mod
        ret %= mod
        
print(ret)

### FIXED CODE ###

N, A, B, K = map(int, input().split())
mod = 998244353

fac = [1]
inv = [1]
for i in range(1, N + 1) :
    fac.append(fac[-1] * i % mod)
    inv.append(pow(fac[-1], mod - 2, mod))

ret = 0
for na in range(N + 1) :
    if (K - na * A) % B != 0 :
        continue
        
    nb = (K - na * A) // B
    if 0 <= na <= N and 0 <= nb <= N :
        ret += fac[N] * inv[N-na] * inv[na] * fac[N] * inv[N-nb] * inv[nb]
        ret %= mod
        
print(ret)
### BUGGY CODE ###

N, M = map(int, input().split())
g = {}
for i in range(M):
  a, b = map(int, input().split())
  if a in g.keys():
    g[a].append(b)
  else:
    g[a] = [b]
  if b in g.keys():
    g[b].append(a)
  else:
    g[b] = [a]
ans = [0 for _ in range(N+1)]
#print(g)
current = [1]
while 0 in ans[2:]:
  #print(ans)
  for i in current:
    next = []
    #print('i',i)
    for j in g[i]:
      if ans[j] == 0:
        ans[j] = i
        next.append(j)
  current = next
print('Yes')
for i in range(2,N+1):
  print(ans[i])


### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
N, M = map(int, input().split())
g = defaultdict(list)
for i in range(M):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)
que = [1]
ans = [0 for _ in range(N+1)]
while len(que)>0:
  current = que.pop(0)
  for next in g[current]:
    if ans[next] == 0:
      que.append(next)
      ans[next] = current
print('Yes')
for i in range(2,N+1):
  print(ans[i])
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
lr=[list(map(int,input().split())) for i in range(q)]
for i in lr:
    print(s[i[0]-1:i[1]].count("AC"))

### FIXED CODE ###

n,q = map(int,input().split())
s = "p" + str(input())
lr = [list(map(int,input().split())) for i in range(q)]
cnt = 0
ans = [0] * (n+1)
for i in range(1,n+1):
    if s[i-1] == "A" and s[i] == "C":
        cnt += 1
    ans[i] = cnt
for i in lr:
    print(ans[i[1]] - ans[i[0]])
### BUGGY CODE ###

from itertools import product
h, w = map(int, input().split())
S = [input() for _ in range(h)]
L = [[0]*w for _ in range(h)]
R = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]
for i, j in product(range(h),range(w)):
    l = S[i][j]
    r = S[i][w-1-j]
    u = S[i][j]
    d = S[h-1-i][j]
    if l == ".": L[i][j] = L[i][max(0, j-1)]+1
    if r == ".": R[i][w-1-j] = R[i][min(w-1, w-j)]+1
    if u == ".": U[i][j] = U[max(0, i-1)][j]+1
    if d == ".": D[h-1-i][j] = D[min(h-1, h-i)][j]+1
A = [L[i][j]+R[i][j]+U[i][j]+D[i][j]-3 for i, j in product(range(h), range(w))]
print(max(A))

### FIXED CODE ###

from itertools import product
h, w = map(int, input().split())
S = [input() for _ in range(h)]
L = [[0]*w for _ in range(h)]
R = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]
for i, j in product(range(h),range(w)):
    l = S[i][j]
    r = S[i][w-1-j]
    u = S[i][j]
    d = S[h-1-i][j]
    if l == ".": L[i][j] = L[i][max(0, j-1)]+1
    if r == ".": R[i][w-1-j] = R[i][min(w-1, w-j)]+1
    if u == ".": U[i][j] = U[max(0, i-1)][j]+1
    if d == ".": D[h-1-i][j] = D[min(h-1, h-i)][j]+1
A = [L[i][j]+R[i][j]+U[i][j]+D[i][j]-3 for i, j in product(range(h), range(w))]
print(max(A))
### BUGGY CODE ###

N, M = map(int, input().split())
if N == 1:
    print(1)
    exit()

a = [int(input()) for i in range(M)]
if M == 0:  a.append(0)
ans = [0] * (N+1)
ans[0] = 1
if a[0] != 1:   ans[1] = 1
else:   pass
for i in range(2, N+1):
    if a.count(i) >= 1:
        ans[i] = 0
    else:
        ans[i] = (ans[i-1] + ans[i-2]) % (10**9+7)
print(ans[N])

### FIXED CODE ###

import bisect
N, M = map(int, input().split())
if N == 1:
    print(1)
    exit()

a = [int(input()) for i in range(M)]
broken = [0]*(N+1)
for i in range(M):
    broken[a[i]] = 1
if M == 0:  a.append(0)
ans = [0] * (N+1)
ans[0] = 1
if a[0] != 1:   ans[1] = 1
else:   pass
for i in range(2, N+1):
    if broken[i] == 1:
        ans[i] = 0
    else:
        ans[i] = (ans[i-1] + ans[i-2]) % (10**9+7)
print(ans[N])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
import heapq
import numpy as np
import math

def main():
    N, K = map(int, input().split())
    A = [int(c) for c in input().split()]
    F = [int(c) for c in input().split()]
    
    A.sort()
    F.sort(reverse=True)

    A = np.array(A)
    F = np.array(F)

    num = 0
    sum_ = A * F
    left = 0
    right = 10 ** 12
    while(num < 100):
        number = 0
        mid = (left + right) // 2
        # print(mid)
        for i in range(len(A)):
            if sum_[i] <= mid:
                continue
            else:
                number += math.ceil((sum_[i] - mid) / F[i])
            # print(number)
        if number > K:
            # 最大値をmidより小さくできない -> 最大値はもっとでかい
            left = mid + 1
        else:
            right = mid
        num += 1
    print(mid)
                
        



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
import heapq
import math
 
def main():
    N, K = map(int, input().split())
    A = [int(c) for c in input().split()]
    F = [int(c) for c in input().split()]
    
    A.sort()
    F.sort(reverse=True)
 
    num = 0
    sum_ = []
    for i in range(N):
      sum_.append(A[i] * F[i])
    left = 0
    right = 10 ** 12
    while(num < 90):
        number = 0
        mid = (left + right) // 2
        # print(mid)
        for i in range(len(A)):
            if sum_[i] <= mid:
                continue
            else:
                number += math.ceil((sum_[i] - mid) / F[i])
            # print(number)
        if number > K:
            # 最大値をmidより小さくできない -> 最大値はもっとでかい
            left = mid + 1
        else:
            right = mid
        num += 1
    print(mid)
                
        
 
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from bisect import bisect_left
s = list(input())
t = list(input())
N = len(s)
if not set(t) <= set(s):
    print(-1)
    exit()
lis = [[] for _ in range(26)]
s = s+s
for i in range(2*N):
    alp = ord(s[i])-97
    lis[alp].append(i+1)
nex = [[0]*N for _ in range(26)]
for now in range(N):
    for alp in range(26):
        if not lis[alp]:
            continue
        i = bisect_left(lis[alp],now+1)
        #print(lis[alp],now+1,i)
        nex[alp][now] = lis[alp][i] - now
ans = 0
now = 0
tN = len(t)
for i in range(tN):
    alp = ord(t[i])-97
    ne = nex[alp][now]
    ans += ne
    if now+ne >= N:
        now += ne-N
    else:
        now += ne
    #print(now,ans)
print(ans)

### FIXED CODE ###

from bisect import bisect_left
s = list(input())
t = list(input())
N = len(s)
if not set(t) <= set(s):
    print(-1)
    exit()
lis = [[] for _ in range(26)]
s = s+s
for i in range(2*N):
    alp = ord(s[i])-97
    lis[alp].append(i+1)
nex = [[0]*N for _ in range(26)]
for now in range(N):
    for alp in range(26):
        if not lis[alp]:
            continue
        i = bisect_left(lis[alp],now+1)
        #print(lis[alp],now+1,i)
        nex[alp][now] = lis[alp][i] - now
ans = 0
now = 0
tN = len(t)
for i in range(tN):
    alp = ord(t[i])-97
    ne = nex[alp][now]
    ans += ne
    if now+ne >= N:
        now += ne-N
    else:
        now += ne
    #print(now,ans)
print(ans)