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

import heapq as hq

def relax(u, v, w):
    if D[u] + w < D[v]:
        D[v] = D[u] + w
        P[v] = u
        for h in H:
            if h[1] == v:
                h[0] = D[v]
        hq.heapify(H)

INF = float('inf')
N = int(input())
D = [INF for i in range(N)]
P = [None for i in range(N)]
D[0] = 0

G = [{} for i in range(N)]
for i in range(N):
    x = list(map(int, input().split()))
    g = x[2:]
    for j, n in enumerate(g):
        if j % 2 == 0:
            G[i][n] = g[j + 1]

H = [[D[i], i] for i in range(N)]
hq.heapify(H)
S = set()

while 0 < len(H):
    d_u, u = hq.heappop(H)
    S.add(u)
    for v, w in G[u].items():
        if not (v in S):
            relax(u, v, w)

for i, d in enumerate(D):
    print('{0} {1}'.format(i, d))

### FIXED CODE ###

import heapq as hq

def relax(u, v, w):
    if D[u] + w < D[v]:
        D[v] = D[u] + w
        P[v] = u
        hq.heappush(H, (D[v], v))

INF = float('inf')
N = int(input())
D = [INF for i in range(N)]
P = [None for i in range(N)]
D[0] = 0

G = [{} for i in range(N)]
for i in range(N):
    x = list(map(int, input().split()))
    g = x[2:]
    for j, n in enumerate(g):
        if j % 2 == 0:
            G[i][n] = g[j + 1]

H = [(0, 0)]

while 0 < len(H):
    d_u, u = hq.heappop(H)
    for v, w in G[u].items():
        relax(u, v, w)

for i, d in enumerate(D):
    print('{0} {1}'.format(i, d))
### BUGGY CODE ###

import sys
import numpy as np
readline = sys.stdin.buffer.readline

N,K = map(int,readline().split())
people = np.array(readline().split(),np.int64)
food = np.array(readline().split(),np.int64)
 
people.sort()
food.sort()
food=food[::-1]

#2分探索　Kの値で
_max = 10**12
_min = 0

while _max!=_min:
  mean = (_max+_min)//2
  # 各人が修行をする回数の配列　負の値もでる
  K_arr = np.maximum(0,people - mean//food)
  # 総修行回数
  _K = sum(K_arr)
  if _K > K:
    _min = mean+1
  else:
    _max = mean
    
print(_max)
  

### FIXED CODE ###

import sys
import numpy as np
readline = sys.stdin.buffer.readline

N,K = map(int,readline().split())
people = np.array(readline().split(),np.int64)
food = np.array(readline().split(),np.int64)
 
people.sort()
food.sort()
food=food[::-1]

#2分探索　Kの値で
_max = max(people)*max(food)
_min = 0

while _max>_min:
  mean = (_max+_min)//2
  # 各人が修行をする回数の配列　負の値もでる
  _K = np.maximum(0,people - mean//food).sum()
  if _K > K:
    _min = mean+1
  else:
    _max = mean
    
print(_max)
### BUGGY CODE ###

a, b, k = map(int, input().split())

for i in range(a, b + 1):
    if a <= i <= a + k - 1 or b - k + 1 <= i <= b:
        print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())

res = []
for i in range(a, min(b + 1, a + k)):
    res.append(i)


for i in range(max(a, b - k + 1), b + 1):
    if i not in res:
        res.append(i)

res = sorted(res)
for i in res:
    print(i)
### BUGGY CODE ###

N = int(input())
A_list = list(map(int, input().split()))
MOD = 10**9 + 7

zeros = [0] * 61
ones = [0] * 61

for a in A_list:
    for i, b in enumerate([1 if (a >> j & 1) else 0 for j in range(61)]):
        if b == 1:
            ones[i] += 1
        else:
            zeros[i] += 1

res = 0
for a in A_list:
    twice = 1
    for i, b in enumerate([1 if (a >> j & 1) else 0 for j in range(61)]):
        if b == 1:
            cnt = zeros[i]
            ones[i] -= 1
        else:
            cnt = ones[i]
            zeros[i] -= 1
        res += twice * cnt
        twice *= 2
    res %= MOD
print(res)

### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
MOD = 10**9 + 7

zeros = [0] * 61
ones = [0] * 61

for a in A_list:
    for i, b in enumerate([1 if (a >> j & 1) else 0 for j in range(61)]):
        if b == 1:
            ones[i] += 1
        else:
            zeros[i] += 1

res = 0
for a in A_list:
    twice = 1
    for i, b in enumerate([1 if (a >> j & 1) else 0 for j in range(61)]):
        if b == 1:
            cnt = zeros[i]
            ones[i] -= 1
        else:
            cnt = ones[i]
            zeros[i] -= 1
        res += twice * cnt
        twice *= 2
    res %= MOD
print(res)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        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 -self.parents[self.find(x)]

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

    def members(self, x):
        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()}


