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

def main():
    import math
    a, b, n = map(int, input().split())
    ans = 0
    
    if n > 10 ** 6:
        for x in range(n, int(math.sqrt(n)), -1):
            fx = math.floor(a * x / b) - math.floor(x / b) * a
            #print(fx)
            if ans < fx:
                ans = fx
            if ans > fx + 10 ** 3:
                #exit()
                pass
    else: 
        for x in range(n, 0, -1):
            fx = math.floor(a * x / b) - math.floor(x / b) * a
            #print(fx)
            if ans < fx:
                ans = fx
            if ans > fx + 10 ** 3:
                #exit()
                pass

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    import math
    a, b, n = map(int, input().split())
    if n >= b:
        ans = math.floor(a * (b-1)/b)
    else:
        ans = math.floor(a * n / b)
    
    print(ans)
    




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

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

from math import gcd

g = a[0]
l = 1
f = True
for i in range(n):
    x = gcd(a[i],l)
    if x!=1:
        f = False
    l = (l*a[i])//x
    g = gcd(g,a[i])

if f:
    print('pairwise coprime')
elif g==1:
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

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

from math import gcd
g = a[0]
for i in range(n):
    g = gcd(g,a[i])

if g!=1:
    print('not coprime')
    exit()

f = True
l = set()
for i in a:
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            if i in l:
                f = False
                break
            l.add(i)
        while i%j==0:
            i = i//j
        if i<2:
            break
    if i>1:
        if i in l:
            f = False
            break
        l.add(i)
        
if f:
    print('pairwise coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, n):
        self.size = n
        self.array = [0] * (n + 1)
        self.e = [0] * n

    def sum(self, i):
        s = 0
        tmp = i
        while tmp > 0:
            s += self.array[tmp]
            tmp -= tmp & -tmp
        return s

    def add(self, i, x):
        self.e[i] += x
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


def main():
    n, q = map(int, input().split())
    *C, = map(lambda x: int(x) - 1, input().split())
    P = [0] * n
    N = [0] * n
    for i in range(n)[::-1]:
        if P[C[i]]:
            N[i] = P[C[i]]
        P[C[i]] = i
    F = [0] * n
    B = BIT(n)
    for i in range(n):
        if F[C[i]] == 0:
            B.add(i, 1)
            F[C[i]] = 1
    XY = sorted([(tuple(map(int, input().split())), j) for j in range(q)])
    a = 0
    lst = [0] * q
    for (x, y), j in XY:
        for i in range(a, x - 1):
            B.add(N[i], 1)
        a = x - 1
        lst[j] = B.sum(y) - B.sum(x - 1)
    print(*lst, sep="\n")


main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, n):
        self.array = [0] * (n + 1)
        self.size = n

    def sum(self, i):
        s = 0
        tmp = i
        while tmp > 0:
            s += self.array[tmp]
            tmp -= tmp & -tmp
        return s

    def add(self, i, x):
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


def main():
    n, q = map(int, input().split())
    *C, = map(lambda x: int(x) - 1, input().split())
    P = [0] * n
    N = [None] * n
    for i in range(n)[::-1]:
        if P[C[i]]:
            N[i] = P[C[i]]
        P[C[i]] = i
    F = [0] * n
    B = BIT(n)
    for i in range(n):
        if F[C[i]] == 0:
            B.add(i, 1)
            F[C[i]] = 1
    XY = [tuple(map(int, input().split())) for j in range(q)]
    ids = list(range(q))
    ids.sort(key=lambda j: XY[j][0])
    a = 0
    lst = [0] * q
    for j in ids:
        x, y = XY[j]
        for i in range(a, x - 1):
            if N[i]:
                B.add(N[i], 1)
        a = x - 1
        lst[j] = B.sum(y) - B.sum(x - 1)
    print(*lst, sep="\n")


main()
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

n, x, y = map(int, input().split())
ma = [[0]*n for _ in range(n)]
for i in range(n-1):
    ma[i][i+1] = 1
    ma[i+1][i] = 1

ma[x-1][y-1] = 1
ma[y-1][x-1] = 1
a = csr_matrix(ma)
b = dijkstra(a, directed=False).astype(int)
ans = [0]*(n-1)
for i in range(n):
  l = b[i]
  for num in l:
    if int(num) != 0:
    	ans[int(num)-1] += 1

