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

def main():
    n, k = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    f = sorted(list(map(int, input().split())), reverse=True)

    def b_search(a, b, value):
        while a+1 < b:
            med = (a+b)//2
            if value(med):
                b = med
            else:
                a = med+1
        if a == b:
            return a
        else:
            if value(a):
                return a
            else:
                return b

    def count(val):
        cnt = 0
        for i in range(n):
            cnt += max(a[i]-val//f[i], 0)
        if cnt > k:
            return False
        else:
            return True

    print(b_search(0, 10**12+10, count))


main()


### FIXED CODE ###

def main():
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    f=sorted(list(map(int,input().split())),reverse=True)
    def b_search(a,b,value,lim):
        med=(a+b)//2
        if a==b:return a
        elif lim=="upper":
            if a+1==b:
                if value(b):return b
                else:return a
            elif value(med):return b_search(med,b,value,lim)
            else:return b_search(a,med-1,value,lim)
        else:
            if a+1==b:
                if value(a):return a
                else:return b
            elif value(med):return b_search(a,med,value,lim)
            else:return b_search(med+1,b,value,lim)

    def count(val):
        cnt=0
        for i in range(n):
            cnt+=max(a[i]-val//f[i],0)
        if cnt>k:
            return False
        else:
            return True
    
    print(b_search(0,10**12+10,count,"lower"))
    
main()
### BUGGY CODE ###

nkq = list(map(int, input().split()))
n = nkq[0]
k = nkq[1]
q = nkq[2]
aes = []
for _ in range(q):
    aes.append(int(input()))

points = [k] * n
for a in aes:
    points =list(map(lambda p: p-1, points))
    points[a-1] = points[a-1] + 1
    
answer = [ "Yes" if p >0  else "No" for p in points]
for ans in answer:
    print(ans)

### FIXED CODE ###

import numpy as np
nkq = list(map(int, input().split()))


n = nkq[0]
k = nkq[1]
q = nkq[2]
aes = []
for _ in range(q):
    aes.append(int(input()))
    


points = np.zeros(n)  + (k - q)
for a in aes:
    points[a-1] = points[a-1] + 1

for p in points:
    if p > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
while len(a) >= 2 :
    k = a[1] % a[0]
    if k == 0 :
        a.pop(1)
    else :
        a[1] = k
    a.sort()
print(a[0])


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
while len(a) >= 2 :
    k = a[1] % a[0]
    if k == 0 :
        a.pop(1)
    else :
        a[1] = k
        a[0], a[1] = a[1], a[0]
print(a[0])
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import Counter
import bisect
from decimal import *
def main():
    N, D, A = MI()
    Enemy = []
    for i in range(N):
        x, h = MI()
        Enemy.append([x, h])
    Enemy.sort(key=lambda list: list[0])
    cnt = 0
    for i in range(N):
        if Enemy[i][1] <= 0:
            continue
        else:
            ata = math.ceil(Decimal(Enemy[i][1]) / Decimal(A))
            cnt += ata
            ran = Enemy[i][0] + 2 * D
            dam = ata * A
            for j in range(i + 1, N):
                if Enemy[j][0] <= ran:
                    Enemy[j][1] -= dam
                else:
                    break
    print(cnt)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import defaultdict
from collections import deque
import bisect
from decimal import *
def main():
    N, D, A = MI()
    Enemy = defaultdict()
    Enemy_ran = []
    for i in range(N):
        x, h = MI()
        Enemy[x] = h
        Enemy_ran.append(x)
    Enemy_ran.sort()
    cnt = 0
    dam_list = deque()
    dam_all = 0
    for i in range(N):
        x = Enemy_ran[i]
        while len(dam_list) != 0 and i >= dam_list[0][0]:
            dam_all -= dam_list.popleft()[1]
        HP = Enemy[x] - dam_all
        if HP <= 0:
            continue
        else:
            ata = math.ceil(Decimal(HP) / Decimal(A))
            cnt += ata
            ran = x + 2 * D
            y = bisect.bisect_right(Enemy_ran, ran)
            dam = ata * A
            dam_list.append((y, dam))
            dam_all += dam


    print(cnt)


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

import math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=qb
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
def dq():
	return queue.deque()
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1

n,c,k = readInts()
t = []
for i in range(n):
	t.append(readInt())
t.sort()

def people(n):
	ans = 0
	for i in t:
		if n>=i:
			ans+=1
		else:
			break
	#print(n,t,ans)
	return ans

ans = 0
while len(t)>0:
	pi = t[0]
	mens = 1
	for i in range(1,len(t)):
		if pi+k>=t[i]:
			mens+=1
		else:
			break
	bus = mens//c
	if bus!=0:
		ans+=bus
		t = t[bus*c:]
	else:
		ans+=1
		t = t[mens:]

	#print(pi,mens,bus,t)
print(ans)

### FIXED CODE ###

import bisect

n,c,k = list(map(int, input().split()))
t = []
for i in range(n):
	t.append(int(input()))
t.sort()

ans = 0
remain = c-1
if c==1:
	print(n)
	exit()
time = t[0]
for i in range(1,len(t)):
	if time+k<t[i]:
		time = t[i]
		remain = c
		ans+=1
	if remain==0:
		remain=c
		time = t[i]
		ans+=1
	remain-=1

print(ans+1)
### BUGGY CODE ###

def f(k, a_s):
    md = 10 ** 9 + 7
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in a_s[:-1]:
        dp[-1], R = sum(dp[k - a:]) % md, dp[-1]
        for j in range(k - 1, a - 1, -1):
            dp[j], R = (dp[j + 1] - R + dp[j - a]) % md, dp[j]
        for j in range(a - 1, -1, -1):
            dp[j], R = (dp[j + 1] - R) % md, dp[j]
    return sum(dp[k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(k, a_s))


### FIXED CODE ###

def f(n, k, a_s):
    md = 10 ** 9 + 7
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in a_s[:-1]:
        ndp = [0] * (k + 1)
        ndp[0] = s = dp[0] % md
        for j in range(1, a + 1):
            ndp[j] = s = (s + dp[j]) % md
        for j in range(a + 1, k + 1):
            ndp[j] = s = (s + dp[j] - dp[j - a - 1]) % md
        dp = ndp
    return sum(dp[k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(n, k, a_s))
### BUGGY CODE ###

from collections import deque

s = str(input())
n=len(s)
left :int=1
mlist=deque("0")
while left<int(n)+1:
  m = int(s[n-left:n])%2019
  mlist.append(str(m))
  left+=1

ll=len(mlist)
l=len(set(mlist))
print(ll-l)

### FIXED CODE ###

import time

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

#start = time.time()#計測始
ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
#end = time.time()#計測終
#print(f"{end-start}sec.")#計測出力
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split(' ')))
l=0
T=[]
for i in range(N):
    for j in range(N):
        for k in range(N):
            if i!=k and i!=j and j!=k:
                u=[i,j,k]
                u.sort()
                if u not in T:
                    T.append(u)
                    if 2*max(L[i],L[j],L[k])<L[i]+L[j]+L[k] and L[i]!=L[k] and L[i]!=L[j] and L[j]!=L[k]:
                        l=l+1
print(l)

### FIXED CODE ###

import itertools
N=int(input())
L=list(map(int,input().split(' ')))
l=0
T=[]
for u in list(itertools.combinations(L, 3)):
    i,j,k=u
    if 2*max(i,j,k)<i+j+k and i!=k and i!=j and j!=k:
        l=l+1
print(l)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

ans_list = []
for i in a:
    for j in b:
        ans_list.append(i+j)
ans_list.sort(reverse=True)
ans_list = ans_list[:min(3001, x*y*z+1)]
ans_list_2 = []
for i in ans_list:
    for j in c:
        ans_list_2.append(i+j)
ans_list_2.sort(reverse=True)
for i in range(k):
    print(ans_list_2[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
p = []
for i in a:
    for j in b:
        p.append(i+j)
p.sort(reverse=True)
p = p[:min(3001, x*y*z+1)]
q = []
for j in c:
    for i in p:
        q.append(i+j)
q.sort(reverse=True)
for i in range(k):
    print(q[i])
### BUGGY CODE ###

import sys
S=sys.stdin.readline().strip()
if int(S)<=10**9:
    A=["0","0",S,"0","0","1"]
    print(" ".join(A))
else:
    for a in range(0,10**9):
        for b in range(0,10**9):
            for c in range(0,10**9):
                for d in range(0,10**9):
                    for e in range(0,10**9):
                        for f in range(0,10**9):
                            T=abs((c-a)*(f-b)-(d-b)*(e-a))
                            if S==T:
                                A=[str(a),str(b),str(c),str(d),str(e),str(f)]
                                print(" ".join(A))
                                exit()

### FIXED CODE ###

s=int(input());l=10**9;n=0--s//l;print(0,0,1,l,n,n*l-s)
### BUGGY CODE ###

import math

N = int(input())

a = pow(10,12)

is_not_prime = False
for k in range(2, int(math.sqrt(N)) + 1):
    if N % k == 0:
        is_not_prime = True
        break
if is_not_prime:
    for i in range(1, N):

        j = N/i
        if j.is_integer():

            if (i+int(j)) < a:
                a = i+int(j)

    print(a - 2)
else:
    print(N - 1)

### FIXED CODE ###

import math

N = int(input())

a = pow(10,12)

is_not_prime = False
#for k in range(2, int(math.sqrt(N)) + 1):
#    if N % k == 0:
#        is_not_prime = True
#        break
#if is_not_prime:
for i in range(1, int(math.sqrt(N))+1):
    #print(i)
    j = N/i
    if j.is_integer():

        if (i+int(j)) < a:
            a = i+int(j)
    #if j < 2:
    #    break

print(a - 2)
#else:
#    print(N - 1)
### BUGGY CODE ###

# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
def resolve():
    # 最短経路問題で使われるアルゴリズムの１つ。
    # グラフ上の全ての頂点間の最短経路を探す
    # 負の閉路（辺の重みの和が負になるような閉路）がない限り、負の辺があっても使える。

    # 負の閉路を持つ場合は'NEGATIVE CYCLE'を、そうでない場合には(i,j)成分に
    # 頂点iから頂点jへの最短経路の距離を格納するdist_listをprintする関数
    def warshall_floyd(v_num, e_num, dist_lst):

        # 負の閉路を持つか

        # 頂点iから頂点jへの経路と、頂点kを経由した場合の経路とを比較して
        # よりコストの合計が小さい方を配列に入れる動的計画法
        for k in range(v_num):
            for i in range(v_num):
                for j in range(v_num):
                    # i→k→jがつながっててしかもi→jルートよりもイケてるなら更新
                    if dist_lst[i][k] != INF and dist_lst[k][j] != INF:
                        if dist_lst[i][j] > dist_lst[i][k] + dist_lst[k][j]:
                            dist_lst[i][j] = dist_lst[i][k] + dist_lst[k][j]

        ans=[0]*N
        for lst in dist_lst:
            for i in range(len(lst)):
                ans[lst[i]]+=1

        for j in range(1,N):
            print(ans[j]//2)

    N,X,Y=map(int,input().split())
    # 頂点の数と辺の数
    v_num, e_num = N,N

    # 配列dist_lst[a][b]には頂点a,b間の辺のコストを入れておき、
    # a=bの時は0を、a,b間の辺が存在しないときはINFを入れておく。
    INF = 10 ** 20
    dist_lst = [[INF] * v_num for _ in range(v_num)]

    for i in range(v_num-1):
        dist_lst[i][i+1] = 1
        dist_lst[i+1][i]=1
    dist_lst[X-1][Y-1] = 1
    dist_lst[Y-1][X-1] = 1


    for v in range(v_num):
        dist_lst[v][v] = 0

    warshall_floyd(v_num, e_num, dist_lst)





resolve()

### FIXED CODE ###

# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np

def resolve():
    from heapq import heappush, heappop

    # 長点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    N,X,Y=map(int,input().split())
    V, E= N,N
    g = [[] for i in range(V)]

    for i in range(N-1):
        g[i].append((1, i+1))
        g[i+1].append((1, i))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
        # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
    g[X-1].append((1, Y-1))
    g[Y-1].append((1, X-1))

    INF = 10 ** 10
    ans = [0] * N

    for r in range(N):
        for i in dijkstra(V, g, r):
            if i<INF:
                ans[i]+=1

    for j in range(1, N):
        print(ans[j] // 2)


resolve()
### BUGGY CODE ###

from collections import deque

he,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
l = [list(input()) for i in range(he)]

sx -= 1
sy -= 1
gx -= 1
gy -= 1
q = deque([])
d = [[float("INF")]*w for i in range(he)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
d[sx][sy] = 0
q.append((0,sx,sy))
while q:
    dis,bx,by = q.popleft()
    if bx == gx and by == gy:
        continue
    for i in range(4):
        for j in range(1,k+1):
            nx = bx+dx[i]*j
            ny = by+dy[i]*j
            if 0 > nx or 0 > ny or nx >= he  or ny >= w:
                break
            if l[nx][ny] == "@":
                break
            if d[nx][ny] <= dis:
                break
            if d[nx][ny] > dis+1:
                d[nx][ny] = dis+1
                q.append((dis+1,nx,ny))

if d[gx][gy] == float("INF"):
    print(-1)
else:
    print(d[gx][gy])


### FIXED CODE ###

from collections import deque

he,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
l = [list(input()) for i in range(he)]

sx -= 1
sy -= 1
gx -= 1
gy -= 1
q = deque([])
d = [[float("INF")]*w for i in range(he)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
d[sx][sy] = 0
q.append((0,sx,sy))
while q:
    dis,bx,by = q.popleft()
    if bx == gx and by == gy:
        continue
    for i in range(4):
        for j in range(1,k+1):
            nx = bx+dx[i]*j
            ny = by+dy[i]*j
            if 0 > nx or 0 > ny or nx >= he  or ny >= w:
                break
            if l[nx][ny] == "@":
                break
            if d[nx][ny] <= dis:
                break
            if d[nx][ny] > dis+1:
                d[nx][ny] = dis+1
                q.append((dis+1,nx,ny))

if d[gx][gy] == float("INF"):
    print(-1)
else:
    print(d[gx][gy])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
diff_i = [A[i] + i + 1 for i in range(N)]
diff_j = [i + 1 - A[i] for i in range(N)]
diff = set(diff_i) & set(diff_j)
ans = 0
for d in diff:
    ans += diff_i.count(d) * diff_j.count(d)
print(ans)


### FIXED CODE ###

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

cnt1 = {}
cnt2 = {}

for i in range(N):
    tmp1 = A[i] + i + 1
    tmp2 = i + 1 - A[i]
    if tmp1 not in cnt1:
        cnt1[tmp1] = 1
    else:
        cnt1[tmp1] += 1
    if tmp2 not in cnt2:
        cnt2[tmp2] = 1
    else:
        cnt2[tmp2] += 1

diff = set(list(cnt1.keys())) & set(list(cnt2.keys()))

ans = 0
for d in diff:
    ans += cnt1[d] * cnt2[d]
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0

for i in range((N//R)+1):
    r = i
    for j in range(((N-R*r)//G)+1):
        g = j
        if (N-R*r-G*g) % B == 0:
            b = N-R*r-G*g
            if b >= 0:
                ans += 1

print(ans)

### FIXED CODE ###

def main():

    R, G, B, N = map(int, input().split())

    ans = 0

    for i in range((N//R)+1):
        r = i
        for j in range(((N-R*r)//G)+1):
            g = j
            if (N-R*r-G*g) % B == 0 and N-R*r-G*g >= 0:
                ans += 1

    print(ans)

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

h, w, d = map(int, input().split(' '))
matrix = [list(map(int, input().split(' '))) for _ in range(h)]
q = int(input())
lr = [list(map(int, input().split(' '))) for _ in range(q)]


for l, r in lr:
    cnt = 0
    for i in range(h):
        for j in range(w):
            if matrix[i][j] == l:
                x = i
                y = j
                
    while l != r:
        l = l + d
        for i in range(h):
            for j in range(w):
                if matrix[i][j] == l:
                    cnt += abs(x - i) + abs(y - j)
                    x = i
                    y = j
                    
    print(cnt)

### FIXED CODE ###

h, w, d = map(int, input().split(' '))

comp = {}
for i in range(h):
    tmp = list(map(int, input().split(' ')))
    for j in range(w):
        comp[tmp[j]] = [i, j]

q = int(input())
lr = [map(int, input().split(' ')) for _ in range(q)]

dp = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
    cnt = dp[i - d]
    cnt += abs(comp[i][0] - comp[i - d][0])
    cnt += abs(comp[i][1] - comp[i - d][1])    
    dp[i] = cnt
    

for l, r in lr:
    print(dp[r] - dp[l])
### BUGGY CODE ###

n,m = map(int,input().split())
key = []
for i in range(1,n+1):
    key.append(i)
ans = []
for i in range(m):
    ls = []
    L,R = map(int,input().split())
    for j in range(L,R+1):
        ls.append(j)
    key = (set(ls)&set(key))
    
print(len(key))
    


### FIXED CODE ###

n,m = map(int,input().split())
key = []
for i in range(1,n+1):
    key.append(i)
    
ls = [0,100000]
for i in range(m):
    L,R = map(int,input().split())
    if L > ls[0]:
        ls[0] = L
    if R < ls[1]:
        ls[1] = R
    
ans = []    
for i in range(ls[0],ls[1]+1):
    ans.append(i)
    
print(len(set(ans)&set(key)))
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
grid = []
for _ in range(H):
    grid.append([s for s in input()])

def dfs(h, w):
    cnt = 0
    if grid[h][w] == "#":
        return cnt
    q = deque([(h, w, "No")])
    cnt += 1
    while q:
        h, w, direct = q.pop()
        for i, j in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            if direct == "No" or direct == (i, j):
                if 0 <= h + i < H and 0 <= w + j < W and grid[h + i][w + j] == ".":
                        cnt += 1
                        q.append((h + i, w + j, (i, j)))
 
    return cnt 
    
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, dfs(h, w))
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
grid = []
for _ in range(H):
    grid.append([s for s in input()])
    
left = [[0 for _ in range(W)] for _ in range(H)]
right = [[0 for _ in range(W)] for _ in range(H)]
up = [[0 for _ in range(W)] for _ in range(H)]
down = [[0 for _ in range(W)] for _ in range(H)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == ".":
            if w == 0:
                left[h][w] = 1
            else:
                left[h][w] += left[h][w - 1] + 1

for h in range(H):
    for w in range(W)[::-1]:
        if grid[h][w] == ".":
            if w == W - 1:
                right[h][w] = 1
            else:
                right[h][w] += right[h][w + 1] + 1
            
for w in range(W):
    for h in range(H):
        if grid[h][w] == ".":
            if h == 0:
                up[h][w] = 1
            else:
                up[h][w] += up[h - 1][w] + 1
                
for w in range(W):
    for h in range(H)[::-1]:
        if grid[h][w] == ".":
            if h == H - 1:
                down[h][w] = 1
            else:
                down[h][w] += down[h + 1][w] + 1
                
ans = -10000
for h in range(H):
    for w in range(W):
        ans = max(ans, up[h][w] + down[h][w] + right[h][w] + left[h][w] - 3)
print(ans)