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

x, y, z, k = map(int, input().split())
Lis = []
for _ in range(3):
    L = list(map(int, input().split()))
    L.sort(reverse=True)
    Lis.append(L)

Li = [[0, 0, 0]]
def search():
    global dic
    L = []
    for a, b, c in Li:
        for d, e, f in [[1, 0, 0], [0, 1, 0], [0, 0, 1]]:
            if a+d < x and b+e < y and c+f < z and [a+d, b+e, c+f] not in Li:
                re = Lis[0][a+d] + Lis[1][b+e] + Lis[2][c+f]
                L.append([re, a+d, b+e, c+f])
    L.sort(reverse=True)
    Li.append([L[0][1], L[0][2], L[0][3]])
    return L[0][0]
    

for i in range(k):
    if i == 0:
        ans = Lis[0][0] + Lis[1][0] + Lis[2][0]
        print(ans)
    else:
        print(search())


### FIXED CODE ###

x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

Q = []
Q.append([A[0]+B[0]+C[0], 0, 0, 0])
M = {(0, 0, 0):True}

def search():
    global Q
    q = Q.pop()
    a = q[1]
    b = q[2]
    c = q[3]
    if a+1 < x and (a+1, b, c) not in M:
        Q.append([A[a+1]+B[b]+C[c], a+1, b, c])
        M[(a+1, b, c)] = True
    if b+1 < y and (a, b+1, c) not in M:
        Q.append([A[a]+B[b+1]+C[c], a, b+1, c])
        M[(a, b+1, c)] = True
    if c+1 < z and (a, b, c+1) not in M:
        Q.append([A[a]+B[b]+C[c+1], a, b, c+1])
        M[(a, b, c+1)] = True
    Q.sort()
    return q[0]

for _ in range(k):
    print(search())
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
c = 0
A_ = [0]
for i in range(0,N):
  A_.append(A_[i]+A[i])
A_.sort()
A_set = list(set(A_))
ans = 0
for i in A_set:
  n = A_.count(i)
  ans += n*(n-1)//2
print(ans)



### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
c = 0
A_ = [0]
for i in range(0,N):
  A_.append(A_[i]+A[i])
