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

import bisect
A, B, Q = map(int, input().split())
s = [-10**11] + [int(input()) for i in range(A)] + [10**11]
t = [-10**11] + [int(input()) for i in range(B)] + [10**11]

#self_jisso
def nibutans(x, l, r):
	if r - l <= 1:
		return r
	nibu = (r + l) // 2
	return nibutans(x, nibu, r) if x > s[nibu] else nibutans(x, l, nibu)

def nibutant(x, l, r):
	if r - l <= 1:
		return r
	nibu = (r + l) // 2
	return nibutant(x, nibu, r) if x > t[nibu] else nibutant(x, l, nibu)

for i in range(Q):
	x = int(input())
	sr, tr = nibutans(x, 0, A + 1), nibutant(x, 0, B + 1)
	ans = 10**17
	for S in [s[sr - 1], s[sr]]:
		for T in [t[tr - 1], t[tr]]:
			d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
#			print(str(ans) + ' ' + str(d1) + ' ' + str(d2))
			ans = min(ans, d1, d2)
	print(ans)


### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
s = [-10**11] + [int(input()) for i in range(A)] + [10**11]
t = [-10**11] + [int(input()) for i in range(B)] + [10**11]

'''
def nibutans(x, l, r):
	if r - l <= 1:
		return max(r, l)
	nibu = (r + l) // 2
	return nibutans(x, nibu, r) if x > s[nibu] else nibutans(x, l, nibu)

def nibutant(x, l, r):
	if r - l <= 1:
		return max(r, l)
	nibu = (r + l) // 2
	return nibutant(x, nibu, r) if x > t[nibu] else nibutant(x, l, nibu)

for i in range(Q):
	x = int(input())
	sr, tr = nibutans(x, 0, A + 1), nibutant(x, 0, B + 1)
	ans = 10**17
	for S in [s[sr - 1], s[sr]]:
		for T in [t[tr - 1], t[tr]]:
			d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
#			print(str(ans) + ' ' + str(d1) + ' ' + str(d2))
			ans = min(ans, d1, d2)
	print(ans)
'''
for q in range(Q):
	x = int(input())
	b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
	res = 10**13
	for S in [s[b - 1], s[b]]:
		for T in [t[d - 1], t[d]]:
			d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
			res = min(res, d1, d2)
	print(res)
### BUGGY CODE ###

import sys
n=int(input())
maxmatch=n*(n-1)
a=[]
for i in range(n):
  b=list(map(int,input().split()))
  a.append(list(reversed(b)))
day=0
 
match=[0]*(n+1)
jyunban=[i for i in range(n)]
jyunban_n=[]
 
while match[n]<maxmatch:
  jyunban_n.clear()
  day+=1
  check=[True]*(n+1)
  for i in jyunban:
    if match[i]==n-1 or check[i]==False:
      continue
    else:
      vs=a[i][-1]-1
      if check[i] and check[vs]:
        if a[vs][-1]-1==i:
          a[i].pop(-1)
          a[vs].pop(-1)
          match[i]+=1
          match[vs]+=1
          match[n]+=2
          check[i]=False
          check[vs]=False
          check[n]=False
          jyunban_n.append(i)
          jyunban_n.append(vs)
      
    if i==jyunban[-1] and check[n]:
      print(-1)
      sys.exit()
  jyunban=jyunban_n[:]
        
print(day)

### FIXED CODE ###

import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
 
N = I()
a = [IL()[::-1] for i in range(N)]
 
used = [-1]*N
updatelist = [i for i in range(N)]
total = N*(N-1)//2
cnt = 0
days = 0
ul = []
while updatelist:
  ul = []
  for i in updatelist:
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        ul.append(i)
        ul.append(numIND)
        cnt += 1
  else:
    updatelist = ul[:]
    if len(ul) != 0:
      days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(-1)
### BUGGY CODE ###

import numpy as np
n,w = map(int, input().split())
high = np.array([[0]*(w+1)]*(n+1),np.int)
for i in range(1,n+1):
    weight, value = map(int, input().split())
    for j in range(w+1):
        if j < weight:
            high[i][j] = high[i-1][j]
        else:
            high[i][j] = max([high[i-1][j-weight]+value, high[i-1][j]])
print(high[n][w])

### FIXED CODE ###

n,w = map(int, input().split())
high = [0] * (w + 1)
for i in range(n):
    weight, value = map(int, input().split())
    if weight <= w:
        renewal = high[:weight]
        renewal += [max([j+value, k]) for j,k in zip(high[:w-weight+1], high[weight:])]
        high = renewal