for i in ans:
  print(i//2)

### FIXED CODE ###

n, x, y = map(int, input().split())
ans = [0 for _ in range(n)]
for i in range(1, n+1):
    for j in range(i+1, n+1):
        ans[min(j-i, abs(i-x)+abs(j-y)+1)] += 1


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

from math import *
def fa(n):
    l = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            l.append([i, cnt])

    if temp != 1:
        l.append([temp, 1])

    if l == []:
        l.append([n, 1])

    return l
s = int(input())
l = fa(s + 1)
print(0, 0, l[0][0], 1, 1, ceil(s / l[0][0]))

### FIXED CODE ###

from math import ceil
s = int(input())
print(0, 0, 10 ** 9, 1, abs(s - ((10 ** 9) * ceil(s / 10 ** 9))), ceil(s / 10 ** 9))
### BUGGY CODE ###

import numpy as np
from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
#s = np.array(s)
#s = (s == ".") * 1
def neext(a):
    l, m = a[0], a[1]
    return [(l, m+1), (l, m-1), (l+1, m), (l-1, m)]
def solve(i, j):
    if s[i][j] == '#':
        return 0
    else:
        pre = 0
        p = np.full((h, w), -1)
        check = deque([((i, j), 0)])#(from,now, dist)
        while check:
            now, d = check.popleft()
            p[now[0]][now[1]] = d
            pre = max(pre, d)
            for b, c in neext((now[0], now[1])):
                if b < 0 or c < 0 or b >= h or c >= w:
                    continue 
                if p[b][c] != -1 or s[b][c] == '#':
                    continue
                else:
                    check.append(((b, c), d + 1))
        return pre
ans = 0
for H in range(len(s)):
    for W in range(len(s[0])):
        ans = max(ans, solve(H, W))
print(ans)

### FIXED CODE ###

import numpy as np
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = 0
for i in range(len(s)):
    for j in range(len(s[0])):
        if s[i][j] == '#':
            continue
        pre = 0
        p = np.full((h, w), -1)
        p[i][j] = 0
        check = deque([((i, j), 0)])#(from,now, dist)
        while check:
            now, d = check.popleft()
            pre = max(pre, d)
            for k, l in [(1,0), (-1,0),(0,1), (0,-1)]:
                b = now[0] + k
                c = now[1] + l
                if b < 0 or c < 0 or b >= h or c >= w:
                    continue 
                elif p[b][c] == -1 and s[b][c] != '#':
                    check.append(((b, c), d + 1))
                    p[b][c] = d + 1
        ans = max(ans, pre)

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

N = int(input())
S = input()
ans = float("INF")

for i in range(N+1):
    left = S[0:i]
    right = S[i::]
    cnt_left = left.count("#")
    cnt_right = right.count(".")
    change_stone = cnt_left + cnt_right
    ans = min(ans, change_stone)
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
left = 0
right = S.count(".")
ans = left + right

for c in S:
    if c == "#":
        left += 1
    else:
        right -= 1
    ans = min(ans, left + right)

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

import sys


def main():
    input = sys.stdin.readline

    h, w, k = map(int, input().split())
    s = [input() for _ in range(h)]

    cs = [[0] * (w + 1) for _ in range(h + 1)]
    for i in range(h):
        for j in range(w):
            cs[i +
               1][j +
                  1] = cs[i][j + 1] + cs[i + 1][j] - cs[i][j] + int(s[i][j])

    # print(*cs, sep='\n')
    # print()

    ans = h + w
    for bit in range(1 << (h - 1)):
        border = [0]
        cand = 0
        for i in range(h):
            if (bit >> i) & 1:
                border.append(i + 1)
                cand += 1
        border.append(h)
        if cand >= ans:
            continue
        j0 = 0
        j = 1
        while j <= w:
            # for j in range(1, w + 1):
            for i, bi in enumerate(border[:-1]):
                # print(
                #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
                #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
                if cs[border[i + 1]][j] - cs[border[
                        i + 1]][j0] - cs[bi][j] + cs[bi][j0] > k:
                    cand += 1
                    j0 = j - 1
                    j -= 1
                    # print(border[i + 1], j, cs[border[i + 1]][j])
                    break
            j += 1

        # print(border, cand0, cand, cut)
        ans = min(ans, cand)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def main():
    input = sys.stdin.readline

    h, w, k = map(int, input().split())
    s = [input() for _ in range(h)]

    cs = [[0] * (w + 1) for _ in range(h + 1)]
    for i in range(h):
        for j in range(w):
            cs[i +
               1][j +
                  1] = cs[i][j + 1] + cs[i + 1][j] - cs[i][j] + int(s[i][j])

    # print(*cs, sep='\n')
    # print()

    ans = h + w
    for bit in range(1 << (h - 1)):
        border = [0]
        cand = 0
        for i in range(h):
            if (bit >> i) & 1:
                border.append(i + 1)
                cand += 1
        border.append(h)
        if cand >= ans:
            continue
        j0 = 0
        j = 1
        while j <= w:
            # for j in range(1, w + 1):
            for i, bi in enumerate(border[:-1]):
                # print(
                #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
                #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
                if cs[border[i + 1]][j] - cs[border[
                        i + 1]][j0] - cs[bi][j] + cs[bi][j0] > k:
                    cand += 1
                    j0 = j - 1
                    j -= 1
                    # print(border[i + 1], j, cs[border[i + 1]][j])
                    break
            j += 1
            if cand >= ans:
                break

        # print(border, cand0, cand, cut)
        ans = min(ans, cand)
    print(ans)


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

import sys
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())

