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

from collections import deque


H, W = map(int, input().split())
m = [[0 if c == '#' else 3000 for c in input()] for _ in range(H)]
queue = deque()
for i, r in enumerate(m):
    for j, n in enumerate(r):
        if n == 0:
            queue.append((i, j))
while queue:
    p, q = queue.popleft()
    if 0 < p and m[p - 1][q] > m[p][q] + 1:
        m[p - 1][q] = m[p][q] + 1
        queue.append((p - 1, q))
    if 0 < q and m[p][q - 1] > m[p][q] + 1:
        m[p][q - 1] = m[p][q] + 1
        queue.append((p, q - 1))
    if p < H - 1 and m[p + 1][q] > m[p][q] + 1:
        m[p + 1][q] = m[p][q] + 1
        queue.append((p + 1, q))
    if q < W - 1 and m[p][q + 1] > m[p][q] + 1:
        m[p][q + 1] = m[p][q] + 1
        queue.append((p, q + 1))
_max = 0
for r in m:
    _max = max(_max, max(r))
print(_max)


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
m = [[0 if c == '#' else 3000 for c in input()] for _ in range(H)]
queue = deque()
for i, r in enumerate(m):
    for j, n in enumerate(r):
        if n == 0:
            queue.append((i, j))
while queue:
    p, q = queue.popleft()
    if 0 < p and m[p - 1][q] > m[p][q] + 1:
        m[p - 1][q] = m[p][q] + 1
        queue.append((p - 1, q))
    if 0 < q and m[p][q - 1] > m[p][q] + 1:
        m[p][q - 1] = m[p][q] + 1
        queue.append((p, q - 1))
    if p < H - 1 and m[p + 1][q] > m[p][q] + 1:
        m[p + 1][q] = m[p][q] + 1
        queue.append((p + 1, q))
    if q < W - 1 and m[p][q + 1] > m[p][q] + 1:
        m[p][q + 1] = m[p][q] + 1
        queue.append((p, q + 1))
_max = 0
for r in m:
    _max = max(_max, max(r))
print(_max)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())

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

    # check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
    check = [0] * N #i番目の次の相手のindex

    ans = 1
    i = 0
    tmp = 0
    count = 0
    flag  = [True] * N #試合をしたかどうかチェック
    while tmp < 2 * N + 2:
        if i == N:
            ans += 1
            flag  = [True] * N #試合をしたかどうかチェック
            i = 0
            
        if check[i] >= N - 1 or flag[i] == False:
            i += 1
            tmp += 1
            continue
        b = A[i][check[i]] - 1
        # print (b)
        if A[b][check[b]] - 1 == i and flag[b]: #試合できる時
            check[i] += 1
            check[b] += 1
            flag[i] = False
            flag[b] = False
            tmp = 0
            count += 1
            if count == (N * (N - 1))//2:
                print (ans)
                exit()
        i += 1
        tmp += 1
    print (-1)
    return 
            
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
B = {i: row for i, row in enumerate(A)}

# print (A)
# print (B)

end = 0

for k in range(8000):
    used = set()
    dels = []
    for i, q in B.items():
        if not q:
            continue
        if i in used:
            continue
        j = q[-1]
        if j in used:
            continue
        if A[j][-1] == i:
            A[j].pop()
            A[i].pop()
            used.add(i)
            used.add(j)
            if not A[i]:
                end += 1
                dels.append(i)
            if not A[j]:
                end += 1
                dels.append(j)
    if not used:
        print (-1)
        exit()
    
    if end == N:
        print (k + 1)
        exit()
    
    for i in dels:
        del B[i]
        