n, m = map(int, input().split())
p_list = list(map(int, input().split()))
q_list = []
for item in p_list:
    q_list.append(item-1)

uni = UnionFind(n)

for i in range(m):
    x, y = map(int, input().split())
    uni.union(x-1, y-1)

ret = 0

tmp_dict = uni.all_group_members()

for item in tmp_dict:
    t_list = tmp_dict[item]
    tmp = []
    for var in t_list:
        tmp.append(q_list[var])
    ret += len(set(tmp) & set(t_list))

print(ret)


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parents[x] == x:
            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.rank[x] < self.rank[y]:
            self.parents[x] = y
        else:
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


n, m = map(int, input().split())
p_list = list(map(int, input().split()))
q_list = list(map(lambda x: x - 1, p_list))

uni = UnionFind(n)

for i in range(m):
    x, y = map(int, input().split())
    uni.union(x-1, y-1)

ret = 0

tmp_dict = dict()

for i in range(n):
    parent = uni.find(i)
    if parent in tmp_dict:
        tmp_dict[parent].append(i)
    else:
        tmp_dict[parent] = [i]

for item in tmp_dict:
    t_list = tmp_dict[item]
    tmp = set()
    for var in t_list:
        tmp.add(q_list[var])
    ret += len(tmp & set(t_list))

print(ret)
### BUGGY CODE ###

import numpy as np


N = int(input())
A = [int(i) for i in input().split(' ')]
cnt = 0
first = 0
xsum_old = 0
r_old = 0
for l in range(0, N):
    xsum = xsum_old
    first = A[l]
    cnt += r_old - l
    for r in range(r_old, N):
        if np.bitwise_and(xsum, A[r]) > 0:
            xsum_old = xsum - first
            r_old = r
            break
        xsum += A[r]
        cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
A_raw = input()
A = [int(i) for i in A_raw.split(' ')]
cnt = 0
first = 0
xsum_old = 0
r_old = 0
for l in range(0, N):
    xsum = xsum_old
    first = A[l]
    cnt += r_old - l
    isBreak = False
    for r in range(r_old, N):
        if xsum & A[r] > 0:
            xsum_old = xsum - first
            r_old = r
            isBreak = True
            break
        xsum += A[r]
        cnt += 1
    if isBreak == False:
        r_old = r
print(cnt)
### BUGGY CODE ###


n = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

A.sort()
B.sort()
C.sort()

cnt = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            if A[i] < B[j] < C[k]:
                cnt += 1

print(cnt)

### FIXED CODE ###

import bisect

n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

a = sorted(a)
b = sorted(b)
c = sorted(c)

ans = 0

for x in b:
    aa = bisect.bisect_left(a,x)
    cc = len(c) - bisect.bisect_right(c,x)
    ans += aa * cc

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

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

ans = 0
check = 0
check_A = [0]
check_B = [0]

for n in range(N):
    check_A.append(check_A[n] + A[n])

for m in range(M):
    check_B.append(check_B[m] + B[m])

for n in range(N+1):
    if check_A[n] > K:
        break
    for m in range(M+1):
        if check_B[m] > K:
            break
        calc = check_A[n] + check_B[m]
        if calc > K:
            break
        if check <= calc:
            check = calc
            ans = n + m

print(ans)

### FIXED CODE ###

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

check_A = [0]
check_B = [0]

for a in range(N):
    check_A.append(check_A[a] + A[a])

for b in range(M):
    check_B.append(check_B[b] + B[b])

ans = 0
j = M

for i in range(N+1):
    if check_A[i] > K:
        break
    while check_B[j] > K - check_A[i]:
        j -= 1
    ans = max(ans, i+j)

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

