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

import sys
import copy

sys.setrecursionlimit(10**6)

m = [0,2,5,5,4,5,6,3,7,6]

def a_le_b(a, b):
    la, lb = len(a), len(b)
    if la == lb:
        for i in range(la):
            if a[i] < b[i]:
                return True
            elif a[i] > b[i]:
                return False
        return True
    return la < lb

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
for i in range(len(A)-1, 0, -1):
    for j in range(i-1, -1, -1):
        if m[A[i]] == m[A[j]]:
            del A[i]
            break
# print(A)
dp = [[] for _ in range(N+1)]

for i in range(N):
    if len(dp[i])==0 and i != 0: continue
    x = copy.copy(dp[i]) + [0]
    # print(x)
    for j in range(len(A)):
        ind = i + m[A[j]]
        if ind <= N:
            x[-1] = A[j]
            if a_le_b(dp[ind], x):
                dp[ind] = copy.copy(x)
# print(dp)
print(''.join(map(str, dp[-1])))


### FIXED CODE ###

import sys
import copy

sys.setrecursionlimit(10**6)

m = [0,2,5,5,4,5,6,3,7,6]

def a_le_b(a, b):
    la, lb = len(a), len(b)
    if la == lb:
        for i in range(la):
            if a[i] < b[i]:
                return True
            elif a[i] > b[i]:
                return False
        return True
    return la < lb

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
for i in range(len(A)-1, 0, -1):
    for j in range(i-1, -1, -1):
        if m[A[i]] == m[A[j]]:
            del A[i]
            break
# print(A)
dp = [[] for _ in range(N+1)]

for i in range(N):
    if len(dp[i])==0 and i != 0: continue
    x = copy.copy(dp[i]) + [0]
    # print(x)
    for j in range(len(A)):
        ind = i + m[A[j]]
        if ind <= N:
            x[-1] = A[j]
            if a_le_b(dp[ind], x):
                dp[ind] = copy.copy(x)
# print(dp)
print(''.join(map(str, dp[-1])))
### BUGGY CODE ###

ans =0
for i in range(1000000000000000000):
  ans += 1
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
ans =[k]
mod = n%k 
ans.append(mod)

ans.append(k - mod) 
print(min(ans))
### BUGGY CODE ###

N = int(input())
S = input()
c = 0
for i in range(N):
    for j in range(i, N):
        for k in range(j, N):
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k] and j - i != k - j:
                c += 1
print(c)


### FIXED CODE ###

N = int(input())
S = input()
a = S.count("R") * S.count("G") * S.count("B")
c = 0
for i in range(N):
    for j in range(i + 1, N):
        k = 2 * j - i
        if k >= N:
            continue
        if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            c += 1
print(a - c)
### BUGGY CODE ###

n,k = map(int,input().split())
x = []
y = []
for i in range(n):
	a,b = map(int,input().split())
	x.append(a)
	y.append(b)
ans = 10 ** 100
for j in range(n):
	for f in range(n):
		for h in range(n):
			for g in range(n):
				cou = 0
				for t in range(n):
					if x[j] <= x[t] <= x[f] and y[h] <= y[t] <= y[g]:
						cou += 1
				if cou >= k:
					ans = min(ans,abs(x[j] - x[f]) * abs(y[h] - y[g]))
print(ans)


### FIXED CODE ###

n,k = map(int,input().split())
x = []
y = []
xx = []
yy = []
for i in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
    xx.append(a)
    yy.append(b)
ans = 10 ** 40
x.sort()
y.sort()
for i in range(n):
    for j in range(i+1,n):
        for l in range(n):
            for h in range(l+1,n):
                lx = x[i]
                rx = x[j]
                uy = y[h]
                dy = y[l]
                cnt = 0
                for ii in range(n):
                    if lx <= xx[ii] <= rx and dy <= yy[ii] <= uy:
                        cnt += 1
                if cnt >= k:
                    if (rx-lx) * (uy-dy) != 0:
                        ans = min(ans,(rx-lx)*(uy-dy))
print(ans)
### BUGGY CODE ###