def dijkstra(s,n,g):
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def warshall_floyd(d,n):
    for i in range(n):
        d[i][i] = 0
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

def main():
    n,w,l = inpm()
    g = [[] for _ in range(n)]
    for _ in range(w):
        x,y,z = inpm()
        x -= 1
        y -= 1
        if z > l:
            continue
        g[x].append((y,z))
        g[y].append((x,z))
    q = inp()
    st = []
    for _ in range(q):
        s,t = inpm()
        s -= 1
        t -= 1
        st.append((s,t))
    d = [[] for _ in range(n)]
    for i in range(n):
        d[i] = dijkstra(i,n,g)
    G = [[10**15 for _ in range(n)] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            if d[i][j] <= l:
                G[i][j] = 1
                G[j][i] = 1
    D = warshall_floyd(G,n)
    for i in range(q):
        [s,t] = st[i]
        ans = D[s][t]
        if ans == 10**15:
            print(-1)
            continue
        print(ans-1)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from heapq import heappop, heappush
from scipy.sparse.csgraph import floyd_warshall
input = sys.stdin.readline
 
def main():
    n,w,l = map(int,input().split())
    d = [[10**15 for _ in range(n)] for _ in range(n)]
    for _ in range(w):
        x,y,z = map(int,input().split())
        x -= 1
        y -= 1
        if z > l:
            continue
        d[x][y] = z
        d[y][x] = z
    for i in range(n):
        d[i][i] = 0
    d = floyd_warshall(d)
    G = [[10**15 for _ in range(n)] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            if d[i][j] <= l:
                G[i][j] = 1
                G[j][i] = 1
    for i in range(n):
        G[i][i] = 0
    G = floyd_warshall(G)
    q = int(input())
    for _ in range(q):
        s,t = map(int,input().split())
        s -= 1
        t -= 1
        ans = G[s][t]
        if ans == 10**15:
            print(-1)
            continue
        print(int(ans)-1)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

INF = 2**30
n = int(input())
P = list(map(int, input().split()))
T = [[] for _ in range(n)]
for i, p in enumerate(P, 1):
  T[p-1].append(i)
X = list(map(int, input().split()))
def dfs(v):
  l = len(T[v])
  x = X[v]
  dp = np.full(x+1, INF, dtype=np.int64)
  dp[0] = 0
  for i, nv in enumerate(T[v]):
    k = np.full(x+1, INF, dtype=np.int64)
    if x+1 >= X[nv]:
      np.minimum(k[X[nv]:], dp[:x+1-X[nv]]+dfs(nv), out=k[X[nv]:])
    if x+1 >= dfs(nv):
      np.minimum(k[dfs(nv):], dp[:x+1-dfs(nv)]+X[nv], out=k[dfs(nv):])
    dp = k.copy()
  res = dp.min()
  return res
ans = dfs(0)
if ans == INF:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

### FIXED CODE ###

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

n = int(input())
P = list(map(int, input().split()))
T = [[] for _ in range(n)]
for i, p in enumerate(P, 1):
  T[p-1].append(i)
X = list(map(int, input().split()))
D = [[-1]*n for _ in range(2)]
def dfs(color, v):
  if D[color][v] != -1:
    return D[color][v]
  l = len(T[v])
  x = X[v]
  dp = [[float("inf")]*(x+1) for _ in range(l+1)]
  dp[0][0] = 0
  for i, nv in enumerate(T[v]):
    for j in range(x+1):
      if j >= X[nv]:
        dp[i+1][j] = min(dp[i+1][j], dp[i][j-X[nv]]+dfs(color, nv))
      if j >= dfs(color^1, nv):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j-dfs(color^1, nv)]+X[nv])
  res = min(dp[l])
  D[color][v] = res
  return res