# https://atcoder.jp/contests/abc159/submissions/11139418

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *a, = map(int, input().split())

    dp = [[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 1

    for i, x in enumerate(a):
        for j in range(S + 1):
            # 選択しない
            dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][0]) % MOD
            dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][0] + dp[i][j][1]) % MOD
            dp[i + 1][j][2] = (dp[i + 1][j][2] + dp[i][j][0] + dp[i][j][1] + dp[i][j][2]) % MOD

            # 選択する
            pj = j - x
            if pj < 0: continue
            dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][pj][0] + dp[i][pj][1]) % MOD
            dp[i + 1][j][2] = (dp[i + 1][j][2] + dp[i][pj][0] + dp[i][pj][1]) % MOD

    ret = dp[N][S][2]
    print(ret)


if __name__ == '__main__':
    main()

# 0: 開始していないが開始して選択することができる
# 1: 開始しており選択を選べる
# 2: 閉じており選択できない


### FIXED CODE ###

# https://atcoder.jp/contests/abc159/submissions/11139734

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *a, = map(int, input().split())

    dp = [0] * (S + 1)

    ret = 0
    for i, x in enumerate(a):
        dp[0] += 1
        if x > S: continue
        ret = (ret + dp[S - x] * (N - i)) % MOD
        for k in range(S - 1, x - 1, -1):
            dp[k] = (dp[k] + dp[k - x]) % MOD

    print(ret)


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

n = int(input())
a = list(map(int, input().split()))
ans = 1
lis = [0] * (n+1)


for i in range(n):
    if a[i] == 0:
        lis[i+1] += 1
    lis[i+1] += lis[i]
#print(lis)
for i in range(n):
    ans *= a[i]
    if lis[-1]-lis[i+1] == 0:
        if ans > int(1e18):
            print(-1)
            exit()
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
lis = [0] * (n+1)


for i in range(n):
    if a[i] == 0:
        lis[i+1] += 1
    lis[i+1] += lis[i]
#print(lis)
if lis[-1] > 0:
    print(0)
    exit()
for i in range(n):
    ans *= a[i]
    if lis[-1]-lis[i+1] == 0:
        if ans > int(1e18):
            print(-1)
            exit()
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

for i in range(1,N+1):
    for j in range(N-1):
        a,b = sorted([i,A[i-1][j]])

        A[i-1][j] = a*(N-1)+b-N-1

E=[set() for i in range(N*N)]
EREV=[set() for i in range(N*N)]

for i in range(N):
    for j in range(1,N-1):
        E[A[i][j-1]].add(A[i][j])
        EREV[A[i][j]].add(A[i][j-1])

from collections import deque
Q=deque()

H=[0]*N*N

for i in range(N*N):
    if E[i]==set() and len(EREV[i])>0:
        Q.append(i)
        H[i]=1

while Q:
    x=Q.pop()

    for fr in EREV[x]:
        H[fr]=max(H[x]+1,H[fr])
        if H[fr]>N*N:
            print(-1)
            sys.exit()
        Q.append(fr)
        

if max(H)==0:
    print(-1)
else:
    print(max(H))


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

for i in range(1,N+1):
    for j in range(N-1):
        a,b = sorted([i,A[i-1][j]])

        A[i-1][j] = a*(N-1)+b-N-1

E=[[] for i in range(N*N)]
EREV=[[] for i in range(N*N)]

EDGEIN=[0]*(N*N)

for i in range(N):
    for j in range(1,N-1):
        E[A[i][j-1]].append(A[i][j])
        EREV[A[i][j]].append(A[i][j-1])
        EDGEIN[A[i][j]]+=1

from collections import deque
Q=deque()

for i in range((N-1)**2):
    if EDGEIN[i]==0 and len(E[i])>0:
        Q.append(i)

TOP=[]
while Q:
    x=Q.pop()
    TOP.append(x)
    for to in E[x]:
        EDGEIN[to]-=1
        if EDGEIN[to]==0:
            Q.append(to)


H=[1]*(N**2)
for x in TOP[::-1]:

    for fr in EREV[x]:
            
        if H[fr]<H[x]+1:
            H[fr]=H[x]+1

if min(EDGEIN)<0 or max(EDGEIN)>0:
    print(-1)
else:
    print(max(H))
### BUGGY CODE ###

#
# P.48 O(n^2)となる単純な回答（比較用）
#
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_D
#
import sys

values = [int(input()) for i in range(int(input()))]

maxv = - sys.maxsize - 1

for c, i in enumerate(values):
    for j in values[c + 1:]:
        maxv = max(maxv, j - i)

print(maxv)