from collections import deque
n = int(input())
a = list(map(int,input().split()))
stack = deque()
stack.append([1000,0,0,200])
ans = []
while stack:
  money,kabu,i,temp = stack.pop()
  ans.append(money)
  if i<n:
    stack.append([money,kabu,i+1,temp])
    if a[i]<temp and a[i]<=money:
      kabu += money//a[i]
      money %= a[i]
    elif a[i]>temp and kabu>=1:
      money += a[i]*kabu
      kabu = 0
    stack.append([money,kabu,i+1,a[i]])
    ans.append(money)
print(max(ans))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
money = 1000
kabu = 0
for i in range(n-1):
  if kabu==0:
    if a[i]<=a[i+1]:
      kabu += money//a[i]
      money %= a[i]
  else:
    if a[i]>a[i+1]:
      money += kabu*a[i]
      kabu = 0
print(money+kabu*a[-1])
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]
b=[]
for i in range(n):
    if i%2==0:
        l=[a[i]]
        l.extend(b)
        b=l
        
    else:
        b.append(a[i])

if n%2==0:
    b.reverse()

for i in range(n):
    if i!=n-1:
        print(b[i],end=" ")
    else:
        print(b[i])




### FIXED CODE ###

from collections import deque
n=int(input())
a=[int(i) for i in input().split()]
b=deque()
for i in range(n):
    if i%2==0:
        b.appendleft(a[i])
        
    else:
        b.append(a[i])

if n%2==0:
    b.reverse()

for i in range(n):
    if i!=n-1:
        print(b[i],end=" ")
    else:
        print(b[i])
### BUGGY CODE ###

import fractions
A,B=map(int,input().split())
s=fractions.gcd(A,B)
t=s
l=set()
if s%2==0:
  l.add(2)
  while s%2==0:
    s//=2
i=3
while i<=t:
  if s%i==0:
    l.add(i)
    while s%i==0:
      s=s//i
  i+=2
print(len(l)+1)

### FIXED CODE ###

import fractions
a,b=map(int,input().split())
s=fractions.gcd(a,b)
cnt={1}
if s%2==0:
    cnt.add(2)
    while s%2==0:
      s//=2
for i in range(3,int(s**0.5)+1,2):
    if s%i==0:
        cnt.add(i)
        while s%i==0:
            s//=i
print(len(cnt)+(s>1))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from math import sqrt

def cross3(a, b, c):
    return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

# ps = [(x, y), ...]: ソートされた座標list
def convex_hull(ps):
    qs = []
    N = len(ps)
    for p in ps:
        # 一直線上で高々2点にする場合は ">=" にする
        while len(qs) > 1 and cross3(qs[-1], qs[-2], p) > 0:
            qs.pop()
        qs.append(p)
    t = len(qs)
    for i in range(N-2, -1, -1):
        p = ps[i]
        while len(qs) > t and cross3(qs[-1], qs[-2], p) > 0:
            qs.pop()
        qs.append(p)
    return qs

def dist(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])
def cross(a, b, c, d):
    return (b[0]-a[0])*(d[1]-c[1]) - (b[1]-a[1])*(d[0]-c[0])
def rotating_calipers(ps):
    qs = convex_hull(ps)
    n = len(qs)
    if n == 2:
        return dist(qs[0], qs[1])
    i = j = 0
    for k in range(n):
        if qs[k] < qs[i]: i = k
        if qs[j] < qs[k]: j = k
    res = 0
    si = i; sj = j
    while i != sj or j != si:
        res = max(res, dist(qs[i], qs[j]))
        if cross(qs[i], qs[i-n+1], qs[j], qs[j-n+1]) < 0:
            i = (i + 1) % n
        else:
            j = (j + 1) % n
    return res

def main():
    N = int(readline())
    m = map(int,read().split())
    XY = list(zip(m,m))

    XY.sort()

    ans = rotating_calipers(XY)
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    N = int(readline())
    m = map(int,read().split())
    XY = list(zip(m,m))

    ans = 0
    z = [x-y for (x, y) in XY]
    # print(z)
    z.sort()
    ans = z[-1] - z[0]
    z = [x+y for (x, y) in XY]
    # print(z)
    z.sort()
    ans = max(ans, z[-1] - z[0])

    print(ans)

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

from collections import defaultdict

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
c = [[]] * m
a, b = ab[0]
last = a
ad = [b]
for i in range(1, n):
    a, b = ab[i]
    if a == last:
        ad.append(b)
    else:
        if last <= m:
            c[last - 1] = ad
        ad = [b]
    last = a