print(high[w])
### BUGGY CODE ###

n = int(input())
import math
num = math.factorial(n)
ans = 0
for i in range(1,num+1):
  if num%i==0:
    ans+=1
print(ans%(10**9+7))

### FIXED CODE ###

n = int(input())
import math
num = math.factorial(n)
dic={}
i = 2
ans = 1
while num != 1:
  cnt = 1
  while num%i == 0:
    num = num//i
    cnt+=1
  ans = ans*cnt
  i +=1
print(ans%(10**9+7))
### BUGGY CODE ###

n,k = map(int,input().split())
s = list(map(int,input()))
s_list = list()
num = s[0]
temp_streak = 0
temp_max = 0
[s_list.append(0) for i in range(1+s[0])]

for i in s:
    if i == num:
        temp_streak += 1
    else:
        s_list.append(temp_streak)
        temp_streak = 1
        num = i
s_list.append(temp_streak)
[s_list.append(0) for i in range(1+s[-1])]
# odd = len(s_list)%2
num_i = len(s_list) // 2 
#print(s_list)

for i in range(max(num_i+1-k,1)):
    temp_max = max(temp_max,sum(s_list[i*2:i*2+k*2+1]))
print(temp_max)




#print(s_list)

### FIXED CODE ###

n,k = map(int,input().split())
s = list(map(int,input()))
s_list = list()
num = s[0]
temp_streak = 0
# temp_max = 0
# temp_sum = 0
[s_list.append(0) for i in range(1+s[0])]

for i in s:
    if i == num:
        temp_streak += 1
    else:
        s_list.append(temp_streak)
        temp_streak = 1
        num = i

s_list.append(temp_streak)
[s_list.append(0) for i in range(1+s[-1])]
# odd = len(s_list)%2
num_i = len(s_list) // 2 
# print(s_list)
temp_max = sum(s_list[0:min(k*2+1,len(s_list) + 1)])
temp_sum = temp_max
temp_max_debug = temp_max
# print(temp_max)
for i in range(1,max(num_i+1-k,1)):
    temp_sum = temp_sum - s_list[i*2-2] - s_list[i*2-1] + s_list[i*2+k*2-1] + s_list[i*2+k*2]
    temp_max = max(temp_max,temp_sum)
    # temp_max_debug = max(temp_max_debug,sum(s_list[i*2:i*2+k*2+1]))
print(temp_max)
# print(temp_max_debug)



#print(s_list)
### BUGGY CODE ###

import math

def main():

    N, T = map(int, input().split())
    C = []
    for _ in range(N):
        A, B = map(int, input().split())
        C.append([B, A])
    # C.sort()

    dp = [[0, 0] for _ in range(T)]
    ans = 0
    for i in range(T):
        for j in range(N):
            if (dp[i][1] >> j) % 2 == 0:
                if i+C[j][1] > T-1:
                    ans = max(ans, dp[i][0] + C[j][0])
                else:
                    if dp[i][0]+C[j][0] > dp[i+C[j][1]][0]:
                        dp[i+C[j][1]][0] = dp[i][0]+C[j][0]
                        dp[i+C[j][1]][1] = (1 << j) | dp[i][1]

    # print(dp)
    for i in range(T):
        ans = max(ans, dp[i][0])
    return ans

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

### FIXED CODE ###

def main():

    N, T = map(int, input().split())
    C = []
    for _ in range(N):
        A, B = map(int, input().split())
        C.append([B, A])

    dp = [[0, set()] for _ in range(T)]
    ans = 0
    for i in range(T):
        for j in range(N):
            if j not in dp[i][1]:
                k = i+C[j][1]
                if k > T-1:
                    ans = max(ans, dp[i][0] + C[j][0])
                else:
                    if dp[i][0]+C[j][0] > dp[k][0]:
                        dp[k][0] = dp[i][0]+C[j][0]
                        dp[k][1] = dp[i][1] | {j}
        ans = max(ans, dp[i][0])

    return ans

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

import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()
p = nfa()

dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1.0
for i in range(n):
    for j in range(i + 1):
        dp[i + 1][j + 1] += dp[i][j] * p[i]
        dp[i + 1][j] += dp[i][j] * (1.0 - p[i])