### FIXED CODE ###

values = [int(input()) for _ in range(int(input()))]
maxv = values[1] - values[0]
minv = values[0]

for val in values[1:]:
    maxv = max(maxv, val - minv)
    minv = min(minv, val)         # 今までの最小値を保持(自分と自分を比較しない様に、最大値の評価後に計算)
print(maxv)
### BUGGY CODE ###

n = int(input())
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return len(lower_divisors + upper_divisors[::-1])
cnt = 0
for m in range(1,n+1):
  cnt += m*make_divisors(m)
print(cnt)

### FIXED CODE ###

N = int(input())

ans = 0
for x in range(1, N + 1):
    n = N // x
    ans += n * (2 * x + (n - 1) * x) // 2

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

import sys
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

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

n=int(input())
a=list(map(int, input().split()))
#print(sorted(a))
a.sort()
wa=[a[0]]
bl=[]

def ok(wa,item,bl):
    for j in range(len(wa)):
        if item%wa[j]==0:
            if item==wa[j]:
                bl.append(item)
                return
            else:
                return
    wa.append(item)
    #print(item,wa,bl)
    return

for item in a[1:]:
    ok(wa,item,bl)

print(max(0,len(wa)-len(set(bl))))

"""
def ok(wa,item,bl):
    for j in range(len(wa)):
        if item%wa[j]==0:
            if item==wa[j]:
                bl.append(item)
                return
            else:
                return
    wa.append(item)
    print(item,wa,bl)
    return

for item in a[1:]:
    ok(wa,item,bl)
"""

### FIXED CODE ###

import sys
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''
def cal(n,li):
    lis=[True]*(n+1)
    for item in li:
        if lis[item]:
            for i in range(item*2,n+1,item):
                lis[i]=False
    return lis
from collections import Counter

n=int(input())
a=list(map(int,input().split()))
a.sort()
l=cal(a[-1],a)
ll=Counter(a)
#print(l,ll)
ans=0
for i in range(n):
    if ll[a[i]]==1:
        if l[a[i]]:
            ans+=1

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

n,m = list(map(int,input().split()))
a = []
b = []
for i in range(n):
    x,y = list(map(int,input().split()))
    a.append(x)
    b.append(y)
count = 0

while True:
    mi = min(a)

    if m - b[a.index(min(a))] > 0 : # Bi本買う
        m = m-b[a.index(min(a))]
        count += b[a.index(min(a))] * min(a)
        
    elif m - b[a.index(min(a))] == 0:
        count += m * min(a)
        
        break
    else:
        count += m * min(a)
        break
    d = a.index(min(a))
    del a[d]
    del b[d]

print(count)




### FIXED CODE ###

n,m = list(map(int,input().split()))
a = []
b = []
dic = {}
count = 0
data = [0] * n
for i in range(n):
    x,y = list(map(int,input().split()))
    data[i] = [x,y]
data = sorted(data,key = lambda x : x[0])
for i in range(n):
    if m > data[i][1]:
        count += data[i][0] * data[i][1]
        m -= data[i][1]
    else:
        count += data[i][0] * m
        break
print(count)

"""
for i in range(n):
    x,y = list(map(int,input().split()))
    dic[x] = y
dic = sorted(dic.items())



for key in dic:
    if m - dic[key] > 0:
        count += key * dic[key]
        m = m - dic[key]
    else:
        count += m * key
        break
print(count)
"""
            

"""

for i in range(n):
    x,y = list(map(int,input().split()))
    a.append(x)
    b.append(y)
count = 0


while m > 0:
    mi = min(a)
    d = a.index(mi)
    if m > b[d]  : # Bi本買う
        m -= b[d]
        count += b[d] * mi
    else:
        count += m * mi
        break
    del a[d]
    del b[d]
print(count)



"""
### BUGGY CODE ###

n = int(input())

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

a = 1
for i in range(n):
    a = a * s[i]


if a > 1000000000000000000:
    print('-1')
else:
    print(a)


### FIXED CODE ###

n = int(input())

s =list(map(int, input().split()))
s.sort()
a = 1
for i in range(n):
    a = a * s[i]
    if a > 1000000000000000000:
        print('-1')
        exit()
    else:
        if a == 0:
            print('0')
            exit()

print(a)
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
P = list(map(int, input().split()))
K = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    K[x].append(y)
    K[y].append(x)