ans = 0
A_set = (Counter(A_))
print(sum(v*(v-1)//2 for v in A_set.values()))
### BUGGY CODE ###

from sys import stdin
n = int(input())
r=[int(input()) for i in range(n)]
rv = r[::-1][:-1]
m = None
for j,r_j in enumerate(rv):
    for r_i in r[:-(j+1)]:
        t = r_j - r_i
        if m == None or t > m:
            m = t
print(m)

### FIXED CODE ###

n = int(input())
minv = int(input())
maxv = -2*10**9
for i in range(n-1):
    r = int(input())
    maxv = max(maxv,r-minv)
    minv = min(minv,r)
print(maxv)
### BUGGY CODE ###

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

N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]

def main(N, A):
    now = [-1]*N
    day = 0
    while True:
        # terminal condition
        count = 0
        for i in range(N):
            if len(A[i]) == 0:
                count += 1
        if count == N:
            return day

        # if not terminal make new now
        for i in range(N):
            if now[i] == -1 and len(A[i]) > 0:
                now[i] = A[i].pop()
        
        # see if we have match today
        have_match = False
        for i in range(N):
            if now[i] != -1 and now[now[i]-1] - 1 == i:
                now[now[i]-1] = -1
                now[i] = -1
                have_match = True
        if not have_match:
            return -1
        day += 1

print(main(N, A))

### FIXED CODE ###

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

N = int(input())
A = [[n-1 for n in list(map(int, input().split()))] + [-1] for _ in range(N)]
A = [a[::-1] for a in A]

def main(N, A):
    now = [A[i].pop() for i in range(N)]
    day = 0
    rest = N * (N-1)
    candidate = set(range(N))

    # WCS O(N**2) <- 1日に1試合だけのときN(N-1)/2回while文が繰り返される
    while True:
        # terminal condition
        # O(1)
        if rest == 0:
            return day

        # see if we have match today
        # O(N)
        have_match = False
        # tmp = now.copy()
        # for i in range(N):
        #     if now[now[i]] == i:
        #         tmp[i] = A[i].pop()
        #         rest -= 1
        #         have_match = True
        # now = tmp
        change = []
        next_candidate = set()
        for i in candidate:
            if now[now[i]] == i:
                j = A[i].pop()
                change.append((i, j))
                # あとで(a, b)でnow[a] = bに更新する
                next_candidate.add(i)
                if j != -1:
                    next_candidate.add(j)
                
                rest -= 1
                have_match = True

        if len(change) == 0:
            return -1
        for (a, b) in change:
            now[a] = b
            
        candidate = next_candidate
        
        day += 1

print(main(N, A))
### BUGGY CODE ###

from collections import Counter
n = int(input())
d = list(input() for _ in range(n))
D = Counter(d)
m = D.most_common()[0][1]
for i in range(len(D)):
  k = D.most_common()[i][1]
  if m != k:
    break
  p = i
D = D.most_common()[:p+1]
D = sorted(D)
for i in D:
  print(i[0])

### FIXED CODE ###

from collections import Counter
n = int(input())
d = list(input() for _ in range(n))
D = Counter(d)
m = max(D.values())
l = []
for i,j in D.most_common():
  if m != j:
    break
  l.append(i)
l.sort()
for i in l:
  print(i)
### BUGGY CODE ###

s = input()
count = 0
while "01" in s or "10" in s:
    while "01" in s:
        s = s.replace("01", "", 1)
        count += 1
    while "10" in s:
        s = s.replace("10", "", 1)
        count += 1

print(count * 2)


### FIXED CODE ###

s = input().rstrip()
a = s.count("0")
b = s.count("1")
print(min(a,b)*2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline 
N=int(input())
L=list(map(int,input().split()))
Q=int(input())
for i in range(Q):
  a,b=map(int,input().split())
  L=[i if i!=a else b for i in L]
  print(sum(L))

### FIXED CODE ###

import sys
input = sys.stdin.readline 
N=int(input())
L=list(map(int,input().split()))
Q=int(input())
R=[0]*(10**5)
for i in L:
  R[i-1]+=1
ans=sum(L)
for i in range(Q):
  a,b=map(int,input().split())
  R[b-1]+=R[a-1]
  ans+=(b-a)*R[a-1]
  R[a-1]=0
  print(ans)
### BUGGY CODE ###

def main():
    N=int(input())
    A=[0]*N
    shougen=[[] for i in range(0,N)]
    for i in range(0,N):
        A[i]=int(input())
        for j in range(0,A[i]):
            a,b=map(int,input().split())
            shougen[i].append([a,b])
    m=0
    for i in range(0,2**N):
        flag=0
        check=[]
        for j in range(0,N):
            if i>>j & 1==1:
                check.extend(shougen[j])#証言の収集
        for j in range(0,N):
            if ([j+1,0] in check) or ([j+1,1] in check):
                if [j+1,0] in check:
                    if j==0:
                        data=[0]
                    else:
                        data.append(0)
                if [j+1,1] in check:
                    if j==0:
                        data=[1]
                    else:
                        data.append(1)

            else:
                if j==0:
                    data=[2]
                else:
                    data.append(2)#証言から得られる正直者リスト
        for j in range(0,N):
            if data[j]!=2:
                if int(data[j])!=(i>>j)%2 :
                    flag=1
        if len(data)!=N:
            flag=1
        if flag==0:
            test=sum(i>>j &1 for j in range(0,N))
            if test>m:
                m=test

    print(m)

if __name__ == '__main__':
    main()


### FIXED CODE ###

N=int(input())
shougen=[(0,0) for i in range(0,N)]
for i in range(0,N):
    A=int(input())
    honest=0
    unkind=0
    for j in range(0,A):
        x,y=map(int,input().split())
        if y==0:
            unkind+=2**(x-1)
        else:
            honest+=2**(x-1)
    shougen[i]=(honest,unkind)

ans=0
for i in range(0,2**N):
    honest=i
    unkind=2**N-1-i
    check=True
    test=0
    for j in range(0,N):
        if (i>>j)&1 ==1:
            test+=1
            x,y=shougen[j]
            if (honest-x)^x!=honest or (unkind-y)^y!=unkind:
                check=False
    if check:
        if test>ans:
            ans=test

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

N, M = map(int, input().split())
cards = [0 for x in range(N)]

for x in range(M):
    l, m = map(int, input().split())
    for y in range(l - 1, m):
        cards[y] = cards[y] + 1

sum = 0
for x in cards:
    if x == M:
        sum = sum + 1

print(sum)

### FIXED CODE ###

N, M = map(int, input().split())
maxL = 0
minM = N
for x in range(M):
    l, m = map(int, input().split())
    maxL = max(maxL, l)
    minM = min(minM, m)

print(max(minM - maxL + 1, 0))
### BUGGY CODE ###

md = 10 ** 9 + 7
ks = input()
d = int(input())
dp = [0] * d
just = 0

for k in ks:
    k = int(k)
    ndp = [0] * d

    for di, dk in enumerate(dp):
        for ndi in range(di, di + 10):
            ndp[ndi % d] += dk

    for ndi in range(just, just + k):
        ndp[ndi % d] += 1

    for dk in dp:
        dk %= md

    just = (just + k) % d
    dp = ndp

print((dp[0] + (just == 0) - 1) % md)


### FIXED CODE ###

def f(ks, d):
    md = 10 ** 9 + 7
    dp = [0] * d
    just = 0

    for k in ks:
        ndp = [0] * d

        for di, dk in enumerate(dp):
            for ndi in range(di, di + 10):
                ndp[ndi % d] += dk

        for ndi in range(just, just + k):
            ndp[ndi % d] += 1

        ndp = [ndk % md for ndk in ndp]

        just = (just + k) % d
        dp = ndp

    print((dp[0] + (just == 0) - 1) % md)


ks = list(map(int, list(input())))
d = int(input())
f(ks, d)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Sep  1 20:25:02 2019

@author: Yamazaki Kenichi
"""

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

T = [0 for i in range(N)]
today = [True for i in range(N)]

ans = 0
counta = 0
while counta < N:
    today = [True for i in range(N)]
    for i in range(N):
        if today[i]:
            vs = A[i][T[i]] - 1
            if A[vs][T[vs]] == i + 1 and today[vs]:
                T[i] += 1
                T[vs] += 1
                if T[i] == N - 1:
                    T[i] = 0
                    counta += 1
                if T[vs] == N - 1:
                    T[vs] = 0 
                    counta += 1
                today[i], today[vs] = False, False
#        print(i,vs,today,T)
    flg = True
    for i in range(N):
        flg *= today[i]
    if flg :
        ans = -1
        break
    ans += 1
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Sep  1 21:55:48 2019

@author: Yamazaki Kenichi
"""


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

T = [0 for i in range(N)]
today = [True for i in range(N)]
yesterday = [i for i in range(N)]

ans = 0
counta = 0
while counta < N:
    today = set([])
    today_p = []
    for i in yesterday:
        if not i in today:
            vs = A[i][T[i]] - 1
            if A[vs][T[vs]] == i + 1 and not vs in today:
                T[i] += 1
                T[vs] += 1
                if T[i] == N - 1:
                    T[i] = 0
                    counta += 1
                if T[vs] == N - 1:
                    T[vs] = 0 
                    counta += 1
                today.add(i)
                today.add(vs)
                today_p.extend([i,vs])
    yesterday = today_p
#        print(i,vs,today,T)
    if len(today_p) == 0:
        ans = -1
        break
    ans += 1
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())

sei_or_gyaku = 1
ans = s[:]

for i in range(q):
    sirei = input()
    if len(sirei) == 1:
        ti = int(sirei)
        sei_or_gyaku *= -1
    else:
        ti, fi, ci = map(str, sirei.split())
        ti, fi = int(ti), int(fi)
        if fi == 1:
            if sei_or_gyaku == 1:
                ans = ci + ans
            else:
                ans = ans + ci
        else:
            if sei_or_gyaku == 1:
                ans = ans + ci
            else:
                ans = ci + ans


if sei_or_gyaku == 1:
    print(ans)
else:
    print(ans[::-1])

### FIXED CODE ###

s = input()
q = int(input())

sei_or_gyaku = 1
mae = ''
ato = ''

for i in range(q):
    sirei = input()
    if len(sirei) == 1:
        ti = int(sirei)
        sei_or_gyaku *= -1
    else:
        ti, fi, ci = map(str, sirei.split())
        ti, fi = int(ti), int(fi)
        if fi == 1:
            if sei_or_gyaku == 1:
                mae += ci
            else:
                ato += ci
        else:
            if sei_or_gyaku == 1:
                ato += ci
            else:
                mae += ci

mae = mae[::-1]
ans = mae + s + ato
if sei_or_gyaku == 1:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

N = int(input())

A = []
for i in range(N):
  tmp = int(input())
  A.append(tmp)
  
for i in range(N):
  tmp_list = A[:]
  tmp_list.pop(i)
  #print(tmp_list)
  tmp_set = set(tmp_list)
  print(max(tmp_set))

### FIXED CODE ###

n=int(input())
l=[int(input()) for i in range(n)]
a=sorted(l)
b=a[-1]
c=a[-2]
for i in l:
  if i!=b:
    print(b)
  else:
    print(c)
### BUGGY CODE ###

# suffix array
# z-algorithm
# rolling-hash
# dp
n = int(input())
s = input()

# z-algorithm
# i左端
# j iからの距離
# k i-i+jの間を進みながら比較
ans = 0
for num in range(n - 1):
    S = s[num:]
    A = [0] * (n - num)
    A[0] = n - num
    i = 1
    j = 0
    while i < n - num:
        while i + j < n - num and S[j] == S[i + j]:
            j += 1
        A[i] = j
        ans = max(ans, min(i, j))
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < n - num and k + A[k] < j:
            A[i + k] = A[k]
            ans = max(ans, min(k, A[k]))
            k += 1
        i += k
        j -= k
print(ans)


### FIXED CODE ###

# suffix array
# z-algorithm
# rolling-hash
# dp
n = int(input())
s = input()

# z-algorithm
# i左端
# j iからの距離
# k i-i+jの間を進みながら比較
ans = 0
for num in range(n - 1):
    S = s[num:]
    A = [0] * (n - num)
    A[0] = n - num
    i = 1
    j = 0
    while i < n - num:
        while i + j < n - num and S[j] == S[i + j]:
            j += 1
        A[i] = j
        ans = max(ans, min(i, j))
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < n - num and k + A[k] < j:
            A[i + k] = A[k]
            ans = max(ans, min(k, A[k]))
            k += 1
        i += k
        j -= k
print(ans)
### BUGGY CODE ###

combNum = [0]*100
inNum = 0
while True:
    n,x = map(int, input().split())
    calcResult = 0
    numList1 = list(range(1,n+1,1))
    numList2 = list(range(1,n+1,1))
    numList3 = list(range(1,n+1,1))
    if n is x is 0:
        break
    else:
        
        for index1 in range(n):
            for index2 in range(n):
                for index3 in range(n):
                    #index = [numList1[index1], numList2[index2], numList3[index3]]
                    if numList1[index1] is numList2[index2] or numList1[index1] is numList3[index3] or numList2[index2] is numList3[index3] or numList1[index1] is numList2[index2] is numList3[index3]:
                    #if index.count(numList1[index1])>1 or index.count(numList1[index2])>1 or index.count(numList1[index3])>1:
                        pass                
                    else:
                        if numList1[index1]<numList2[index2]<numList3[index3]:
                            calcResult = numList1[index1] + numList2[index2]+numList3[index3]
                            if calcResult == x:
                                combNum[inNum] =combNum[inNum]+1
                                
                        else:
                            pass
        inNum = inNum+1
for index in range(inNum):
    print(combNum[index])


### FIXED CODE ###

dataNum = 0
combNum = [0] * 100
while True:
    n,x=map(int, input().split())
    if n is x is 0:
        break
    else:
        for a in range(1,n-1):
            for b in range(a+1,n):
                for c in range(b+1,n+1):
                    calcResult = a + b + c
                    if calcResult == x:
                        combNum[dataNum] += 1
                    else:
                        pass
    dataNum += 1

for index in range(dataNum):
    print(combNum[index])
### BUGGY CODE ###

import math
L = input().split()
sp = 998244353
# approx 10**9
N = int(L[0])
A = int(L[1])
B = int(L[2])
K = int(L[3])

def binom(n,m):
	if n == m:
		return 1
	elif m == 1:
		return n
	elif m > n:
		return 0
	else:
		a = math.factorial(n)
		b = math.factorial(m)
		c = math.factorial(n - m)
		return a // (b*c)

# max is A*N + B*N
sum = 0
for i in range(0,N):
	if (K - A*i) % B == 0:
		j = (K-A*i)//B
		sum += (binom(N,i) * binom(N,j)) % sp

print(sum)



### FIXED CODE ###

N,A,B,K = map(int,input().split())
sprime = 998244353 # approx 10**9
A,B = sorted((A,B))
if (A+B) * N < K:
	print(0)
	exit()
 
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
 
memo = [0] * (N+1)
memo[0] = memo[N] = 1
for i in range(1,N//2+1):
	v = memo[i-1] * (N-i+1) * modinv(i,sprime)
	v = v % sprime
	memo[i] = memo[N-i] = v
 
# max is A*N + B*N
sum = 0
for b in range(N+1):
  a = (K-b*B)//A
  if 0 <= a <= N and a*A+b*B == K:
    sum += memo[a]*memo[b]
    sum %= sprime

print(sum)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ab = []
for ai in a:
    for bi in b:
        ab.append(ai + bi)
ab.sort(reverse=True)
if k < len(ab):
    ab = ab[:k]

ans = []
for abi in ab:
    for ci in c:
        ans.append(abi + ci)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])


### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ab = []
for ai in a:
    for bi in b:
        ab.append(ai + bi)
ab.sort(reverse=True)
if k < len(ab):
    ab = ab[:k]

ans = []
for abi in ab:
    for ci in c:
        ans.append(abi + ci)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

#22
N,x = map(int,input().split())
a = list(map(int,input().split()))
cou =0

a.sort()

for i in a:
    if i >x:
        break
    cou +=1
    x -= i
    
while x>0:
    for i in a:
        if x%i ==0:
            cou -=1
            break
        while x > i:
            x-=i
        cou -= 1
print(cou)
    

### FIXED CODE ###

#22
N,x = map(int,input().split())
a = list(map(int,input().split()))

a.sort()

if sum(a) ==x:
    print(N)
elif sum(a) < x:
    print(N-1)
else:
    for i in range(N):
        if sum(a[0:i+1]) >x:
            print(i)
            break
### BUGGY CODE ###

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

dp = [float('inf')] * n

dp[0] = 0
for i in range(n):
  for j in range(i+1):
    if j <= k:
      dp[i] = min(dp[i], dp[i-j]+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 = [float('inf')] * n

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

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

import numpy as np
n,k = map(int,input().split())	
s=list(input())	

li = np.array([])
is1s = False
if s[0] == "1":
    is1s = True
cnt0 = 0
cnt1 = 0
for i in range(len(s)):
    if s[i] == "0" :
        cnt0 += 1
    if s[i] == "1":
        cnt1 += 1
    if i >= 1:
        if s[i] == "0" and s[i-1] == "1":
            li=np.append(li,cnt1)
            cnt1 = 0
        if s[i] == "1" and s[i-1] == "0": 
            li=np.append(li,cnt0)
            cnt0 = 0

if (cnt1 > 0):
    li=np.append(li,cnt1)
if (cnt0 > 0):
    li=np.append(li,cnt0)
pivot = 2 * k 

anslist=np.array([])
if(is1s):
    for i in range(len(li)):
        if(i % 2 == 0):
            tmp = np.sum(li[i:min(len(li), i+pivot+1)])
            anslist=np.append(anslist, tmp)
else:
    for i in range(len(li)):
        if(i % 2 == 1):
            tmp = np.sum(li[i:min(len(li), i+pivot+1)])
            anslist=np.append(anslist ,tmp)
    anslist=np.append(anslist, np.sum(li[0:pivot]))

print(int(np.max(anslist)))


### FIXED CODE ###

import numpy as np
n,k = map(int,input().split())	
s=list(input())	

li = []
is1s = False
if s[0] == "1":
    is1s = True
cnt0 = 0
cnt1 = 0
for i in range(len(s)):
    if s[i] == "0" :
        cnt0 += 1
    elif s[i] == "1":
        cnt1 += 1
    if i >= 1:
        if s[i] == "0" and s[i-1] == "1":
            li.append(cnt1)
            cnt1 = 0
        elif s[i] == "1" and s[i-1] == "0": 
            li.append(cnt0)
            cnt0 = 0

if (cnt1 > 0):
    li.append(cnt1)
if (cnt0 > 0):
    li.append(cnt0)
pivot = 2 * k 
li = np.array(li)
anslist=[]
if(is1s):
    for i in range(len(li)):
        if(i % 2 == 0):
            tmp = np.sum(li[i:min(len(li), i+pivot+1)])
            anslist.append(tmp)
else:
    for i in range(len(li)):
        if(i % 2 == 1):
            tmp = np.sum(li[i:min(len(li), i+pivot+1)])
            anslist.append(tmp)
    anslist.append(sum(li[0:pivot]))

print(max(anslist))
### BUGGY CODE ###

import numpy as np

N,K = list(map(int, input().split()))
while True:
  temp_N=N-K
  if temp_N>0:
    N=np.abs(temp_N)
  else:
    break
if np.abs(temp_N)>N:
  print(N)
else:
  print(np.abs(temp_N))


### FIXED CODE ###

n, k = map(int, input().split())
print(min(n%k, k - n%k))
### BUGGY CODE ###

N = int(input())
A = 1
B = 1
p = 0

while A < N:
  while A * B < N:
    p += 1
    B += 1
  A += 1
  B = 1

print(p)

### FIXED CODE ###

N = int(input())
A = 1
B = 1
d = 0
e = 0

while A < N:
  while A * B < N:
    if A == B:
      e += 1
    else:
      d += 1
    B += 1
  A += 1
  B = A

print(d*2+e)
### BUGGY CODE ###

h,w = map(int, input().split())
Data = [[[0,0,0,0] for i in range(w)] for j in range(h)]
S = [input() for i in range(h)]
for i in range(h):
    for j in range(w):
        if S[i][j] == ".":
            if j > 0:
                Data[i][j][0] = Data[i][j-1][0] + 1
            else:
                Data[i][j][0] = 1
for i in range(h):
    for j in range(w-1,-1,-1):
        if S[i][j] == ".":
            if j < w-1:
                Data[i][j][1] = Data[i][j+1][1] + 1
            else:
                Data[i][j][1] = 1
for i in range(w):
    for j in range(h):
        if S[j][i] == ".":
            if j > 0:
                Data[j][i][2] = Data[j-1][i][2] + 1
            else:
                Data[j][i][2] = 1
for i in range(w):
    for j in range(h-1,-1,-1):
        if S[j][i] == ".":
            if j < h-1:
                Data[j][i][3] = Data[j+1][i][3] + 1
            else:
                Data[j][i][3] = 1
ans = 0
for i in range(h):
    for j in range(w):
       ans = max(sum(Data[i][j])-3,ans)
print(ans)

### FIXED CODE ###

h,w = map(int, input().split())
S = [input() for i in range(h)]
U = [[0]*w for i in range(h)]
D = [[0]*w for i in range(h)]
L = [[0]*w for i in range(h)]
R = [[0]*w for i in range(h)]

for i in range(h):
    for j in range(w):
        if S[i][j] == ".":
            if j > 0:
                L[i][j] = L[i][j-1] + 1
            else:
                L[i][j] = 1
    for j in range(w-1,-1,-1):
        if S[i][j] == ".":
            if j < w-1:
                R[i][j] = R[i][j+1] + 1
            else:
                R[i][j] = 1
for i in range(w):
    for j in range(h):
        if S[j][i] == ".":
            if j > 0:
                D[j][i] = D[j-1][i] + 1
            else:
                D[j][i] = 1
    for j in range(h-1,-1,-1):
        if S[j][i] == ".":
            if j < h-1:
                U[j][i] = U[j+1][i] + 1
            else:
                U[j][i] = 1
ans = 0
for i in range(h):
    for j in range(w):
       ans = max(L[i][j]+R[i][j]+U[i][j]+D[i][j]-3,ans)
print(ans)