if a <= m:
    c[a - 1] = ad
choice = defaultdict(int)
ans = 0
for i in range(m):
    for j in c[i]:
        choice[j] += 1
    if choice:
        use = max(choice)
        ans += use
        choice[use] -= 1
        if choice[use] <= 0:
            del choice[use]
print(ans)


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
c = [[]] * m
a, b = ab[0]
last = a
ad = [b]
for i in range(1, n):
    a, b = ab[i]
    if a == last:
        ad.append(b)
    else:
        if last <= m:
            c[last - 1] = ad
        ad = [b]
    last = a
if a <= m:
    c[a - 1] = ad
a = [3, 0, 2, 6]
choice = []
heapq.heapify(choice)
ans = 0
for i in range(m):
    for j in c[i]:
        heapq.heappush(choice, -j)
    if choice:
        ans -= heapq.heappop(choice)
print(ans)
### BUGGY CODE ###


from collections import deque
N, u, v = map(int, input().split())
u, v = u-1, v-1
AB = [list(map(int, input().split())) for a in range(N-1)]

G = [[0 for b in range(N)] for a in range(N)]
D = [[0 for b in range(N)] for a in range(N)]


for ab in AB:
  G[ab[0]-1][ab[1]-1] = 1
  G[ab[1]-1][ab[0]-1] = 1

def bfs(current, goal):
  if D[current][goal] > 0:
    return D[current][goal]
  q = deque([[current, 0]])
  memo = [0 for a in range(N)]
  while q:
    startcost = q.popleft()
    start = startcost[0]
    cost = startcost[1]
    if start == goal:
      D[current][goal] = cost
      D[goal][current] = cost
      return cost
    for i in range(N):
      if G[start][i] == 1 and memo[i] == 0:
        q.append([i, cost + 1])
        memo[i] = 1
  

distances = [0]
for i in range(N):
  aoki = bfs(i, v)
  takahashi = bfs(i, u)
  if aoki > takahashi:
    distances.append(aoki)

print(max(distances)-1)



### FIXED CODE ###

from collections import deque
N, u, v = map(int, input().split())
u, v = u-1, v-1
AB = [list(map(int, input().split())) for a in range(N-1)]

G = [[] for a in range(N)]

for ab in AB:
  G[ab[0]-1].append(ab[1]-1)
  G[ab[1]-1].append(ab[0]-1)

qA = deque([v])
qT = deque([u])
costsA = [0 for a in range(N)]
doneA = [0 for a in range(N)]
costsT = [0 for a in range(N)]
doneT = [0 for a in range(N)]

doneA[v] = 1
doneT[u] = 1

def bfs(q, costs, done):
  while q:
    start = q.popleft()
    for i in G[start]:
      if done[i] == 0:
        q.append(i)
        costs[i] = costs[start] + 1
        done[i] = 1

bfs(qA, costsA, doneA)
bfs(qT, costsT, doneT)

distances = [0]
for i in range(N):
  if costsA[i] > costsT[i]:
    distances.append(costsA[i])

print(max(distances)-1)
### BUGGY CODE ###

H, W = map(int, input().split())
m = ['X' + input() + 'X' for i in range(H)]
m.insert(0, 'X' * (W+2))
m.insert(H+1, 'X' * (W+2))

cnt = 0
while(True):
  flag = True
  mm = [['X' for i in range(W+2)] for j in range(H+2)]
  for i in range(1, 1+H):
    for j in range(1, 1+W):
      if m[i][j] == '.':
        if m[i+1][j] == '#' or m[i-1][j] == '#' or m[i][j+1] == '#' or m[i][j-1] == '#':
          mm[i][j] = '#'
        else:
          mm[i][j] = '.'
        if flag:
          flag = False
      elif m[i][j] == '#':
        mm[i][j] = '#'
  cnt += 1
  m = mm.copy()
  if flag:
    break

print(cnt-1)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())

m = [['X'] * (W+2)]
for i in range(H):
  row = [c for c in input()]
  row.insert(0, 'X')
  row.append('X')
  m.append(row)
m.append(['X'] * (W+2))

q = deque([deque([(i, j) for j in range(1, 1+W) for i in range(1, 1+H) if m[i][j] == '#'])])