used = [0]*N
OK = [0]*N
Origin = []
for i in range(N):
    P[i] -= 1
    if i == P[i]:
        OK[i] = 1
        Origin.append(i)
ans = 0
for i in range(N):
    c = 0
    if used[i] == 0:
        used[i] = 1
        S = deque([i])
        Enable = Origin.copy()
        Enable.append(i)
        T = OK.copy()
        T[P[i]] = 1
        while S:
            t = S.popleft()
            for j in K[t]:
                if used[j] == 0:
                    used[j] = 1
                    Enable.append(j)
                    T[P[j]] = 1
                    S.append(j)
    Enable = list(set(Enable))
    for j in Enable:
        if T[j] == 1:
            c += 1
    ans = max(ans, c)

print(ans)

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
P = list(map(int, input().split()))
K = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    K[x].append(y)
    K[y].append(x)
used = [0]*N
OK = []
for i in range(N):
    P[i] -= 1
    if i == P[i]:
        OK.append(i)
ans = 0
for i in range(N):
    if used[i] == 0:
        used[i] = 1
        S = deque([i])
        Enable = [i]
        Origin = [P[i]]
        while S:
            t = S.popleft()
            for j in K[t]:
                if used[j] == 0:
                    used[j] = 1
                    Enable.append(j)
                    Origin.append(P[j])
                    S.append(j)
        T_1 = list(set(OK + Enable))
        T_2 = list(set(OK + Origin))
        ans = max(ans, len(T_1) + len(T_2) - len(set(T_1 + T_2)))

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

N= int(input())

# まず二分探索の始点・終点を調べる
print(0)
l_s = input()
if l_s == 'vacant': exit()

print(N-1)
r_s = input()
if r_s == 'vacant': exit()

# 二分探索する
l = 0
r = N-1

while r - l > 1:
  c = (l + r) // 2
  print(c)
  s = input()
  if s == 'vacant':
    exit()
  elif ((l-c) % 2 == 1) ^ (seat[l] == seat[c]):
    r = c-1
  elif ((r-c) % 2 == 1) ^ (seat[r] == seat[c]):
    l = c+1
    
# loopを抜ける可能性あり
print(l)
s = input()
if s == 'vacant': exit()

### FIXED CODE ###

N= int(input())

# queryを投げて空の時の処理をする関数
def query1(i):
  print(i)
  tmp = input()
  if tmp[0] == 'V':
    exit()
  return tmp

# 最初に始点を探索
z = query1(0)
  
# 矛盾していないか判定する関数, Falseなら矛盾
def judge1(m):
  s = query1(m)
  if m % 2 == 0: # 偶数なら0番目と同じなら矛盾しない
    return z==s
  else:
    return z!=s
  
# 二分探索する
l = 0
r = N # N-1にするとN-1が探索されずにwhileを抜けてしまう
while r - l > 1:
  m = (l + r) // 2
  if judge1(m):
    # l~mまでが矛盾しない
    l = m
  else:
    r = m
### BUGGY CODE ###

h,w=map(int,input().split())
S=[["#"]+list(input())+["#"] for _ in range(h)]
S.insert(0,["#"]*(w+2))
S.append(["#"]*(w+2))

C=[[[0]*4 for _ in range(w+2)] for _ in range(h+2)]
for n,flag in enumerate((1,-1)):
    for i in range(1,h+1):
        for j in range(1,w+1)[::flag]:
            if S[i][j]!="#":C[i][j][n] +=C[i][j-flag][n]+1
for n,flag in enumerate((1,-1)):
    for i in range(1,w+1):
        for j in range(1,h+1)[::flag]:
            if S[j][i]!="#":C[j][i][n+2] +=C[j-flag][i][n+2]+1

print(max([sum(C[i][j])-3 for i in range(1,h+1) for j in range(1,w+1)]))

### FIXED CODE ###

import numpy as np
h,w=map(int,input().split())
S=np.array([list(input()) for _ in range(h)])
S=np.where(S==".",1,0)

left,right,up,down=[np.zeros((h,w),dtype=np.int64) for _ in range(4)]
for i in range(w):
    left[:,i]=(left[:,i-1]+1)*S[:,i]
    right[:,-i-1]=(right[:,-i]+1)*S[:,-i-1]
for i in range(h):
    up[i]=(up[i-1]+1)*S[i]
    down[-i-1]=(down[-i]+1)*S[-i-1]

print(int(np.max(left+right+up+down)-3))