ans = dfs(0, 0)
if ans == float("inf"):
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")
### BUGGY CODE ###

# 素数列挙 (エラトステネスの篩)
def primes_create(n):
    p = [True]*(n+1)
    p[0] = p[1] = False
    i = 2
    while i*i <= n:
        if p[i]:
            for j in range(i<<1, n+1, i): p[j] = False
        i += 1
    return p

P = primes_create(3163)
P_list = []
for i in range(len(P)):
    if P[i]: P_list.append(i)

# 素数と個数を求める
def factorize(n):
    res = []
    if n < 2: return res
    for i in range(2, n):
        if i*i > n: break
        if n%i: continue
        c = 0
        while n%i == 0: n //= i; c += 1
        res += [[i, c]]
    if n != 1: res += [[n, 1]]
    return res

def factorize_2(n):
    res = []
    if n < 2: return res
    for i in P_list:
        if i*i > n: break
        if n%i: continue
        c = 0
        while n%i == 0: n //= i; c += 1
        res += [[i, c]]
    if n != 1: res += [[n, 1]]
    return res

n = int(input())

s = 0
for i in range(1, n+1):
    cc = 1
    for p,c in factorize_2(i):
        cc *= (c + 1)
    s += i * cc
print(s)


### FIXED CODE ###

n = int(input())
s = 0
for m in range(1, n+1):
    k = n // m
    s += k * (k+1) * m // 2
print(s)
### BUGGY CODE ###

n,m=map(int,input().split())
lr=[list(map(int,input().split())) for _ in range(m)]
card=[0]*n

for i in range(m):
    l,r=lr[i]
    for j in range(l-1,r):
        card[j]+=1
print(card.count(m))

### FIXED CODE ###

n,m=map(int,input().split())
l=1
r=n
for i in range(m):
    ll,rr = map(int,input().split())
    l=max(l,ll)
    r=min(r,rr)
if l<=r:
    print(r-l+1)
else:
    print(0)
### BUGGY CODE ###

n,k=map(int,input().split())
a=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x: x[1])
type=set([a[i][0] for i in range(k)])
dsum=sum([x[1] for x in a[:k]])
tnum=dict()
for i in [x[0] for x in a[:k]]:
    if i not in tnum.keys():
        tnum[i]=1
    else:tnum[i]+=1
ans=dsum+len(type)**2
sushi=a[-(n-k+1)::-1]
for i in a[k:]:
    if i[0] not in type:
        type.add(i[0])
        for x in sushi[:]:
            if tnum[x[0]]>1:
                tnum[x[0]]-=1
                dsum=dsum+i[1]-x[1]
                ans=max(ans,dsum+len(type)**2)
                break
            sushi.remove(x)
print(ans)




### FIXED CODE ###

n, k = map(int, input().split())
td = sorted([list(map(int, input().split())) for i in range(n)], reverse=True, key=lambda x: x[1])

type = set()
L = []
Sum = 0
for x in td[:k]:
    Sum += x[1]
    if x[0] not in type:
        type.add(x[0])
    else:
        L.append(x[1])