cnt = 0
while(True):
  if not q:
    break
  tt = q.popleft()
  nn = deque([])
  for t in tt:
    # left, right, up, down
    for n in ((t[0]-1, t[1]), (t[0]+1, t[1]), (t[0], t[1]-1), (t[0], t[1]+1)):
      if m[n[0]][n[1]] == '.':
        nn.append(n)
        m[n[0]][n[1]] = '#'
  if nn:
    q.append(nn)
  cnt += 1

print(cnt-1)
### BUGGY CODE ###

N,M=[int(x) for x in input().rstrip().split()]
l=[]
for i in range(M):
    b=input().rstrip().split()
    l.append(b)
count=0
ans=0
for i in range(1,N+1):
    for x,y in l:
        if int(x)<=i and i<=int(y):
            count+=1
        else:
            break
        if count==M:
            ans+=1

    count=0
print(ans)







### FIXED CODE ###

N,M=[int(x) for x in input().rstrip().split()]
l=[]
r=[]
for i in range(M):
    b=input().rstrip().split()
    l.append(int(b[0]))
    r.append(int(b[1]))

L=max(l)
R=min(r)

if R<L:
    print(0)
else:

    print(R-L+1)
### BUGGY CODE ###

m = 10000
NIL = -1

def h1(key):
    return key % m

def h2(key):
    return 1 + (key % (m - 1))

def h(key, i):
    return (h1(key) + i * h2(key)) % m

def insert(t, key):
    i = 0
    while True:
        j = h(key, i)
        if t[j] == NIL:
            t[j] = key
            return j
        else:
            i += 1

def find(t, key):
    i = 0
    while True:
        j = h(key, i)
        if t[j] == key:
            return j
        elif t[j] == NIL or i >= m:
            return NIL
        else:
            i += 1

def convert(word):
    result = ""
    for i in word:
        if i == "A":
            result += "1"
        elif i == "T":
            result += "2"
        elif i == "G":
            result += "3"
        else:
            result += "4"
    return int(result)


t = [NIL]*m
n = int(input())
for i in range(n):
    com = input().split()
    key = convert(com[1])
    if com[0] == "insert":
        insert(t, key)
    else:
        if find(t, key) != NIL:
            print("yes")
        else:
            print("no")



### FIXED CODE ###

n = int(input())
d = set()

for i in range(n):
    com = input().split()
    if com[0] == "insert":
        d.add(com[1])
    else:
        print("yes" if com[1] in d else "no")
### BUGGY CODE ###

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

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

stc2 = sorted(stc)

ans = []

for i in range(n):
    ans2 = [list(ans[i]) for i in range(len(ans))]
    time = [stc2[i][0],0,0]
    for j in range(len(ans2)):
        if stc2[i][2] != ans2[j][1]:
            ans2[j][0]+=1
        if ans2[j][0]<time[0]:
            time[0] = ans2[j][0]
            time[1] = ans2[j][1]
            time[2] = j
        elif ans2[j][0]==time[0] and time[1]!=stc2[i][2]:
            time[0] = ans2[j][0]
            time[1] = ans2[j][1]
            time[2] = j
    if time[1] == 0:
        ans.append([0,0])
        time[2]=-1
    ans[time[2]][0]=stc2[i][1]
    ans[time[2]][1]=stc2[i][2]

print(len(ans))

### FIXED CODE ###



N,C = map(int, input().split())

channels =[[]for i in range(C)]

for i in range(N):
    s,t,c = map(int,input().split())
    channels[c-1].append([s,t])

merged_channels = [[]for i in range(C)]
for i in range(len(channels)):
    channels[i].sort()
    if len(channels[i])>0:
        merged_channels[i].append(channels[i][0])
        for j in range(1,len(channels[i])):
            if merged_channels[i][-1][1]==channels[i][j][0]:
                merged_channels[i][-1][1] = channels[i][j][1]
            else:
                merged_channels[i].append(channels[i][j])

tv = [0]*(10**5+1)
for i in range(len(merged_channels)):
    for s,t in merged_channels[i]:
        for k in range(s,t+1):
            tv[k]+=1

print(max(tv))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
k=0
b=[]
for i in range(0,n+1):
  k+=a[i]*pow(2,n-i)
  b.append(k)
if k>pow(2,n):
  print(-1)