ans = sum([dp[n][j] for j in range(n // 2 + 1, n + 1)])
print(ans)

### FIXED CODE ###

import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()
p = nfa()

dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1.0
for i in range(n):
    for j in range(i + 1):
        dp[i + 1][j + 1] += dp[i][j] * p[i]
        dp[i + 1][j] += dp[i][j] * (1.0 - p[i])

ans = sum([dp[n][j] for j in range(n // 2 + 1, n + 1)])
print(ans)
### BUGGY CODE ###

def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    
    left = [[None]*W for _ in range(H)]
    right = [[None]*W for _ in range(H)]
    up = [[None]*W for _ in range(H)]
    down = [[None]*W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                if j == 0:
                    left[i][j] = 0
                else:
                    left[i][j] = left[i][j-1] + 1
                if i == 0:
                    up[i][j] = 0
                else:
                    up[i][j] = up[i-1][j] + 1
            else:
                left[i][j] = -1
                up[i][j] = -1
            
            if S[-1-i][-1-j] == '.':
                if j == 0:
                    right[-1-i][-1-j] = 0
                else:
                    right[-1-i][-1-j] = right[-1-i][-1-(j-1)] + 1
                if i == 0:
                    down[-1-i][-1-j] = 0
                else:
                    down[-1-i][-1-j] = down[-1-(i-1)][-1-j] + 1
            else:
                right[-1-i][-1-j] = -1
                down[-1-i][-1-j] = -1

    ans = 0
    temp = [0] * W
    for i in range(H):
        for j in range(W):
            temp[j] = left[i][j] + right[i][j] + down[i][j] + up[i][j] + 1
        ans = max(ans, max(temp))
    print(ans)

main()

### FIXED CODE ###

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

    left = [[-1]*W for _ in range(H)]
    right = [[-1]*W for _ in range(H)]
    up = [[-1]*W for _ in range(H)]
    down = [[-1]*W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                if j == 0:
                    left[i][j] = 0
                else:
                    left[i][j] = left[i][j-1] + 1

    for i in range(H):
        for j in range(W):
            if S[-1-i][-1-j] == '.':        
                if j == 0:
                    right[-1-i][-1-j] = 0
                else:
                    right[-1-i][-1-j] = right[-1-i][-1-(j-1)] + 1

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                if i == 0:
                    up[i][j] = 0
                else:
                    up[i][j] = up[i-1][j] + 1

    for i in range(H):
        for j in range(W):
            if S[-1-i][-1-j] == '.':
                if i == 0:
                    down[-1-i][-1-j] = 0
                else:
                    down[-1-i][-1-j] = down[-1-(i-1)][-1-j] + 1
            
    ans = 0
    temp = [0] * W
    for i in range(H):
        for j in range(W):
            temp[j] = left[i][j] + right[i][j] + down[i][j] + up[i][j] + 1
        ans = max(ans, max(temp))
    print(ans)

main()
### BUGGY CODE ###

pattern = int(input())

xs = []
ys = []
hs = []

for _ in range(pattern):
    x, y, h = map(int, input().split(' '))
    xs.append(x)
    ys.append(y)
    hs.append(h)



correct = 0

max_h = max(hs) + 200

# 全探索
for Cx in range(101):
    for Cy in range(101):
        for H in range(max(hs), max_h):
            for x, y, h in zip(xs, ys, hs):
                if abs(x-Cx) + abs(y-Cy) == abs(h-H):
                    correct += 1
                    if correct == len(xs) and max(hs) <= H:
                        print(Cx, Cy, H)
                        exit()
                else:
                    correct = 0
                    continue

### FIXED CODE ###

N = int(input())

coords = [list(map(int, input().split(' '))) for _ in range(N)]

coords.sort(key=lambda x: x[2], reverse=True)

# 全探索
def search():
    for Cx in range(101):
        for Cy in range(101):
            x, y, h = tuple(coords[0])
            H = h + abs(Cx - x) + abs(Cy - y)
            for x, y, h in coords:
                if max(H - abs(Cx - x) - abs(Cy - y), 0) != h:
                    break
            else:
                return Cx, Cy, H

x, y, h = search()
print("{} {} {}".format(x, y, h))
### BUGGY CODE ###

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

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

print(ans)

### FIXED CODE ###

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

ans=0
val=P[0]
for i in range(N):
  if val>=P[i]:
    ans+=1
    val=P[i]
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
dic1 = {}
dic2 = {}
for i in range(N):
  if A[i] in dic1:
    dic1[A[i]] += 1
  else:
    dic1[A[i]] = 1

for j in range(N):
  ans = 0
  for k, v in dic1.items():
    if A[j] == k:
      ans += ((v-1)*(v-2))//2
    else:
      ans += (v*(v-1))//2
  print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
dic1 = {}
dic2 = {}
for i in range(N):
  if A[i] in dic1:
    dic1[A[i]] += 1
  else:
    dic1[A[i]] = 1
ans = 0
for v in dic1.values():
  ans += (v*(v-1))//2
for j in range(N):
  w = dic1[A[j]]
  v = w-1
  comb = ans -(w*(w-1))//2 + (v*(v-1))//2
  print(comb)
### BUGGY CODE ###

import itertools
N = int(input())
S = [s for s in input()]
ans = []
for (i, j, k) in itertools.combinations(S, 3):
    s = i + j + k
    #print(s)
    if s not in ans:
        ans.append(s)
print(len(ans))

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    v = str(i).zfill(3)
    idx = 0
    c = 0
    idx_now = 0
    for j in range(3):
        idx = S[idx_now:].find(v[j])
        if idx == -1:
            break
        else:
            idx_now += idx + 1
            c += 1
    if c == 3:
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
lis = []
for i in range(n):
    s = input()
    key = []
    val = []
    for j in range(10):
        cnt = 1
        if s[j] not in key and j < 9:
            for k in range(j+1,10):
                if s[j] == s[k]:
                    cnt += 1
            key.append(s[j])
            val.append(cnt)
        elif j == 9:
            if s[j] not in key:
                key.append(s[j])
                val.append(cnt)
    d = dict(zip(key, val))
    lis.append(d)
#print(lis)
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        if lis[i] == lis[j]:
            ans += 1
#print(lis[1] == lis[3])
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
dic = {}
for i in range(n):
    sorted_s = sorted(input())
    s = ""
    for j in range(10):
        s = s + sorted_s[j]
    
    if s not in dic:
        dic[s] = 1
    else:
        ans += dic[s]
        dic[s] = dic[s] + 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
import itertools
ans = 0
result = []


for i in range(len(a)):
    for j in range(i+1,len(a)):
        if i < j:
            ans += a[i] * a[j]
        
print(ans%(10 ** 9 + 7))

### FIXED CODE ###

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

ans = 0

sum_a = sum(a)


for i in range(n):
    ans += a[i] * (sum_a - a[i])
    sum_a -= a[i]

print(ans%(10 ** 9 + 7))
### BUGGY CODE ###

import functools
import operator
prod = functools.partial(functools.reduce, operator.mul)
listS = []

# N = 5 
# K = 3
# A = [96,98,95,100,20]

N, K  = map(int, input().split())
A = list(map(int,input().split()))

for i in range(0,N-K+1):
    listS.append(prod(A[i:K+i]))
    
for j in range(len(listS)-1):
    if listS[j] < listS[j+1]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N, K  = map(int, input().split())
A = list(map(int,input().split()))

for i in range(0,N-K):
    if A[i] < A[i+K]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import itertools

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

prices = list(map(int, input().split()))

ans = 1000000

for i in itertools.combinations(prices, k):
    ans = min(ans, sum(i))

print(ans)

### FIXED CODE ###

import itertools

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

prices = list(map(int, input().split()))

prices = sorted(prices)

print(sum(prices[:k]))
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(1000000)
h, w = map(int, input().split())
field = []
for _ in range(h):
    field.append(list(input()))

dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
distance = [[-1] * w for i in range(h)]

que = deque([])
for y in range(h):
    for x in range(w):
        if field[y][x] == '.':
            continue
        que.append([y, x])
        distance[y][x] = 0

while que:
    q = que.popleft()
    for i in range(4):
        now_y = q[0] + dy[i]
        now_x = q[1] + dx[i]
        if now_y < 0 or now_y >= h or now_x < 0 or now_x >= w or field[now_y][now_x] == '#':
            continue
        if distance[now_y][now_x] != -1:
            continue
        que.append([now_y, now_x])
        distance[now_y][now_x] = distance[q[0]][q[1]] + 1

draw_count = 0
for y in range(h):
    for x in range(w):
        draw_count = max(draw_count, distance[y][x])
print(draw_count)

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(1000000)
h, w = map(int, input().split())
field = []
for _ in range(h):
    field.append(list(input()))

dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
distance = [[-1] * w for i in range(h)]

que = deque([])
for y in range(h):
    for x in range(w):
        if field[y][x] == '.':
            continue
        que.append([y, x])
        distance[y][x] = 0

while que:
    q = que.popleft()
    for i in range(4):
        now_y = q[0] + dy[i]
        now_x = q[1] + dx[i]
        if now_y < 0 or now_y >= h or now_x < 0 or now_x >= w or field[now_y][now_x] == '#':
            continue
        if distance[now_y][now_x] != -1:
            continue
        que.append([now_y, now_x])
        distance[now_y][now_x] = distance[q[0]][q[1]] + 1

draw_count = 0
for y in range(h):
    for x in range(w):
        draw_count = max(draw_count, distance[y][x])
print(draw_count)
### BUGGY CODE ###

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
to = [False]*N
for i in range(M):
  a,b = map(int, input().split())
  edge[a-1].append(b-1)
  to[b-1] = True

import sys
sys.setrecursionlimit(10**8)

def dfs(v):
  if len(edge[v])==0:
    return 1
  ans = 0
  for u in edge[v]:
    ans = max(ans, dfs(u))
  return ans+1

ans = 0
for r in range(N):
  if to[r]==False:
    ans = max(ans, dfs(r)-1)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)

def dp(v,dpv,e):
    if dpv[v] != -1:
        return dpv[v]
    if len(e[v])==0:
        dpv[v]=0
        return 0
    res = 0
    for w in e[v]:
        res = max(dp(w,dpv,e),res)
    res += 1
    dpv[v] = res
    return res

def solve(edge):
    dpv = [-1]*N
    for i in range(N):
        dp(i,dpv,edge)
    ans = max(dpv)
    # print(dpv)
    return ans
print(solve(edge))
### BUGGY CODE ###

H,N=map(int,input().split())
A=input()
waza=0
for i in range(0,N):
    waza=waza+int(A.split()[i])
if waza>=H:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

H,N=map(int,input().split())
A=input()
list_A=A.split()
waza=0
for i in range(0,N):
    waza=waza+int(list_A[i])
if waza>=H:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

H,W=map(int,input().split())
g=[[True for j in range(W)] for i in range(H)] # 障害物がなければTrue
for i in range(H):
    S=input()
    for j in range(W):
        if S[j]=='#':
            g[i][j]=False
D=[[0 for j in range(W)] for i in range(H)]
U=[[0 for j in range(W)] for i in range(H)]
R=[[0 for j in range(W)] for i in range(H)]
L=[[0 for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        if j==0:
            L[i][j]=1 if g[i][j] else 0
        else:
            L[i][j]=L[i][j-1]+1 if g[i][j] else 0
    for j in reversed(range(W)):
        if j==W-1:
            R[i][j]=1 if g[i][j] else 0
        else:
            R[i][j]=R[i][j+1]+1 if g[i][j] else 0

for j in range(W):
    for i in range(H):
        if i==0:
            U[i][j]=1 if g[i][j] else 0
        else:
            U[i][j]=U[i-1][j]+1 if g[i][j] else 0
    for i in reversed(range(H)):
        if i==H-1:
            D[i][j]=1 if g[i][j] else 0
        else:
            D[i][j]=D[i+1][j]+1 if g[i][j] else 0

ans=0

for i in range(H):
    for j in range(W):
        if g[i][j]:
            ans=max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
            
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
s=[]
for i in range(H):
    si=[]
    Si=input()
    for j in range(W):
        si.append(Si[j]=='.')
    s.append(si)

# 左に照らした場合 行ごとに見てゆく
L=[[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if j==0 and s[i][j]:
            L[i][j]=1
        elif s[i][j]:
            L[i][j]=L[i][j-1]+1

# 右に照らした場合 行ごとに見てゆく
R=[[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in reversed(range(W)):
        if j==W-1 and s[i][j]:
            R[i][j]=1
        elif s[i][j]:
            R[i][j]=R[i][j+1]+1

# 上に照らした場合 列ごとに見てゆく
U=[[0 for j in range(W)] for i in range(H)]
for j in range(W):
    for i in range(H):
        if i==0 and s[i][j]:
            U[i][j]=1
        elif s[i][j]:
            U[i][j]=U[i-1][j]+1

# 下に照らした場合 列ごとに見てゆく
D=[[0 for j in range(W)] for i in range(H)]
for j in range(W):
    for i in reversed(range(H)):
        if i==H-1 and s[i][j]:
            D[i][j]=1
        elif s[i][j]:
            D[i][j]=D[i+1][j]+1

ans=0
for i in range(H):
    for j in range(W):
        ans=max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

print(ans)