L = L[::-1]
type_cnt = len(type)
ans = Sum + type_cnt ** 2
for x in td[k:]:
    if len(L)==0:break
    if x[0] not in type:
        type.add(x[0])
        type_cnt += 1
        Sum = Sum - L.pop(0) + x[1]
        ans = max(ans, Sum + type_cnt ** 2)
print(ans)
### BUGGY CODE ###

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

for i in range(M):
    A.sort()
    A[-1] = A[-1]//2

print(sum(A))

### FIXED CODE ###

from heapq import heapify, heappush, heappop

N, M = map(int, input().split())
A = list(map(lambda x:int(x)*(-1), input().split()))
heapify(A)

for i in range(M):
    heappush(A, (-1*heappop(A))//2*-1)

print(-sum(A))
### BUGGY CODE ###

n,y=map(int,input().split())
flag=False
if 10000*n<y:
    print('-1 -1 -1')
elif 10000*n==y:
    print(str(n)+' 0 0')
else:
    for i in range(n+1):
        if flag:
            break
        for j in range(n-i+1):
            if flag:
                break
            for k in range(n-i-j+1):
                if 10000*i+5000*j+1000*k==y and i+j+k==n:
                    print(str(i)+' '+str(j)+' '+str(k))
                    flag=True
                    break
    if flag==False:
        print('-1 -1 -1')


### FIXED CODE ###

n,y=map(int,input().split())
flag=False
if 10000*n<y:
    print('-1 -1 -1')
elif 10000*n==y:
    print(n,0,0)
else:
    for i in range(n+1):
        if flag:
            break
        for j in range(n-i+1):
            if 10000*i+5000*j+1000*(n-i-j)==y:
                print(i,j,n-i-j)
                flag=True
                break
    else:
        print('-1 -1 -1')
### BUGGY CODE ###

n = int(input())
l = [int(_) for _ in input().split()]
ans = 0
L = [0 for _ in range(1,2000+1)]
s = [0 for _ in range(0,2000+1)]
for k in range(0, n):
    L[l[k]-1] += 1
for x in range(0,2000):
    s[x+1] = s[x] + L[x]

for i in range(0, n-1):
    for j in range(i+1, n):
        exc = 0
        m = abs(l[i] - l[j])
        M = l[i] + l[j]
        if l[i] > m:
            exc += 1
        if l[j] > m:
            exc += 1
        ans += s[M] - s[m] - L[M-1] - exc
print(ans//3)



### FIXED CODE ###

n = int(input())
l = [int(_) for _ in input().split()]
ans = 0
L = [0 for _ in range(1,2000+2)]
s = [0 for _ in range(0,2000+2)]
for k in range(0, n):
    L[l[k]-1] += 1
for x in range(0,2001):
    s[x+1] = s[x] + L[x]
 
for i in range(0, n-1):
    for j in range(i+1, n):
        exc = 0
        m = abs(l[i] - l[j])
        M = l[i] + l[j]
        if l[i] > m:
            exc += 1
        if l[j] > m:
            exc += 1
        ans += s[M] - s[m] - L[M-1] - exc
print(ans//3)
### BUGGY CODE ###

n = int(input());
a = input().split(" ");
b = input().split(" ");
c = input().split(" ");
num_b = [0]*n;
for i in range(n) :
	for j in range(n) :
		if int(b[i]) < int(c[j]) :
			num_b[i] += 1;
ans = 0;
for i in range(n) :
	for j in range(n) :
		if int(a[i]) < int(b[j]) :
			ans += num_b[j]
print(ans);

### FIXED CODE ###

import bisect

n = int(input());
a = input().split(" ");
b = input().split(" ");
c = input().split(" ");
num_b = [0]*n;
for i in range(n) :
	a[i] = int(a[i]);
	b[i] = int(b[i]);
	c[i] = int(c[i]);
a.sort();
b.sort();
c.sort();
num_b = [0]*(n+1);
for i in range(n) :
	num_b[n-1-i] = n - bisect.bisect_right(c,b[n-1-i]) + num_b[n-i];
ans = 0;
for i in range(n) :
	ans += num_b[bisect.bisect_right(b,a[i])];
print(ans);
### BUGGY CODE ###

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


for i in range(N):
    x *= A[i]
if x <= 10**18:
    print(x)
else:
    print("-1")

### FIXED CODE ###

N = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 1
rec = True
for i in range(N):
    ans = ans * l[i]
    if ans > 10**18:
        rec = False
        break

if rec:
    print(ans)
else:
    print('-1')
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 9)

H, W = map(int, input().split())
lst = [['#'] * (W+2)]
lst += [['#'] + list(input()) + ['#'] for i in range(H)]
lst += [['#'] * (W+2)]


lst_ue = [[-1] * (W+2) for i in range(H+2)]
lst_shita = [[-1] * (W+2) for i in range(H+2)]
lst_migi = [[-1] * (W+2) for i in range(H+2)]
lst_hidari = [[-1] * (W+2) for i in range(H+2)]

# print (lst_ue)
def ue(i, j):
    if lst_ue[i][j] != -1:
        return lst_ue[i][j]
    if lst[i][j] == '#':
        lst_ue[i][j] = 0
        return 0
    else:
        lst_ue[i][j] = ue(i-1, j) + 1
        return lst_ue[i][j]


def shita(i, j):
    if lst_shita[i][j] != -1:
        return lst_shita[i][j]
    if lst[i][j] == '#':
        lst_shita[i][j] = 0
        return 0
    else:
        lst_shita[i][j] = shita(i+1, j) + 1
        return lst_shita[i][j]        


def hidari(i, j):
    if lst_hidari[i][j] != -1:
        return lst_hidari[i][j]
    if lst[i][j] == '#':
        lst_hidari[i][j] = 0
        return 0
    else:
        lst_hidari[i][j] = hidari(i, j-1) + 1
        return lst_hidari[i][j]        

def migi(i, j):
    if lst_migi[i][j] != -1:
        return lst_migi[i][j]
    if lst[i][j] == '#':
        lst_migi[i][j] = 0
        return 0
    else:
        lst_migi[i][j] = migi(i, j+1) + 1
        return lst_migi[i][j]        

ans = 0
for i in range(1,H+1):
    for j in range(1, W+1):
        if lst[i][j] != '#':
            ans = max(ans, ue(i,j)+shita(i,j)+hidari(i,j)+migi(i,j)-3)
            if ans == H + W -1:
                print (ans)
                sys.exit()
# else:
#     for i in range(750,1250):
#         for j in range(750, 1250):
#             if lst[i][j] != '#':
#                 ans = max(ans, ue(i,j)+shita(i,j)+hidari(i,j)+migi(i,j)-3)
#                 if ans == H+W-1:
#                     print (ans)
#                     sys.exit()

print (ans)


### FIXED CODE ###

#上下方向の探索と左右方向の探索をまとめる
#まず表を完成させる-->全マスの探索
H, W = map(int, input().split())
lst = [['#'] * (W+2)]
lst += [['#'] + list(input()) + ['#'] for i in range(H)]
lst += [['#'] * (W+2)]


lst_ue = [[0] * (W+2) for i in range(H+2)]
lst_shita = [[0] * (W+2) for i in range(H+2)]
lst_migi = [[0] * (W+2) for i in range(H+2)]
lst_hidari = [[0] * (W+2) for i in range(H+2)]

for i in range(1, H+1):
    for j in range(1, W+1):
        lst_hidari[i][j] = 0 if lst[i][j] == '#' else 1 + lst_hidari[i][j-1]
    for j in range(W, 0, -1):
        lst_migi[i][j] = 0 if lst[i][j] == '#' else 1 + lst_migi[i][j+1]

for j in range(1, W+1):
    for i in range(1, H+1):
        lst_ue[i][j] = 0 if lst[i][j] == '#' else 1 + lst_ue[i-1][j]
    for i in range(H+1, 0, -1):
        lst_shita[i][j] = 0 if lst[i][j] == '#' else 1 + lst_shita[i+1][j]

ans = 0
for i in range(1,H+1):
    for j in range(1, W+1):
        ans = max(ans, lst_ue[i][j]+lst_shita[i][j]+lst_migi[i][j]+lst_hidari[i][j]-3)

print (ans)