else:
  current=0
  ans=0
  for i in range(0,n+1):
    current+=a[n-i]
    if i==n:
      ans+=1
    else:
      s=(pow(2,n)-b[n-i-1])//pow(2,i)
      if (s+1)*pow(2,i)<=pow(2,n)-b[n-i-1]:
        s+=1
      current=min(current,s)
      current=min(current,pow(2,n-i))
      ans+=current
  print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
k=0
N=sum(a)
failflag=0
node=1
min1=[]
min2=[]
for i in range(0,n+1):
  node=node*2-a[i]
  if i==0:
    node=1-a[0]
  node=min(node,N)
  min1.append(node+a[i])
  if node<0:
    failflag=1
if failflag==1:
  print(-1)
else:
  current=0
  for i in range(0,n+1):
    current+=a[n-i]
    min2.append(current)
  min2.reverse()
  ans=0
  for i in range(0,n+1):
    ans+=min(min1[i],min2[i])
  print(ans)
### BUGGY CODE ###

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

dp = [[0]* (w+1) for _ in range(n+1)]

for i in range(1, n+1):
    w_temp, v_temp = wv[i-1]
    for j in range(1,w+1):
        if(j >= w_temp):
            dp[i][j] = max(dp[i-1][j],
                            dp[i-1][j-w_temp] + v_temp)
        else:
            dp[i][j] = dp[i-1][j]

print(dp[n][w])

### FIXED CODE ###

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

dp = [[0]* (w+1) for _ in range(n+1)]

for i in range(1, n+1):
    w_temp, v_temp = wv[i-1]
    for j in range(1,w+1):
        if(j >= w_temp):
            dp[i][j] = max(dp[i-1][j],
                            dp[i-1][j-w_temp] + v_temp)
        else:
            dp[i][j] = dp[i-1][j]

print(dp[n][w])
### BUGGY CODE ###

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


c = 0
a = 0

t = [0]*(n+1)

temp = []


for i in range(m):
    s = input().split()
    if s[0] not in temp:
        if s[1] == 'AC':
            a += 1
            c += t[int(s[0])]
            temp += [s[0]]
        elif s[1] == 'WA':
            t[int(s[0])] += 1

# for i in range(m):
#     s = input().split()
#     if s[0] not in temp:
#         if s[1] == 'AC':
#             a += 1
#             c += t
#             t = 0
#             temp += [s[0]]
#         elif s[1] == 'WA':
#             t += 1

print(a, c)


### FIXED CODE ###

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

a = [0] * (n+1)
b = [0] * (n+1)

c = 0

for i in [0]*(m):

    s = input().split()

    if a[int(s[0])] == 0:
        if s[1] == "AC":
            a[int(s[0])] = 1
            c += b[int(s[0])]
        else:
            b[int(s[0])] += 1

print(sum(a), c)
### BUGGY CODE ###

n=int(input())
c = list(map(int, input().rstrip().split()))
a=0
b=10**9+7
for i in range(len(c)):
    for j in range(i+1,n):
        
        a=(a+(c[i]%b*c[j]%b)%b)%b
        
print(a)

### FIXED CODE ###

n=int(input())
c = list(map(int, input().rstrip().split()))
ans=0
b=10**9+7
sum1=0
for i in range(n):
    ans=(ans+c[i]*sum1)%b
    sum1=(sum1+c[i])%b

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

n=int(input())
comb=[]
ans=[]


for k in range(1, n+1):
    flag=False
    for x in range(1, 100):
        if 6*x**2 > k:
            break
        else:
            for y in range(x, 100):
                for z in range(y, 100):
                    if (x+y+z)**2 - x*y-y*z-z*x==k:
                        comb.append((x,y,z))
                        flag=True
                        break
    
    if flag:
        pass
    else:
        comb.append((0, 0, 0))


for s in range(n):
    if comb[s][0]==comb[s][1]==comb[s][2]==0:
        ans.append(0)
    elif comb[s][0]==comb[s][1]==comb[s][2]!=0:
        ans.append(1)
    elif comb[s][0]!=comb[s][1] and comb[s][1]!=comb[s][2] and comb[s][2]!=comb[s][0]:
        ans.append(6)
    else:
        ans.append(3)

for i in range(n):
    print(ans[i])

### FIXED CODE ###

n=int(input())
cnt=[0]*(n+1)