print (N * (N - 1) // 2)
### BUGGY CODE ###

N = int(input())
S = input()

con = 0

for n in range(0,1000):
  c = str(n)
  c = "0" * (3 - len(c)) + c
  for i in range(len(S) - 2):
    if S[i] == c[0]:
      for j in range(i + 1,len(S) - 1):
        if S[j] == c[1] and c[2] in S[j + 1:]:
          con += 1
          break
      break

print(con)

### FIXED CODE ###

N = int(input())
S = input()
con = 0

for i in range(10):
  if str(i) in S:
    p = S.index(str(i))
    S2 = S[p + 1:]
    for j in range(10):
      if str(j) in S2:
        q = S2.index(str(j))
        S3 = S2[q + 1:]
        for k in range(10):
          if str(k) in S3:
            con += 1

print(con)
### BUGGY CODE ###

import heapq
h,w = map(int,input().split())
si,sj = map(int,input().split())
gi,gj = map(int,input().split())
si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
grid = []
for _ in range(h):
    grid.append(input())
dist = {(i,j):float("inf") for i in range(h) for j in range(w)}
dist[si,sj] = 0
heap = [(0,si,sj)]
while heap:
    mindist,i,j = heapq.heappop(heap)
    if (i,j) == (gi,gj):
        print(mindist)
        break
    if mindist > dist[i,j]: continue
    for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
        if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
            if dist[ni,nj] > dist[i,j]:
                dist[ni,nj] = dist[i,j]
                heapq.heappush(heap,(dist[ni,nj],ni,nj))
    for ni in range(i-2,i+3):
        if not (0 <= ni and ni < h): continue
        for nj in range(j-2,j+3):
            if not (0 <= nj and nj < w): continue
            if (ni,nj) not in [(i,j),(i+1,j),(i-1,j),(i,j+1),(i,j-1)] and grid[ni][nj] == ".":
                if dist[ni,nj] > dist[i,j] + 1:
                    dist[ni,nj] = dist[i,j] + 1
                    heapq.heappush(heap,(dist[ni,nj],ni,nj))

else:
    print(-1)

### FIXED CODE ###

from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
def main():
    s = input()[:-1]
    q = int(input())
    tmp = [input().split() for _ in range(q)]
 
    for i in range(len(tmp)):
        if len(tmp[i]) == 1:
            s = s[::-1]
        else:
            if int(tmp[i][1]) == 1:
                s = ''.join([tmp[i][2], s])
            else:
                s = ''.join([s, tmp[i][2]])
                
    print(s)
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque

def main():
    input = sys.stdin.readline

    s = input()[:-1]
    q = int(input())
    tmp = [input().split() for _ in range(q)]

    flag = 0
    ans = deque([s])
    for t in tmp:
        if len(t) == 1:
            flag = ~flag 
        else:
            f = int(t[1])
            c = t[2]
            if (f == 1 and flag == 0) or (f ==2 and flag == -1):
                ans.appendleft(c)
            else:
                ans.append(c)
    if flag == 0:
        print(''.join(ans))
    else:
        print(''.join(ans)[::-1])

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

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

def cf(x1,x2):
    cf=[]
    for i in range(1,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            if i%2==0 and i!=2:
                    continue
            cf.append(i)
    return cf

def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

L=cf(a,b)
L2=[]
for i in L:
     if is_prime(i):
           L2.append(i)

print(len(L2)+1)

### FIXED CODE ###

import fractions

a,b=map(int,input().split())
g=fractions.gcd(a,b)
#print(g)
ans=1
i=2
while i*i<=g:
    if(g%i==0):
        ans+=1
        while g%i==0:
            g/=i
    i=i+1
if(g!=1):ans+=1
print(ans)
### BUGGY CODE ###

import math

def prime(m):
    pf = {}
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:pf[m]=1
    return pf

def calc_tmpans(primes, tmpans, cnt, val):
    if len(primes) == 0:
        tmpans[val] = cnt
    else:
        (p, v) = primes[0]
        for i in range(v + 1):
            calc_tmpans(primes[1:], tmpans, cnt * (i + 1), val * (p ** i) )

def main():
    N = int(input())

    tmpans = [0]*(N+1)
    ans = 0
    for c in range(1, N):
        if tmpans[N - c] != 0:
            ans += tmpans[N-c]
        else:
            p = prime(N - c)
            tmp = 1
            p_list = list(p.items())
            # for (k, v) in p_list:
            #     tmp *= (v + 1)
            calc_tmpans(p_list, tmpans, 1, 1)
            ans += tmp
    return sum(tmpans)

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data
 
p_list = get_sieve_of_eratosthenes(10**3)
 
def factorization_counta(n):
    arr = []
    temp = n
    for i in p_list:
        if i * i > n:
            break
        elif temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append(cnt)
            
    if temp != 1:
        arr.append(1)
    if arr == []:
        arr.append(1)
    return arr

def main():
    N = int(input())
    ans = 1
    for c in range(2, N):
        p = factorization_counta(c)
        tmp = 1
        for v in p:
            tmp *= (v + 1)
        ans += tmp
    return ans
 
if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

import sys

input = sys.stdin.readline
R, C, K = map(int, input().split())
values = [[0]*C for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    values[r-1][c-1] = v

dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]

for r in range(R-1, -1, -1):
    for c in range(C-1, -1, -1):
        v = values[r][c]
        for i in range(4):
            if i == 0 or v == 0:
                dp[r][c][i] = max(dp[r+1][c][3], dp[r][c+1][i])
            else:
                dp[r][c][i] = max(dp[r + 1][c][3]+v, dp[r][c + 1][i], dp[r][c + 1][i-1] + v)

print(dp[0][0][3])


### FIXED CODE ###

import sys

input = sys.stdin.readline
R, C, K = map(int, input().split())
values = [[0]*C for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    values[r-1][c-1] = v

dp = [[[0 for _ in range(C+1)] for _ in range(R+1)] for _ in range(4)]

for r in range(R-1, -1, -1):
    # dp[0][r][C - 1] = dp[3][r + 1][C - 1]
    # for i in range(1, 4):
    #    dp[i][r][C-1] = dp[3][r + 1][C-1][3]+values[r][C-1]
    for c in range(C-1, -1, -1):
        v = values[r][c]
        for i in range(4):
            if i == 0 or v == 0:
                dp[i][r][c] = max(dp[3][r+1][c], dp[i][r][c+1])
            else:
                dp[i][r][c] = max(dp[3][r + 1][c]+v, dp[i][r][c + 1], dp[i-1][r][c + 1] + v)

print(dp[3][0][0])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1
    j = 0
    A[0] = len_s = len(S)
    while i < len_s:
        while i+j < len_s and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while len_s-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A


def solve(N: int, S: str):
    ans = 0
    for i in range(N-1):
        ans = max(z_algo(S[i:])[(N-i+1)//2:] + [ans])
    print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def z_algo(N, S):
    end = 1
    start = 0
    max_length = 0

    while start < N:
        while end-start > N-end:
            break
        subword = S[start:end]
        if subword in S[end:]:
            max_length = max(max_length, len(subword))
            end += 1
        else:
            start += 1
            if start == end:
                end += 1
    return max_length


def solve(N: int, S: str):
    print(z_algo(N, S))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)


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

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

dp = [10**10] * n
dp[0] = 0

for i in range(n):
    for j in range(1, k + 1):
        if i + j < n:
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
print(dp[n - 1])

### FIXED CODE ###

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

dp = [10**9] * n
dp[0] = 0

for i in range(n):
    for j in range(1, k + 1):
        if i + j < n:
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
        else:
            break
print(dp[n - 1])
### BUGGY CODE ###

def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        ans = 1
        cnt = 0
        while p % 2 == 0:
            p //= 2
            cnt += 1
        if cnt >= n:
            ans *= 2**(cnt//n)
        cnt = 0
        while p % 3 == 0:
            p //= 3
            cnt += 1
        if cnt >= n:
            ans *= 3**(cnt//n)
        cnt = 0
        while p % 5 == 0:
            p //= 5
            cnt += 1
        if cnt >= n:
            ans *= 5**(cnt//n)
        x = 5
        while x**n <= p:
            x += 2
            if x % 3 == 0 or x % 5 == 0:
                continue
            cnt = 0
            while p % x == 0:
                p //= x
                cnt += 1
            if cnt >= n:
                ans *= x**(cnt//n)
        print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from math import log
def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        ans = 1
        if n > int(log(p, 2))+2:
            print("1")
            sys.exit()
        if p % (2**n) == 0:
            while p % (2**n) == 0:
                ans *= 2
                p //= (2**n)
        for i in range(3, 10**6+1, 2):
            while p % (i**n) == 0:
                ans *= i
                p //= (i**n)
        print(ans)

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

import sys
import heapq
import copy

n = int(input())
a = []

for _ in range(n):
	a.append(int(input()))

for i in range(n):
	b = copy.deepcopy(a)
	b.remove(a[i])
	b = [-1*tmp for tmp in b]
	heapq.heapify(b)
	print(heapq.heappop(b) * (-1))



### FIXED CODE ###

import sys
import heapq
import copy

n = int(input())
a = []

for _ in range(n):
	a.append(-1 * int(input()))

b = copy.deepcopy(a)
heapq.heapify(b)

for i in range(n):
	maximum = heapq.heappop(b)
	if maximum == a[i]:
		tmp = maximum
		maximum = heapq.heappop(b)
		print(maximum * (-1))
		heapq.heappush(b,tmp)
	else:
		print(maximum * (-1))
	heapq.heappush(b,maximum)
### BUGGY CODE ###

import sys
from collections import deque


def LS():
    return list(input().split())


S = deque(input())
Q = int(input())
rev = 0
for i in range(Q):
    A = LS()
    if A[0] == "1":
        rev += 1
        rev %= 2
    else:
        if A[1] == "1":
            if rev == 0:
                S.appendleft(A[2])
            else:
                S.append(A[2])
        else:
            if rev == 0:
                S.append(A[2])
            else:
                S.appendleft(A[2])
if rev == 0:
    for i in range(len(S)):
        print(S[i], end="")
else:
    for i in range(len(S)-1, -1, -1):
        print(S[i], end="")


### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
reverse = 0
Tlist = []
for i in range(Q):
    Tlist.append(list(input().split()))
    if Tlist[i][0] == str(2):
        if (int(Tlist[i][1])+reverse) % 2 == 0:
            S.append(Tlist[i][2])
        else:
            S.appendleft(Tlist[i][2])
    else:
        if reverse == 1:
            reverse = 0
        else:
            reverse = 1
if reverse == 0:
    print(''.join(S))
else:
    S.reverse()
    print(''.join(S))
### BUGGY CODE ###

import itertools

mod = 10**9 + 7
N = int(input())

A = [int(i)%mod for i in input().split()]

ans = 0
for i, j in itertools.combinations(A, 2):
    ans += (i*j)

print(ans%mod)

### FIXED CODE ###

N = int(input())

mod = 10**9 + 7

A = [int(i)%mod for i in input().split()]

S = [0]*N

ans = 0
for i in range(N-1):
    if i == 0:
        S[i] = sum(A) - A[i]
    else:
        S[i] = (S[i-1] - A[i])
    ans +=  (A[i]*S[i])%mod

print(ans%mod)
### BUGGY CODE ###

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

ans=0
while True:
  for i in l:
    if i%2!=0:
      break
  ans+=1
  l=[i/2 for i in l]
  
print(ans)

### FIXED CODE ###

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

ans=0
while True:
  for i in l:
    if i%2!=0:
      print(ans)
      exit()
  ans+=1
  l=[i/2 for i in l]
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    S = list(map(int, list(input())))
    S = S[::-1]
    n = len(S)
    mod = 2019
    A = [0] * n
    times = 1
    for i in range(n):
        A[i] = S[i] * times % mod
        times = times * 10

    # 累積和
    R = [0] * (n + 1)
    for i in range(n):
        R[i+1] = (R[i] + A[i]) % mod
    # print(R)
    cnt = {}
    ans = 0
    for i in range(n+1):
        r = R[i] % mod
        # print(r)
        ans = ans + cnt.get(r, 0)
        # cnt.setdefault(r, 0)
        # ans = ans + cnt[r]
        cnt[r] = cnt.get(r, 0) + 1
    # print(cnt)
    print(ans)

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())
 
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
 
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
 
INF = float('inf')
 
def solve():
    S = list(map(int, list(input())))
 
    S = S[::-1]
    # print(S)
    n = len(S)
    mod = 2019
 
    #
    A = [0] * (n)
    a = 1
    for i in range(n):
        A[i] = S[i] * a
        a = a * 10 % mod
    # print(A)
 
    # 累積和
    R = [0] * (n+1)
    for j in range(n):
        R[j+1] = (R[j] + A[j]) % mod
    # print(R)
 
    # 個数を数える
    cnt = {}
    ans = 0
    for l in range(0, n+1):
        r = R[l]
        ans = ans + cnt.get(r, 0)
        cnt[r] = cnt.setdefault(r, 0) + 1
    print(ans)
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

import numpy as np

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

max = 0
j = N-K+1
for i in range(j):
    tmp = np.sum(p[i:i+K])
    if tmp>max:
        max = tmp

print((max+K)/2)

### FIXED CODE ###

import numpy as np

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

tmp = np.sum(p[:K])
max = tmp
for i in range(N-K):
    tmp = tmp-p[i]+p[i+K]
    if tmp>max:
        max = tmp

print((max+K)/2)
### BUGGY CODE ###

import numpy as np
N = int(input())
X = []
ans = 0
for c in range(1, N):
  X.append(N - c)
arr_X = np.array(X)

for b in range(1, N):  
  ans += np.count_nonzero(arr_X % b == 0)
print(ans)


### FIXED CODE ###

N = int(input())
ans = 0
for a in range(1, N):
  ans += (N - 1) // a 
print(ans)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N, W = map(int, input().split())
    dp = [[0] * (W+1) for i in range(N+1)]
    #dp[i][j]  iまでをみてjの重さでの最大価値
    for i in range(1,N+1):
        w, v = map(int, input().split())
        for j in range(W+1):
            if j-w>=0:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
            else:
                dp[i][j] = dp[i-1][j]
#    print(dp)
    print(dp[N][W])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=np.int)
for n in range(1,N+1):
  wn, vn = map(int, input().split())
  dp[wn:]=np.maximum(dp[wn:], dp[:-wn]+vn)
print(dp[W])
### BUGGY CODE ###

def solve():
    H, W = map(int, input().split())
    maze = [[] for _ in range(H)]
    for i in range(H):
        maze[i] = list(input())

    u = [[0 for _ in range(W)] for _ in range(H)]
    r = [[0 for _ in range(W)] for _ in range(H)]
    d = [[0 for _ in range(W)] for _ in range(H)]
    l = [[0 for _ in range(W)] for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if maze[i][j] == '#':
                continue
            if i == 0:
                u[i][j] = 1
            else:
                u[i][j] = u[i-1][j] + 1
            if j == 0:
                l[i][j] = 1
            else:
                l[i][j] = l[i][j-1] + 1
    for i in range(H-1, -1, -1):
        for j in range(W-1, -1, -1):
            if maze[i][j] == '#':
                continue
            if i == H - 1:
                d[i][j] = 1
            else:
                d[i][j] = d[i+1][j] + 1
            if j == W - 1:
                r[i][j] = 1
            else:
                r[i][j] = r[i][j+1] + 1

    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, u[i][j] + r[i][j] + d[i][j] + l[i][j] - 3)
    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    H, W = map(int, input().split())
    maze = [[] for _ in range(H)]
    for i in range(H):
        maze[i] = list(input())

    u = [[0 for _ in range(W)] for _ in range(H)]
    r = [[0 for _ in range(W)] for _ in range(H)]
    d = [[0 for _ in range(W)] for _ in range(H)]
    l = [[0 for _ in range(W)] for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if maze[i][j] == '#':
                continue
            if i == 0:
                u[i][j] = 1
            else:
                u[i][j] = u[i-1][j] + 1
            if j == 0:
                l[i][j] = 1
            else:
                l[i][j] = l[i][j-1] + 1
    for i in range(H-1, -1, -1):
        for j in range(W-1, -1, -1):
            if maze[i][j] == '#':
                continue
            if i == H - 1:
                d[i][j] = 1
            else:
                d[i][j] = d[i+1][j] + 1
            if j == W - 1:
                r[i][j] = 1
            else:
                r[i][j] = r[i][j+1] + 1

    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, u[i][j] + r[i][j] + d[i][j] + l[i][j] - 3)
    print(ans)


if __name__ == '__main__':
    solve()