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

from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    if d>cost[x][y]:
        continue
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d<cost[nx][ny]:
            cost[nx][ny]=d
            queue.appendleft([nx,ny,d])

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d+1<cost[nx][ny]:            
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])

if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)



### FIXED CODE ###

from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d<cost[nx][ny]:
            cost[nx][ny]=d
            queue.appendleft([nx,ny,d])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d+1<cost[nx][ny]:            
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)
### BUGGY CODE ###

n=int(input())
memo={}
for i in range(n):
  s=input()
  if s not in memo:
    memo[s]=1
  else:
    memo[s]+=1
max_k_list = [kv[0] for kv in memo.items() if kv[1] == max(memo.values())]
print('\n'.join(sorted(max_k_list)))

### FIXED CODE ###

n=int(input())
memo={}
for i in range(n):
  s=input()
  if s not in memo:
    memo[s]=1
  else:
    memo[s]+=1
    
a=[]
max_v = max(memo.values())
for k, v in memo.items():
  if v==max_v:
    a.append(k)
print('\n'.join(sorted(a)))
### BUGGY CODE ###

def main():
    N = int(input())
    GA, SA, BA = map(int, input().split())
    GB, SB, BB = map(int, input().split())

    def napsac(x, g1, s1, b1, g2, s2, b2):
        dp = [None for _ in range(x+1)]
        dp[0] = 0

        # def case(i, m1, m2):
        #     return 0 if i - m1 < 0 else dp[i-m1] + m2

        # for i in range(1,x+1):
        #     dp[i] = max(i, case(i, g1, g2), case(i, s1, s2), case(i, b1, b2))

        for i in range(1,x+1):
            dp[i] = max(i, 0 if i - g1 < 0 else dp[i-g1] + g2,
                        0 if i - s1 < 0 else dp[i-s1] + s2,
                        0 if i - b1 < 0 else dp[i-b1] + b2)
            
        return dp[-1]

    print(napsac(napsac(N, GA, SA, BA, GB, SB, BB), GB, SB, BB, GA, SA, BA))

if __name__ == "__main__":
    main()

### FIXED CODE ###

N = int(input())
GA, SA, BA = map(int, input().split())
GB, SB, BB = map(int, input().split())

def napsac(x, g1, s1, b1, g2, s2, b2):
    dp = [0 for _ in range(x+1)]
    dp[0] = 0

    def case(i, m1, m2):
        return 0 if i - m1 < 0 else dp[i-m1] + m2

    for i in range(1,x+1):
        dp[i] = max(i, case(i, g1, g2), case(i, s1, s2), case(i, b1, b2))

    return dp[-1]

print(napsac(napsac(N, GA, SA, BA, GB, SB, BB), GB, SB, BB, GA, SA, BA))
### BUGGY CODE ###

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

import itertools

n, k = map(int, input().split())
a = list(itertools.accumulate(list(map(int, input().split()))))
a = [0] + a
s = []
for i in range(n+1):
    for j in range(i,n+1):
        s.append(list(format(a[j]-a[i], '050b')))