for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            tmp=x*x + y*y + z*z + x*y + y*z + z*x
            if tmp <=n:
                cnt[tmp]+=1


for i in range(1, n+1):
    print(cnt[i])
### BUGGY CODE ###

import collections

H, W = map(int, input().split(" "))
mp = []
for _ in range(H):
    mp.append(input().strip())


def bfs(sh, sw, mp):
    que = collections.deque()
    que.append((sh, sw, 0))
    dist = [[float('inf') for _ in range(W)] for _ in range(H)]

    while len(que) > 0:
        h, w, d = que.popleft()
        dist[h][w] = d
        for (dh, dw) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
                continue
            if mp[h + dh][w + dw] == '#' or dist[h + dh][w + dw] != float('inf'):
                continue
            que.append((h + dh, w + dw, d + 1))
    return dist


for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            tmp_dist = bfs(h, w, mp)
            sh = h; sw = w;
            break

for h in range(H):
    for w in range(W):
        if mp[h][w] == '.' and tmp_dist[h][w] >= tmp_dist[sh][sw]:
            sh = h
            sw = w

dist = bfs(sh, sw, mp)
ans = 1
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            ans = max(ans, dist[h][w])
print(ans)

### FIXED CODE ###

import collections

H, W = map(int, input().split(" "))
mp = []
for _ in range(H):
    mp.append(input().strip())


def bfs(sh, sw, mp):
    que = collections.deque()
    que.append((sh, sw))
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    dist[sh][sw] = 0

    while que:
        h, w = que.popleft()
        for (dh, dw) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
                continue
            if mp[h + dh][w + dw] == '.' and dist[h + dh][w + dw] == -1:
                dist[h + dh][w + dw] = dist[h][w] + 1
                que.append((h + dh, w + dw))

    ans = 0
    for row in dist:
        ans = max(ans, max(row))
    return ans


ans = 0
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            ans = max(ans, bfs(h, w, mp))
print(ans)
### BUGGY CODE ###

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1= []
dp2= []
dp3=[]
dp4=[]
for i in range(h):
    dp1.append([])
    dp2.append([])
    dp3.append([])
    dp4.append([])
    for j in range(w):
        dp1[i].append(-1)
        dp2[i].append(-1)
        dp3[i].append(-1)
        dp4[i].append(-1)






for i in range(w):
    for j in range(h):
        if s[j][i] == "#":
            dp3[j][i] = 0
        elif j == 0:
            dp3[j][i] = 1
        else:
            dp3[j][i] = 1 + dp3[j-1][i]

        if s[h-j-1][i] == "#":
            dp4[h-j-1][i] = 0
        elif h-j-1 == h-1:
            dp4[h-j-1][i] = 1
        else:
            dp4[h-j-1][i] = 1 + dp4[h-j][i]


a = 1
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]

        if s[i][w-j-1] == "#":
            dp2[i][w-j-1] = 0
        elif w-j-1 == w-1:
            dp2[i][w-j-1] = 1
        else:
            dp2[i][w-j-1] = 1 + dp2[i][w-j]
a = 1
for i in range(h):
    for j in range(w):
        a = max(a,dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3)


print(a)

### FIXED CODE ###

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1= []
dp2= [[-1 for i in range(w)] for j in range(h)]
dp3=[]
dp4=[[-1 for i in range(w)] for j in range(h)]


for i in range(h):
    dp1.append([])
    dp3.append([])
    for j in range(w):
        dp1[i].append(-1)
        dp3[i].append(-1)

        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]

        if s[i][w-j-1] == "#":
            dp2[i][w-j-1] = 0
        elif w-j-1 == w-1:
            dp2[i][w-j-1] = 1
        else:
            dp2[i][w-j-1] = 1 + dp2[i][w-j]

        if s[i][j] == "#":
            dp3[i][j] = 0
        elif i == 0:
            dp3[i][j] = 1
        else:
            dp3[i][j] = 1 + dp3[i-1][j]

        if s[h-i-1][j] == "#":
            dp4[h-i-1][j] = 0
        elif h-i-1 == h-1:
            dp4[h-i-1][j] = 1
        else:
            dp4[h-i-1][j] = 1 + dp4[h-i][j]



        

a = 1
for i in range(h):
    for j in range(w):
        a = max(a,dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3)


print(a)