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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

H, W = map(int, input().split())
A = [[int(i) for i in input().split()] for _ in range(H)]
B = [[int(i) for i in input().split()] for _ in range(H)]

pdp = [set() for _ in range(W)]
pdp[0] = set([0])
for y in range(H) :
    ndp = [set() for _ in range(W)]
    for x in range(W) :
        s = set([i + A[y][x] - B[y][x] for i in pdp[x]] + [i + B[y][x] - A[y][x] for i in pdp[x]])
        if y < H - 1 :
            for i in pdp[x] :
                ndp[x] |= s
        if x < W - 1 :
            for i in pdp[x] :
                pdp[x+1] |= s
    
    if y == H - 1 :
        ret = float('inf')
        for i in pdp[-1] :
            ret = min(ret, abs(i + A[H-1][W-1] - B[H-1][W-1]))
            ret = min(ret, abs(i + B[H-1][W-1] - A[H-1][W-1]))
        print(ret)
    pdp = ndp

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

H, W = map(int, input().split())
A = [[int(i) for i in input().split()] for _ in range(H)]
B = [[int(i) for i in input().split()] for _ in range(H)]
C = [[abs(A[y][x] - B[y][x]) for x in range(W)] for y in range(H)]

N = 13000
half = N // 2

dp = [[0] * W for _ in range(H)]
dp[0][0] = (1 << (half - C[0][0])) | (1 << (half + C[0][0]))

for y in range(H) :
    for x in range(W) :
        if y != 0 :
            dp[y][x] |= (dp[y-1][x] >> C[y][x]) | (dp[y-1][x] << C[y][x])
                    
        if x != 0 :
            dp[y][x] |= (dp[y][x-1] >> C[y][x]) | (dp[y][x-1] << C[y][x])

b = bin(dp[-1][-1])[2:][::-1]
ret = float('inf')
for k, v in enumerate(b) :
    if v == '1' :
        ret = min(ret, abs(k - half))
        
print(ret)
### BUGGY CODE ###

import bisect
def main():
  N=int(input())
  A=list(map(int,input().split()))
  B=list(map(int,input().split()))
  ans=[]
  for i in range(29):
    T=2**i
    B_=list(B)
    A_=list(A)
    t=0
    for j in range(N):
      B_[j]%=2*T
      A_[j]%=2*T
    B_.sort()
    for j in range(N):
      a=A_[j]
      p=bisect.bisect_left(B_,T-a)
      q=bisect.bisect_left(B_,2*T-a)
      r=bisect.bisect_left(B_,3*T-a)
      s=bisect.bisect_left(B_,4*T-a)
      t+=(q-p)+(s-r)
    ans.append(t%2)
  a=0
  for i in range(29):
    a+=2**i*ans[i]
  print(a)
if __name__=='__main__':
  main()


### FIXED CODE ###

def main():
  N=int(input())
  A=list(map(int,input().split()))
  B=list(map(int,input().split()))
  ans=[]
  for i in range(29):
    T=2**i
    B_=list(B)
    A_=list(A)
    t=0
    for j in range(N):
      B_[j]%=2*T
      A_[j]%=2*T
    A_.sort()
    B_.sort()
    p=q=r=0
    for a in A_[::-1]:
      while p<N and a+B_[p]<T:
        p+=1
      while q<N and a+B_[q]<2*T:
        q+=1
      while r<N and a+B_[r]<3*T:
        r+=1
      t+=(q-p)+(N-r)
    ans.append(t%2)
  a=0
  for i in range(29):
    a+=2**i*ans[i]
  print(a)