ret = 0
sel = set(range(n*(n+1)//2))
for i in range(50):
    nxt = set([])
    for j in sel:
        if s[j][i] == '1':
            nxt.add(j)
    if len(nxt)>=k:
        sel = nxt
        ret += 2**(49-i)
print(ret)

### FIXED CODE ###

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

import itertools

n, k = map(int, input().split())
a = list(itertools.accumulate(list(map(int, input().split()))))
a = [0] + a
s = [None] * (n*(n+1)//2)
cnt = 0
for i in range(n+1):
    for j in range(i+1,n+1):
        s[cnt] = format(a[j]-a[i], '050b')
        cnt += 1

ret = 0
sel = set(range(n*(n+1)//2))
for i in range(50):
    nxt = set([])
    for j in sel:
        if s[j][i] == '1':
            nxt.add(j)
    if len(nxt)>=k:
        sel = nxt
        ret += 2**(49-i)
print(ret)
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1, N):
    ans += i
print(ans)

### FIXED CODE ###

N = int(input())
print(N * (N - 1) // 2)
### BUGGY CODE ###

n = input()
l = len(n)
key = [0]*2019
mod = 1
judge = 0
for i in range(l):
  judge += ((mod%2019)*int(n[l-i-1]))%2019
  judge %= 2019
  k = judge%2019
  key[k] += 1
  mod *= 10

ans = key[0]
for i in range(2019):
  if key[i] >= 2:
    ans += key[i]*(key[i]-1)//2
print(ans)

### FIXED CODE ###

n = input()
l = len(n)
key = [0]*2019
mod = 1
judge = 0
for i in range(l):
  judge += ((mod%2019)*int(n[l-i-1]))%2019
  judge %= 2019
  k = judge%2019
  key[k] += 1
  mod *= 10
  mod %= 2019

ans = key[0]
for i in range(2019):
  if key[i] >= 2:
    ans += key[i]*(key[i]-1)//2
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n = int(input())
s = [ input() for i in range(n)]
count = 0
x = [sorted(i) for i in s]
_x = sorted(x)

for i in range(n-1):
    tmp = _x[i]
    for j in range(i+1,n):
        if tmp == _x[j]:
            count += 1
        else:
            break

print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(raw_input())
d = {}
ans = 0
for i in range(n):
    si = ''.join(sorted(raw_input()))
    if si in d:
        ans += d[si]
        d[si] += 1
    else:
        d[si] = 1
print(ans)
### BUGGY CODE ###

import fractions

MOD = 1000000007

def lcm(x, y):
    return x * y // fractions.gcd(x, y)

N = int(input())
A = [int(x) for x in input().split()]
lc = 1
for i in A:
    lc = lcm(lc, i)
ans = 0
for i in A:
    ans = (ans + lc // i) % MOD
print(ans)

### FIXED CODE ###

import fractions

def lcm(x, y):
    return x * y // fractions.gcd(x, y)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    prev_lc = 1
    ans = 0
    for i in A:
        lc = lcm(prev_lc, i)
        ans = ans * (lc // prev_lc) + lc // i
        prev_lc = lc
    print(ans % 1000000007)

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

n,W = map(int,input().split())
table = [[0]*(W+1) for _ in range(n+1)]
for i in range(n):
  w,v = map(int,input().split())
  for k in range(W+1):
    if k < w:
      table[i+1][k] = table[i][k]
    else:
      table[i+1][k] = max(table[i][k],table[i][k-w]+v)

print(table[n][W])
  
  

### FIXED CODE ###

n,W = map(int,input().split())
table = [[0]*(W+1) for _ in range(n+1)]
for i in range(n):
  w,v = map(int,input().split())
  for k in range(W+1):
    if k < w:
      table[i+1][k] = table[i][k]
    else:
      table[i+1][k] = max(table[i][k],table[i][k-w]+v)

print(table[n][W])
### BUGGY CODE ###

H, N = map(int, input().split(' '))
magic = [[0 for _ in range(3)] for j in range(N)]
for i in range(N):
  temp_a, temp_b = map(int, input().split())
  magic[i][0] = temp_a
  magic[i][1] = temp_b

dp = [float('inf')] * (H + 1)
dp[0] = 0

for i in range(1, H + 1):
  for j in range(N):
    if i >= magic[j][0]:
      dp[i] = min(dp[i - magic[j][0]] + magic[j][1], dp[i])
    else:
      dp[i] = min(magic[j][1], dp[i])

print(dp[H])

### FIXED CODE ###

H, N = map(int, input().split(' '))
magic = [[0 for _ in range(3)] for j in range(N)]
for i in range(N):
  temp_a, temp_b = map(int, input().split())
  magic[i][0] = temp_a
  magic[i][1] = temp_b

dp = [float('inf')] * (H + 1)
dp[0] = 0

for i in range(1, H + 1):
  for j in range(N):
    if i >= magic[j][0]:
      dp[i] = min(dp[i - magic[j][0]] + magic[j][1], dp[i])
    else:
      dp[i] = min(magic[j][1], dp[i])

print(dp[H])
### BUGGY CODE ###

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

temp=0

for i in range(n):
    c=a.count(i)
    temp=temp+int(c*(c-1)/2)

for k in range(n):
    ch=a[k]
    c2=a.count(ch)
    if c2==0 or c2==1:
        print(temp)
    else:
        ans=temp-int(c2*(c2-1)/2)+int((c2-1)*(c2-2)/2)
        print(ans)


### FIXED CODE ###

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

temp=0

s=[0]*n

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

for i in range(n):
    c=s[i]
    temp=temp+int(c*(c-1)/2)

for k in range(n):
    ch=a[k]
    c2=s[ch-1]
    if c2==0 or c2==1:
        print(temp)
    else:
        ans=temp-int(c2*(c2-1)/2)+int((c2-1)*(c2-2)/2)
        print(ans)
### BUGGY CODE ###

import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    S = NI()
    
    dp = [[0 for _ in range(2010)] for _ in range(2010)]

    
    for k in range(1,2010):
        dp[0][k] = 1

    
    for i in range(1,2010):
        cnt = 0
        for j in range(0,2010):
            cnt += dp[i-1][j]
            dp[i][j] = cnt

    ans = 0
    for s in range(1,S//3+1):
        ans += dp[S-s*3][s]%MOD
        ans = ans%MOD
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    S = NI()
    
    dp = [[0 for _ in range(2010)] for _ in range(2010)]

    
    for k in range(1,2010):
        dp[0][k] = 1

    
    for i in range(1,2010):
        cnt = 0
        for j in range(0,2010):
            cnt += dp[i-1][j]
            dp[i][j] = cnt%MOD

    ans = 0
    for s in range(1,S//3+1):
        ans += dp[S-s*3][s]%MOD
        ans = ans%MOD
    print(ans)


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

import copy
s=[]
i=0
n=int(input())
while i!=n:
    s.append(int(input()))
    i+=1
maxx=max(s)
i=0
#print(s)
while i!=n:

    a=s[0]
    del s[0]
    if maxx==a:
        print(max(s))
        maxx=max(s)
    else:
        print(maxx)


    s.append(a)
    i+=1

### FIXED CODE ###

import copy
s=[]
i=0
n=int(input())
while i!=n:
    s.append(int(input()))
    i+=1
maxx=max(s)
g=s.count(maxx)
i=0
j=0

#print(g)
while i!=n:
    a = s[j]
    if maxx == a and g < 2:
        a=s[j]
        del s[j]
        print(max(s))
        s.append(a)
    else:
        print(maxx)
        j+=1

    i+=1
### BUGGY CODE ###

H,W = map(int,input().split())
masu = [list(input()) for _ in range(H)]
from collections import deque
def bfs():
    que = deque([])
    seen = [[0]*(W+2)] + [[0] + [float('inf')]*(W)+[0]  for _ in range(H)] +[[0]*(W+2)] 
    for w in range(W):
        for h in range(H):
            if masu[h][w] == '#':
                que.append((w,h))
                seen[h+1][w+1] =0
    while que:
        a,b = que.popleft()
        for x,y in [[0,1],[1,0],[0,-1],[-1,0]]:
            nx = a+x
            ny = b+y
            if seen[ny+1][nx+1] == float('inf') and masu[ny][nx] == '.':
                seen[ny+1][nx+1] = seen[b+1][a+1] +1
                que.append((nx,ny))
    ans = 0
    for i in range(H+2):
        for j in range(W+2):
            if seen[i][j] > ans:
                ans = seen[i][j]
    return ans
print(bfs())

### FIXED CODE ###

from collections import deque
 
def solve(h, w, a):
    used = [[True] * (w+2) for _ in range(h+2)]
    que = deque()
    for r in range(h):
        used[r+1][1:-1] = map(lambda _:_=="#", a[r])
        for c in range(w):
            if a[r][c] == "#":
                que.append((r+1, c+1, 0))
    neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
    while que:
        r, c, k = que.popleft()
        for dr, dc in neighbors:
            nr, nc = r+dr, c+dc
            if not used[nr][nc]:
                que.append((nr, nc, k+1))
                used[nr][nc] = True
    return k
 
h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(solve(h, w, a))
### BUGGY CODE ###

if __name__ == "__main__":
    a, b, x = map(int, input().split())
    counter = 0
    for i in range(a, b + 1):
        counter += int(i % x == 0)
    print(counter)

### FIXED CODE ###

if __name__ == "__main__":
    a, b, x = map(int, input().split())
    z = (b) // x
    z -= (a - 1) // x
    print(z)
### BUGGY CODE ###

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

ans = set()
for i in range(10):
    for j in range(10):
        for k in range(10):
            tmp = str(i) + str(j) + str(k)

            f = -1
            s = -1
            t = -1
            for x in range(N):
                X = S[x]
                if f == -1 and X == str(i):
                    f = x
                if s == -1 and f != -1 and f < x and X == str(j):
                    s = x
                if t == -1 and s != -1 and s < x and X == str(k):
                    t = x
            if f < s < t:
                ans.add(tmp)
print(len(ans))



### FIXED CODE ###

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

from bisect import *
from collections import defaultdict

res = defaultdict(list)

for i in range(len(S)):
    s = S[i]
    res[int(s)].append(i)

for i in range(10):
    res[i].append(10000000)
ans = set()
for i in range(10):
    for j in range(10):
        for k in range(10):
            if len(res[i]) > 1 and len(res[j]) > 1 and len(res[k]) > 1:
                tmp = str(i) + str(j) + str(k)
                # print(i, j, k)
                f = res[i][0]
                s_i = bisect_left(res[j], f + 1)
                if s_i != len(res[j]) - 1:
                    s = res[j][s_i]
                else:
                    continue
                t_i = bisect_left(res[k], s + 1)
                if t_i != len(res[k]) - 1:
                    t = res[k][t_i]
                else:
                    continue
                if f < s < 10000000 and s < t < 10000000:
                    ans.add(tmp)
print(len(ans))
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
ans = N
 
for i in range(N):
  for j in range(i):
    if P[i] > P[j]:
      ans -= 1
      break
    
print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
ans = 0
min_number = 2*10**5+1

for i in range(N):
  min_number = min(min_number, P[i])
  if min_number == P[i]:
    ans += 1
  
print(ans)
### BUGGY CODE ###

# @author 

import sys

class QFlowers:
    def solve(self):
        n = int(input())
        h = [int(_) for _ in input().split()]
        a = [int(_) for _ in input().split()]

        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = a[i - 1]
            for j in range(i):
                if h[i - 1] > h[j - 1]:
                    dp[i] = max(dp[i], dp[j] + a[i - 1])

        # print(dp)
        print(dp[-1])

solver = QFlowers()
input = sys.stdin.readline

solver.solve()


### FIXED CODE ###

# @author 

import sys

class QFlowers:
    def solve(self):
        n = int(input())
        h = [int(_) for _ in input().split()]
        a = [int(_) for _ in input().split()]

        # h = [(h[i], i) for i in range(n)]
        # h.sort()

        def update(i, x):
            while i < n + 1:
                if x > dp[i]:
                    dp[i] = x
                i += i & -i

        def get(i):
            mx = 0
            while i > 0:
                if dp[i] > mx:
                    mx = dp[i]
                i -= i & -i
            return mx

        dp = [0] * (n + 1)
        for i, he in enumerate(h):
            update(he, get(he - 1) + a[i])

        # print(dp)
        print(max(dp))

solver = QFlowers()
input = sys.stdin.readline

solver.solve()
### BUGGY CODE ###

S = input()

N = len(S)

cnt = 0
for i in range(N-3):
    for j in range(i+3,N):
        S_int = int(S[i:(j+1)])
        if S_int % 2019 == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

S = input()
 
N = len(S)

mod = 2019
d = [0 for i in range(2019)]
d[0] = 1
t = 1
rem = 0

for i in reversed(S):
    rem += int(i) * t
    rem %= mod
    t *= 10
    t %= mod
    d[rem] += 1

print(int(sum([i * (i-1) / 2 for i in d])))
### BUGGY CODE ###

import sys
from operator import itemgetter
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
def main():
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while(e[0] > d):
			if cont == True:
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			else:
				mini = min(kouho)
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			cont = True
			if q < Q-1:
				q = q + 1
				d = int(inputs())
			else:
				flag = True
				q = q + 1
				break
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
		
def sub():
	V = [list(map(int,inputs().split())) for p in [0]*N]
	M = [int(inputs()) for p in [0]*Q]
	V.sort(key = lambda x:(x[2],x[0],x[1]))
	for v in V:
		v[0] -= v[2]
		v[1] -= v[2] + 1
	for m in M:
		for n in range(N):
			if V[n][0] <=m and m <= V[n][1]:
				print(V[n][2])
				break
		else:
			print(-1)

#N200000
if Q>199998:
	sub()
else:
	main()

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

import sys
import numpy as np

def retmin(a, b):
    if a > b:
        return b
    return a

input = sys.stdin.readline

# N 足場の数、K カエルができる行動
n, k = map(int, input().split())

# H 各足場の高さ
h = list(map(int, input().split()))

# 初期化
# dp = np.full(100100, 1000000000)
dp = [999999999999 for i in range(100100)]
dp[0] = 0

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

### FIXED CODE ###

import sys
import numpy as np

input = sys.stdin.readline

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

h = np.array([int(x) for x in input().split()])

# 初期化
dp = np.zeros(n, dtype=int)

for i in range(1, n):
    start = max(0, i-k)
    dp[i] = min(dp[start:i] + np.abs(h[i] - h[start:i]))
print(dp[n-1])
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
b = 1

for i in range(N):
  b *= a[i]

if b>10**(18):
  print('-1')
else:
  print(b)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
b = 1

if 0 in a:
  print(0)
  exit()

for i in range(N):
  b *= a[i]
  if b>10**(18):
    print('-1')
    exit()

print(b)
### BUGGY CODE ###

def m():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    G = [[[-1, -1] for _ in range(W)] for _ in range(H)]
    for a in range(H):
        left = 0
        for b in range(W):
            if S[a][b] == '#':
                left = 0
            else:
                G[a][b][0] = left + 1
                left = G[a][b][0]
    for b in range(W):
        top = 0
        for a in range(H):
            if S[a][b] == '#':
                top = 0
            else:
                G[a][b][1] = top + 1
                top = G[a][b][1]

    for i in reversed(range(H)):
        right = 0
        for j in reversed(range(W)):
            if G[i][j][0] == -1:
                right = 0
            else:
                G[i][j][0] = max(G[i][j][0], right)
                right = G[i][j][0]

    for j in reversed(range(W)):
        bot = 0
        for i in reversed(range(H)):
            if G[i][j][1] == -1:
                bot = 0
            else:
                G[i][j][1] = max(G[i][j][1], bot)
                bot = G[i][j][1]
    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(sum(G[i][j]), ans)
    return ans-1


print(m())


### FIXED CODE ###

def m():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    Gx = [[-1 for _ in range(W)] for _ in range(H)]
    Gy = [[-1 for _ in range(W)] for _ in range(H)]

    for a in range(H):
        left = 0
        for b in range(W):
            if S[a][b] == '#':
                left = 0
            else:
                Gx[a][b] = left + 1
                left = Gx[a][b]
    for b in range(W):
        top = 0
        for a in range(H):
            if S[a][b] == '#':
                top = 0
            else:
                Gy[a][b] = top + 1
                top = Gy[a][b]

    for i in reversed(range(H)):
        right = 0
        for j in reversed(range(W)):
            if Gx[i][j] == -1:
                right = 0
            else:
                Gx[i][j] = max(Gx[i][j], right)
                right = Gx[i][j]

    for j in reversed(range(W)):
        bot = 0
        for i in reversed(range(H)):
            if Gy[i][j] == -1:
                bot = 0
            else:
                Gy[i][j] = max(Gy[i][j], bot)
                bot = Gy[i][j]
    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(Gx[i][j] + Gy[i][j], ans)
    return ans - 1


print(m())