if __name__=='__main__':
  main()
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    ans = 1
    s, t = [], []
    for i in range(n):
        if a[i] < 0:
            t.append(a[i])
        else:
            s.append(a[i])

    S, T = len(s), len(t)
    ok = False

    if S > 0:
        if n == k:
            ok = (T % 2 == 0)
        else:
            ok = True
    else:
        ok = (k % 2 == 0)

    if not ok:
        a.sort(key=abs)
        for i in range(k):
            ans *= a[i]
    else:
        s.sort()
        t.sort(reverse=True)
        if k % 2 == 1:
            ans *= s.pop()
        p = []
        while len(s) >= 2:
            x = s.pop()
            x *= s.pop()
            p.append(x)
        while len(t) >= 2:
            x = t.pop()
            x *= t.pop()
            p.append(x)
        p.sort(reverse=True)
        for i in range(k//2):
            ans *= p[i]
    print(ans % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    ans = 1
    s, t = [], []
    for i in range(n):
        if a[i] < 0:
            t.append(a[i])
        else:
            s.append(a[i])
    # s, t = [i for i in a if i > 0], [j for j in a if j < 0]

    S, T = len(s), len(t)
    ok = False

    if S > 0:
        if n == k:
            ok = (T % 2 == 0)
        else:
            ok = True
    else:
        ok = (k % 2 == 0)

    if not ok:
        a.sort(key=abs)
        for i in range(k):
            ans *= a[i]
            ans %= mod
    else:
        s.sort()
        t.sort(reverse=True)
        if k % 2 == 1:
            ans *= s.pop()
            ans %= mod
        p = []
        while len(s) >= 2:
            x = s.pop()
            x *= s.pop()
            p.append(x)
        while len(t) >= 2:
            x = t.pop()
            x *= t.pop()
            p.append(x)
        p.sort(reverse=True)
        for i in range(k//2):
            ans *= p[i]
            ans %= mod
    print(ans % mod)


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

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

maxs = 0
for i, s1 in enumerate(S):
    if i + maxs > len(S):
        break
    matchs = S[i:i+maxs+1]
    for j in range(i+maxs+1, len(S)-maxs):
        # 以下でmatchしてたらここに戻りたい
        for k in range(j,len(S)-maxs):
            if i + maxs >= j:
                break
            checks = S[j:j+maxs+1]
            if matchs == checks:
                maxs = len(matchs)
                matchs = S[i:i+maxs+1]
print(maxs)

### FIXED CODE ###

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

i = j = 0
ans = 0
while j < N-1:
    if S[i:j] in S[j:]:
        ans = max(ans, j-i)
        j += 1
    else:
        i += 1
print(ans)
### BUGGY CODE ###

import math


H,N = map(int,input().split())
Damage = []
Cost = []


DP = [0] * (H+1)



for i in range(N):
    a,b = map(int,input().split())
    Damage.append(a)
    Cost.append(b)
    
#print(DP)


# DP[i] = best magic points to do i damage

for i in range(1,len(DP)):
    best = pow(10,9)
    for spell in range(N):
#        print(spell,i, Damage[spell], Cost[spell])
        best = min(best,DP[max(0,i-Damage[spell])]+Cost[spell])
    DP[i] = best




print (DP[H])



### FIXED CODE ###


     

import math



H,N = map(int,input().split())
Damage = []
Cost = []


DP = [0] + [pow(10,9)] * (H+1)



for i in range(N):
    a,b = map(int,input().split())
    Damage.append(a)
    Cost.append(b)
    
#print(DP)


# DP[i] = min magic points to do i damage

for i in range(1,len(DP)):
    for spell in range(N):
        DP[i] = min(DP[i],DP[max(0,i-Damage[spell])]+Cost[spell])




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

N = int(input())
A = [int(i) for i in input().split()]
mod = 10**9 + 7
bits = [0]*61

ans = 0
for i, a in enumerate(A):
    for b in range(60):
        if (a >> b) & 1:
            ans += (2**b)*(i-bits[b])
            bits[b] += 1
        else:
            ans += (2**b)*bits[b]
    ans %= mod
print(ans)


### FIXED CODE ###

import numpy as np

N = int(input())
mod = 10**9 + 7
A = np.array(input().split(), dtype=np.int64)
# print(A)

ans = 0
for i in range(60):
    b = np.count_nonzero(A >> i & 1)
    ans += 2**i*(b*(N-b))
    ans %= mod
    # c = np.count_nonzero(A >> i)
    # print(c)
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    s = input()
    ans = 0
    r, g, b = [], [], []
    for i in range(n):
        if s[i] == 'R':
            r.append(i)
        elif s[i] == 'G':
            g.append(i)
        else:
            b.append(i)
    for ri in r:
        for gi in g:
            for bi in b:
                rgb = sorted([ri, gi, bi])
                if rgb[2] - rgb[1] == rgb[1] - rgb[0]:
                    continue
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    s = input()
    r, g, b = [], [], []
    for i in range(n):
        t = s[i]
        if t == 'R':
            r.append(i)
        elif t == 'G':
            g.append(i)
        else:
            b.append(i)
    ans = len(r) * len(g) * len(b)

    for i in range(1, n // 2 + 1):
        for k in range(n):
            try:
                if {s[k], s[k + i], s[k + 2 * i]} == {'R', 'G', 'B'}:
                    ans -= 1
            except IndexError:
                break
    print(ans)


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

from collections import Counter
n = int(input())
ls = []
for _ in range(n):
    ls.append(input())
res = []
counter = Counter(ls).most_common(1)
check=counter[0][1]
for x in set(ls):
    if ls.count(x) == check:
        res.append(x)
r = sorted(res)
print("\n".join(r))

### FIXED CODE ###

from collections import Counter
n = int(input())
ls = []
for _ in range(n):
    ls.append(input())
res = []
counter = Counter(ls).most_common()
for x in counter:
    if x[1] == counter[0][1]:
        res.append(x[0])
print("\n".join(sorted(res)))
### BUGGY CODE ###

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

for i in range(n):
    for j in range(n):
        if i == students[j]:
            print(j+1,end=" ")
print()

### FIXED CODE ###

n = int(input())
students = list(map(lambda x: int(x)-1,input().split()))
arrived = [0]*n

for i in range(n):
    arrived[students[i]] = i

for i in range(n):
    print(arrived[i]+1,end=" ")
print()
### BUGGY CODE ###

import itertools
def my_index(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

H,W,M=map(int,input().split())
P=list()
P_X=[0]*(H+1)
P_Y=[0]*(W+1)
for _ in range(M):
    P.append(list(map(int,input().split())))
for m in range(M):
    P_X[P[m][0]]+=1
for m in range(M):
    P_Y[P[m][1]]+=1
Max_X=max(P_X)
Max_Y=max(P_Y)
max_X=my_index(P_X,Max_X)
max_Y=my_index(P_Y,Max_Y)
for i, j in itertools.product(max_X, max_Y):
    if [i,j] in P:
        a=1
    else:
        a=0
        break
if a==0:
    answer=Max_X+Max_Y
else:
     answer=Max_X+Max_Y-1
    
print(answer)

    


### FIXED CODE ###


def my_index(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

H,W,M=map(int,input().split())
P=list()
P_X=[0]*(H+1)
P_Y=[0]*(W+1)
for m  in range(M):
    P.append(list(map(int,input().split())))
    P_X[P[m][0]]+=1
    P_Y[P[m][1]]+=1
Max_X=max(P_X)
Max_Y=max(P_Y)
max_X=my_index(P_X,Max_X)
max_Y=my_index(P_Y,Max_Y)
m_count=0
for k in P:
    if  P_X[k[0]] == Max_X and P_Y[k [1]] == Max_Y:
        m_count += 1
if m_count==len(max_X)*len(max_Y):
    answer=Max_X+Max_Y-1
else:
     answer=Max_X+Max_Y
    
print(answer)
### BUGGY CODE ###

# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math 
# import collections
# import string
# ===================================
n, k = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]
ans = [None for _ in range(n)]
ans[0] = 0

for i in range(1, n):
	t = int(1e9)
	for j in range(1, k+1):
		if i-j >= 0: t = min(t, ans[i-j] + abs(q[i-j] - q[i]))

	ans[i] = t

print(ans[n-1])


### FIXED CODE ###

# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math 
# import collections
# import string
# ===================================
import numpy as np
n, k = [int(x) for x in input().split()]
q = np.array([int(x) for x in input().split()])
ans = np.zeros(n, dtype=int)

for i in range(1, n):
	start = max(0, i-k)
	ans[i] = min(ans[start:i] + np.abs(q[i] - q[start:i]))

print(ans[n-1])
### BUGGY CODE ###

a, b = map(int, input().split())
c = []
if a > b:
    a, b = b, a
while True:
    for i in range(a):
        x = i + 2
        if a%x == 0:
            if b%x == 0:
                c.append(x)
                a = a//x
                b = b//x
                break
    if i == a-1:
        break
s = 1
for j in c:
    s = s * j
print(s)



### FIXED CODE ###

a, b = map(int, input().split())
c = []
if a > b:
    a, b = b, a
if b%a == 0:
    print(a)
else:
    while True:
        for i in range(a):
            x = i + 2
            if a%x == 0:
                if b%x == 0:
                    c.append(x)
                    a = a//x
                    b = b//x
                    break
                elif b%(a//x) == 0:
                    c.append(a//x)
                    a = x
                    b = b//(a//x)
                    break
            if x > a**0.5:
                break
        if x > a**0.5:
            break
    s = 1
    for j in c:
        s = s * j
    print(s)
### BUGGY CODE ###

n, k, q = map(int, input().split())
As = [int(input()) for i in range(q)]
points = {i: k for i in range(n)}
for i in range(q):
    solver = As[i] - 1
    for j in range(n):
        if j == solver:
            continue
        else:
            points[j] -= 1
for i in range(n):
    if points[i] <= 0:
        print("No")
    else:
        print("Yes")





### FIXED CODE ###

n, k, q = map(int, input().split())
As = [int(input()) for i in range(q)]
points = {i: k for i in range(n)}
accepted = [0] * n

for i in range(q):
    accepted[As[i]-1] += 1

for i in range(n):

    if k - q + accepted[i] <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().rstrip().split()))
work=int()
testA=int()
testB=int()
testC=int()
work=sum(A)//N-N//2
test=list((sum(abs(A[i]-i-work+N//2-j) for i in range(N))) for j in range(N))
output=min(test)
print(output)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().rstrip().split()))
B=list(A[i]-i for i in range(N))
C=list(A[i]-i for i in range(N))
C.sort()
work=C[N//2]
testA=sum(abs(B[i]-work) for i in range(N))
testB=sum(abs(B[i]-work-1) for i in range(N))
testC=sum(abs(B[i]-work+1) for i in range(N))
output=min(testA,testB,testC)
print(output)
### BUGGY CODE ###

import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

cons = 10 ** 6
Ps = primes(cons)
flags = [[0 for _ in range(n)] for _ in range(len(Ps))]
pairwiseFlag = True
setwiseFlag = True

for ia, a in enumerate(As):
  index = bisect.bisect_right(Ps, math.ceil(math.sqrt(a)))
  temp = 0
  for ip, p in enumerate(Ps[:index]):
    if a % p == 0:
      flags[ip][ia] = 1
for i in range(len(Ps)):
  s = sum(flags[i])
  if s >= 2:
    pairwiseFlag = False
  if s == n:
    setwiseFlag = False

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')


### FIXED CODE ###

import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

# cons = 10 ** 6
# is_prime = [True] * (cons + 1)
# is_prime[0] = False
# is_prime[1] = False
# for i in range(2, int(cons**0.5) + 1):
#     if not is_prime[i]:
#         continue
#     for j in range(i * 2, cons + 1, i):
#         is_prime[j] = False
# Ps = [i for i in range(cons + 1) if is_prime[i]]
def eratosthenes(n):
    is_prime = [0, 0] + [1] * (n - 1)
    for i in range(int(n**0.5) + 1):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return [i for i, pi in enumerate(is_prime) if pi == 1]
Ps = eratosthenes(10 ** 6)

def factorize(n):
    primes = set()
    for p in Ps:
        if p * p > n:
            break
        while n % p == 0:
            n //= p
            primes.add(p)
    if n > 1:
        primes.add(n)
    return primes

gcd = As[0]
for a in As:
  gcd = math.gcd(gcd, a)
setwiseFlag = (gcd == 1)

pairwiseFlag = True
target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target |= primes

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')
### BUGGY CODE ###

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

cnt = 1

for i in range(1, N):
  if P[i] == min(P[:i+1]):
    cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
min_p = P[0]
cnt = 0

for p in P:
  if p <= min_p:
    min_p = p
    cnt += 1

print(cnt)
### BUGGY CODE ###

N = int(input())
X = tuple(map(int,input().split()))
test = int(N/2)
for i in range(len(X)):
    temp = list(X)
    temp.pop(i)
    temp = sorted(temp)
    print(temp[test-1])


### FIXED CODE ###

N = int(input())
X = list(map(int,input().split()))
X_sorted = sorted(X)
X_median = (N)/2
median1 = X_sorted[int(X_median)]
median2 = X_sorted[int(X_median-1)]
for i in range(N):
    if X[i] >=median1:
        print(median2)
    else:
        print(median1)
### BUGGY CODE ###

n=int(input())
a=list()
for i in range (n):
    a.append(int(input()))
new_a_reverse=sorted(a,reverse=True)
for i in range(n):
    if(max(a)==a[i]):
        print(new_a_reverse[1])
    elif(max(a)!=a[i]):
        print(max(a))


### FIXED CODE ###

n=int(input())
a=list()
for i in range (n):
    a.append(int(input()))
new_a_reverse=sorted(a,reverse=True)
max=new_a_reverse[0]
max2=new_a_reverse[1]
for i in a:
    if(i==max):
        print(max2)
    else:
        print(max)
### BUGGY CODE ###

def main():

    s = input()
    t = input()
    m, n = len(s), len(t)
    dp = [["" for _ in range(n+1)] for _ in range(2)]

    for i in range(m):
        for j in range(n):
            if s[i] == t[j]:
                dp[(i+1)%2][j+1] = dp[i%2][j] + s[i]
            else:
                if len(dp[(i+1)%2][j]) >= len(dp[i%2][j+1]):
                    dp[(i+1)%2][j+1] = dp[(i+1)%2][j]
                else:
                    dp[(i+1)%2][j+1] = dp[i%2][j+1]
    return dp[(i+1)%2][n]


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

### FIXED CODE ###

def main():

    s = input()
    t = input()
    m, n = len(s), len(t)
    dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

    for i in range(m):
        for j in range(n):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    i, j = m, n
    ans = ""
    while i > 0 and j > 0:
        if s[i-1] == t[j-1]:
            ans += s[i-1]
            i -= 1
            j -= 1
        elif dp[i][j-1] > dp[i-1][j]:
            j -= 1
        else:
            i -= 1
    return ans[::-1]


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

n=int(input())
a=list(map(int,input().split()))
q=int(input())
num=[[a.count(i+1)] for i in range(10**5)]
ans=sum(a)
for i in range(q):
    b,c=map(int,input().split())
    ans=ans+(c-b)*num[b-1][0]
    num[c-1][0]+=num[b-1][0]
    num[b-1][0]=0
    print(ans)
    

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
num=[0]*(10**5+1)
ans=sum(a)
for i in a:
    num[i]+=1
for i in range(q):
    b,c=map(int,input().split())
    ans=ans+(c-b)*num[b]
    num[c]+=num[b]
    num[b]=0
    print(ans)
### BUGGY CODE ###

from collections import deque
from sys import exit, stdin
S = deque(stdin.readline().rstrip())
Q = int(stdin.readline().rstrip())
query = [stdin.readline().rstrip().split() for _ in range(Q)]
for q in query:
    if q[0] == '1':
        S.reverse()
    elif q[0] == '2':
        if q[1] == '1':
            S.appendleft(q[2])
        elif q[1] == '2':
            S.append(q[2])
print(''.join(S))

### FIXED CODE ###

from collections import deque
from sys import exit, stdin

S = deque(stdin.readline().rstrip())
Q = int(stdin.readline().rstrip())
query = [stdin.readline().rstrip().split() for _ in range(Q)]
front = 0

for q in query:
    if q[0] == '1':
        if front == 0:
            front = -1
        elif front == -1:
            front = 0
    elif q[0] == '2':
        if q[1] == '1':
            if front == 0:
                S.appendleft(q[2])
            elif front == -1:
                S.append(q[2])
        elif q[1] == '2':
            if front == 0:
                S.append(q[2])
            elif front == -1:
                S.appendleft(q[2])
if front == 0:
    print(''.join(S))
elif front == -1:
    S.reverse()
    print(''.join(S))
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
H, W = MAP()
S = [input() for _ in range(H)]

w = [[-1]*W for _ in range(H)]
h = [[-1]*W for _ in range(H)]

for i in range(H):
	cnt = 0
	for j in range(W):
		if S[i][j] == ".":
			cnt += 1
			w[i][j] = cnt
		else:
			cnt = 0
	for j in range(W-2, -1, -1):
		if S[i][j] == ".":
			w[i][j] = max(w[i][j], w[i][j+1])


for i in range(W):
	cnt = 0
	for j in range(H):
		if S[j][i] == ".":
			cnt += 1
			h[j][i] = cnt
		else:
			cnt = 0

	for j in range(H-2, -1, -1):
		if S[j][i] == ".":
			h[j][i] = max(h[j][i], h[j+1][i])


ans = 0
for i in range(H):
	for j in range(W):
		if h[i][j] != -1 and w[i][j] != -1:
			ans = max(ans, h[i][j]+w[i][j]-1)
print(ans)








### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
H, W = MAP()
S = [input() for _ in range(H)]

w = [[-1]*W for _ in range(H)]
h = [[-1]*W for _ in range(H)]

for i in range(H):
	cnt = 0
	for j in range(W):
		if S[i][j] == ".":
			cnt += 1
			w[i][j] = cnt
		else:
			cnt = 0
	for j in range(W-2, -1, -1):
		if S[i][j] == ".":
			w[i][j] = max(w[i][j], w[i][j+1])


for i in range(W):
	cnt = 0
	for j in range(H):
		if S[j][i] == ".":
			cnt += 1
			h[j][i] = cnt
		else:
			cnt = 0

	for j in range(H-2, -1, -1):
		if S[j][i] == ".":
			h[j][i] = max(h[j][i], h[j+1][i])


ans = 0
for i in range(H):
	for j in range(W):
		if h[i][j] != -1 and w[i][j] != -1:
			ans = max(ans, h[i][j]+w[i][j]-1)
print(ans)