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

import sys
input=sys.stdin.readline
n, m = map(int, input().split())
A = [0] * m
B = [0] * m
C = [[] for _ in range(m)]
for i in range(m):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b
    c = list(map(int, input().split()))
    C[i] = c
D = [0] * m
for i in range(m):
    d = 0
    for j in C[i]:
        d |= 1 << (j - 1)
    D[i] = d
# dp[i][s], i番目までの鍵を使ってSを作る最小コスト
infi = 10 ** 20
dp = [[infi for i in range(2 ** n + 1)] for _ in range(m + 1)]
dp[0][0] = 0
for i in range(m):
    for s in range(2 ** n):
        ni = i + 1
        ns = s
        # 使わないとき
        dp[ni][ns] = min(dp[i][s], dp[ni][ns])
        # 使うとき
        ns = s | D[i]
        dp[ni][ns] = min(dp[ni][ns], dp[i][s] + A[i])
ans = dp[m][2 ** n - 1]
print(ans if ans < infi else -1)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n, m = map(int, input().split())
A = [0] * m
B = [0] * m
C = [[] for _ in range(m)]
for i in range(m):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b
    c = list(map(int, input().split()))
    C[i] = c
D = [0] * m
for i in range(m):
    d = 0
    for j in C[i]:
        d |= 1 << (j - 1)
    D[i] = d
# dp[i][s], i番目までの鍵を使ってSを作る最小コスト
infi = 10 ** 20
dp = [[infi for i in range(2 ** n + 1)] for _ in range(m + 1)]
dp[0][0] = 0
for i in range(m):
    for s in range(2 ** n):
        ni = i + 1
        ns = s
        # 使わないとき
        dp[ni][ns] = min(dp[i][s], dp[ni][ns])
        # 使うとき
        ns = s | D[i]
        dp[ni][ns] = min(dp[ni][ns], dp[i][s] + A[i])
ans = dp[m][2 ** n - 1]
print(ans if ans < infi else -1)
### BUGGY CODE ###

import math
def main():

    N = int(input())

    d = [2 for _ in range(N+1)]
    d[1] = 1

    # for i in range(2, N//2+1):
    #     for j in range(i+i, N+1, i):
    #         d[j] += 1

    v = int(math.sqrt(N))
    for i in range(2, v+1):
        for j in range(i+i, N+1, i):
            d[j] += 1
            if j//i > v: d[j] += 1

    ans = 0
    for i in range(1, N+1):
        ans += i * d[i]
    return ans

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

### FIXED CODE ###

import math
import collections
def main():

    N = int(input())
    d = dict()
    for i in range(1, N+1):
        d[i] = 0

    ans = 0
    for i in range(1, N+1):
        p = N//i
        ans += p * (p+1)//2 * i
    return ans

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

# https://atcoder.jp/contests/dp/tasks/dp_g
import sys
sys.setrecursionlimit(10**7)


class DAG:
    def __init__(self, n):
        # n: num of vertices
        self.n = n
        self.adj = [[] for _ in range(n)]

    def addEdge(self, parent, child):
        self.adj[parent].append(child)

    def dfs(self, node):
        ans = 0
        for child in self.adj[node]:
            ans = max(ans, 1 + self.dfs(child))
        return ans

    def dfsWithDp(self, node, dp, visited):
        if(visited[node]):
            return dp[node]
        visited[node] = True
        for child in self.adj[node]:
            if not visited[child]:
                self.dfsWithDp(child, dp, visited)
            dp[node] = max(dp[node], 1 + self.dfsWithDp(child, dp, visited))
        return dp[node]

    # o(n^2) solution
    def findLongestPathNaive(self):
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfs(i))
        return ans

    # O(n) solution
    def findLongestPathWithDp(self):
        visited = [False] * self.n
        dp = [0] * self.n  # dp[i] := longest path starting from vertex i
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfsWithDp(i, dp, visited))
        return ans


def main():
    N, M = map(int, input().split())
    dag = DAG(N)
    for _ in range(M):
        parent, child = map(lambda i: int(i) - 1, input().split())
        dag.addEdge(parent, child)
    # print(dag.findLongestPathWithDp())
    print(dag.findLongestPathNaive())


main()


### FIXED CODE ###

# https://atcoder.jp/contests/dp/tasks/dp_g
import sys
sys.setrecursionlimit(10**7)


class DAG:
    def __init__(self, n):
        # n: num of vertices
        self.n = n
        self.adj = [[] for _ in range(n)]

    def addEdge(self, parent, child):
        self.adj[parent].append(child)

    def dfsWithDp(self, node, dp, visited):
        if(visited[node]):
            return dp[node]
        visited[node] = True
        for child in self.adj[node]:
            if not visited[child]:
                self.dfsWithDp(child, dp, visited)
            dp[node] = max(dp[node], 1 + self.dfsWithDp(child, dp, visited))
        return dp[node]

    def findLongestPathWithDp(self):
        visited = [False] * self.n
        dp = [0] * self.n  # dp[i] := longest path starting from vertex i
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfsWithDp(i, dp, visited))
        return ans


def main():
    N, M = map(int, input().split())
    dag = DAG(N)
    for _ in range(M):
        parent, child = map(lambda i: int(i) - 1, input().split())
        dag.addEdge(parent, child)
    print(dag.findLongestPathWithDp())


main()
### BUGGY CODE ###

from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
      #queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()#queueに入っていたものを消す。
        if [y, x] == [gy, gx]:#もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
          p = 0
          for l in range(1, K + 1):
            if p == 0:
              new_y, new_x = y + j * l, x + k * l #改行して条件文を続けるときにバックスラッシュ
              if (0 <= new_y < H) and (0 <= new_x < W): 
                if maze[new_y][new_x] == "@":
                  p = 1
                else:
                  if visited[new_y][new_x] == -1:#まだ来たことない点だったという条件
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])#新しい点を足す。


H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
C = [0] * H
for i in range(H):
  C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
#print(visited)
print(visited[x2][y2])
  




### FIXED CODE ###

from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
      #queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()#queueに入っていたものを消す。
        if [y, x] == [gy, gx]:#もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
          p = 0
          l = 1
          while p == 0:
              new_y, new_x = y + j * l, x + k * l 
              if (0 <= new_y < H) and (0 <= new_x < W): 
                if maze[new_y][new_x] == "@":
                  p = 1
                elif visited[new_y][new_x] == -1:#まだ来たことない点だったという条件
                  visited[new_y][new_x] = visited[y][x] + 1
                  queue.append([new_y, new_x])#新しい点を足す。
                elif visited[new_y][new_x] < visited[y][x] + 1:
                  p = 1
              else:
                p = 1
              l += 1
              if l == K + 1:
                p = 1

H, W, K = map(int, input().split())
#K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
C = [0] * H
for i in range(H):
  C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
#print(visited)
print(visited[x2][y2])
### BUGGY CODE ###

N =int(input())
x = list(map(int, input().split()))
count=0
for i in range(N):
    if x[i]==min(x[0:i+1]):
        count=count+1
print(count)

### FIXED CODE ###

N = int(input())
x = list(map(int, input().split()))
count=0
min=2000000
for i in range(N):
    if min>=x[i]:
        count=count+1
        min=x[i]
print(count)
### BUGGY CODE ###

import collections

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

for i in range(len(a)):
    t = a[:i] + a[i+1:]
    ans = 0
    c = collections.Counter(t)
    for j in c.values():
        ans += j * (j-1) // 2

    print(ans)


### FIXED CODE ###

import collections

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

mx = 0

for item, value in c.items():
    mx += value * (value-1) // 2

for i in range(len(a)):
    ans = mx

    t = c[a[i]]
    ans -= t * (t-1) //2
    ans += (t-1)*(t-2) //2
    print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
route=[]
cur=0
while 1:
    if cur in route:
        print(-1)
        break
    if cur==1:
        print(len(route))
        break
    route.append(cur)
    cur = a[cur]-1


### FIXED CODE ###

n=int(input())
a=[int(input())-1 for i in range(n)]
cur=0
i=0
while 1:
    if cur==1:
        print(i)
        break
    if i>=n:
        print(-1)
        break
    i+=1
    cur=a[cur]
### BUGGY CODE ###

def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    if 10%p == 0:
        ss = map(int, s)
        ss = list(ss)
        for i in range(n):
            if ss[i]%p == 0:
                ans += i+1
        print(ans)
        return
    sr = s[::-1]
    ssr = map(int, sr)
    tens = 1
    v = 0
    for i, si in enumerate(ssr):
        v = (v + (si%p)*tens)%p
        mu[i] = v
        c[v] += 1
        tens *= 10
    c[0] += 1
    for i in c:
        if i:
            ans += ((i-1)*i)//2
        
    print(ans)
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    if 10%p == 0:
        ss = map(int, s)
        ss = list(ss)
        for i in range(n):
            if ss[i]%p == 0:
                ans += i+1
        print(ans)
        return
    sr = s[::-1]
    ssr = map(int, sr)
    tens = 1
    v = 0
    for i, si in enumerate(ssr):
        v = (v + (si%p)*tens)%p
        mu[i] = v
        c[v] += 1
        tens *= 10
        tens %= p
    c[0] += 1
    for i in c:
        if i:
            ans += ((i-1)*i)//2
        
    print(ans)
    

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

N=int(input())
H=list(map(int,input().split()))
c=0

def till(M):
	d=max(H[k] for k in range(M))
	return d

for i in range(2,N):
	if till(i-1)-H[i]>=2:
		c=c+1
if c>=1:
	print('No')
else:
	print('Yes')

### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))
c=0
d=H[0]

for i in range(N):
	if d<=H[i]:
		d=H[i]
	else:
		if d-H[i]>=2:
			c=c+1
if c>=1:
	print('No')
else:
	print('Yes')
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()
    RGB = ('R', 'G', 'B')
    ans = 0
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            if S[i] != S[j]:
                cnt = S[j + 1:].count(RGB[3 - RGB.index(S[i]) - RGB.index(S[j])])
                if 2 * j - i < N:
                    if S[2 * j - i] == RGB[3 - RGB.index(S[i]) - RGB.index(S[j])]:
                        cnt -= 1
                ans += cnt
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import collections


def main():
    N = int(input())
    S = input()
    RGB = ('R', 'G', 'B')
    cnt = collections.Counter(S)
    ans = cnt['R'] * cnt['G'] * cnt['B']

    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            if S[i] != S[j]:
                if 2 * j - i < N:
                    if S[2 * j - i] == RGB[3 - RGB.index(S[i]) - RGB.index(S[j])]:
                        ans -= 1

    print(ans)


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

N, M = map(int,input().split())
side = [[]for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    side[a-1].append([b-1,c])
node = [-float('inf')]*N
node[0] = 0
queue = [0]
nque = []
for i in range(N+5):
    while queue:
        q = queue.pop(-1)
        for a,c in side[q]:
            if node[a] < node[q]+c:
                node[a] = node[q]+c
                nque.append(a)
    queue = nque[:]
    nque = []

while queue:
    q = queue.pop(-1)
    for a,c in side[q]:
        if node[a] < node[q]+c:
            node[a] = float('inf')
            queue.append(a)

print(node[-1])

### FIXED CODE ###

N,M = map(int,input().split())
gra = [[]for i in range(N)]
p = [[0]+[-float("inf")]*(N-1) for i in range(N*2+1)]
p[0][0] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    gra[a-1].append([b-1,c])
for i in range(N*2):
    for j in range(N):
        for b,c in gra[j]:
            p[i+1][b] = max(p[i+1][b],p[i][j]+c,p[i][b])
print(["inf",p[N][-1]][p[N][-1] == p[-1][-1]])
### BUGGY CODE ###

# https://ikatakos.com/pot/programming_algorithm/dynamic_programming/inversion から
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

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

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
from itertools import accumulate

def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

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

def tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += bit.sum(p)
        bit.add(p, 1)
        #print(p, ans)
    #print(xs, ans)
    return ans

def f(x):
    Bs = list(map(lambda a: 1 if a>=x else -1, As))
    xs = Bs[:]
    Bs = [0] + list(accumulate(Bs))
    mn = min(Bs)
    Bs = list(map(lambda x : x + max(0, -mn) + 1, Bs))
    #print(x, As, xs, Bs)
    return -tento(list(Bs))

M = (N*(N+1))//2
print(bsearch((-M//2) , min(As), max(As), f))


### FIXED CODE ###

# https://ikatakos.com/pot/programming_algorithm/dynamic_programming/inversion から
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

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

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
from itertools import accumulate

def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if max_i - min_i <= 1:
            return min_i
        if func(index) <= target:
            index, min_i = (index + max_i)//2, index
            continue
        index, max_i = (index + min_i)//2, index

N, = map(int, input().split())
As = list(map(int, input().split()))
mna, mxa = min(As), max(As)

def tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += bit.sum(p)
        bit.add(p, 1)
        #print(p, ans)
    #print(xs, ans)
    return ans

def f(x):
    Bs = [0] + list(accumulate(map(lambda a: 1 if a>=x else -1, As)))
    mn = min(Bs)
    Bs = list(map(lambda x : x - mn + 1, Bs))
    return -tento(Bs)

M = (N*(N+1))//2
print(bsearch((-M//2) , mna, mxa, f))
### BUGGY CODE ###

n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
ikeruheya = [[] for i in range(n)]
ans = [0]*(n+1)
check = [0]*n
check[0]=1
for i in range(m):
    ikeruheya[a[i][0]-1].append(a[i][1])
    ikeruheya[a[i][1]-1].append(a[i][0])

    
next=[1]
count = 1
while len(next) != 0 and count <= n:
    imaheya = next.pop(0)
    for j in range(len(ikeruheya[imaheya-1])):
        
        if check[ikeruheya[imaheya-1][j]-1]==0:
            ans[ikeruheya[imaheya-1][j]]= imaheya 
            check[ikeruheya[imaheya-1][j]-1] = 1
            next.append(ikeruheya[imaheya-1][j])
            count += 1
            
print("Yes")
for i in range(2, n+1):
    print(ans[i])


    
    


### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
a=[list(map(int, input().split())) for i in range(m)]
b=[[] for j in range(n)] 

michi=[-1]*(n)
michi[0]=0
heya=[]


for i in range(m):
    b[a[i][0]-1].append(a[i][1])
    b[a[i][1]-1].append(a[i][0])



heya.append(1)


while len(heya):
    now=heya.pop(0)-1
    
    for i in range(len(b[now])):
        if michi[b[now][i]-1] == -1:
            heya.append(b[now][i])
            michi[b[now][i]-1] = now+1
print("Yes")
for i in range(1,n):
    print(michi[i])
### BUGGY CODE ###

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

ans = 0

for i in range(n):
    j = 0
    for a in A[i+A[i]:]:
        if a == j:
            ans += 1
        j += 1

print(ans)


### FIXED CODE ###

import collections

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

L, R = [], []

for i in range(n):
    L.append(i+1+A[i])
    R.append(i+1-A[i])

cl = collections.Counter(L)
cr = collections.Counter(R)

ans = 0

for c in cl:
    ans += cl[c] * cr[c]

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

n = int(input())
a = []
for i in range(n):
    b = int(input())
    if b in a:
        a.remove(b)
    else:
        a.append(b)

print(len(a))

### FIXED CODE ###

import collections
n = int(input())
l = list(input() for i in range(n))
a = collections.Counter(l)
a = list(a.values())
p = 0
for i in range(len(a)):
    if a[i] % 2 != 0:
        p += 1
print(p)
### BUGGY CODE ###

def findmax(ma, a,b):
	ma = a.index(max(a))
	if b[ma] > 0:
		b[ma] -= 1
		return ma,a,b
	else:
		a.pop(ma)
		b.pop(ma)
		return findmax(ma, a, b)

init = input().split(' ')
init = [int(i) for i in init]
n,m= init[0],init[1]

a = []
b = []

try:
	while True:
		inp1 = input().split(' ')
		inp1 = [int(i) for i in inp1]
		a.append(inp1[0])
		b.append(inp1[1])
except:
	pass

ma = a.index(max(a))
total = sum([a[j]*b[j] for j in range(n)])
deltarget = sum(b) - m

while deltarget > 0:
	ma, a, b = findmax(ma, a, b)
	total -= a[ma]
	deltarget -= 1
	
print(total)

### FIXED CODE ###

init = input().split(' ')
init = [int(i) for i in init]
n,m= init[0],init[1]

ab = []

try:
	while True:
		inp1 = input().split(' ')
		inp1 = [int(i) for i in inp1]
		ab.append([inp1[0],inp1[1]])
except:
	pass

ab.sort()
total = sum([ab[j][0]*ab[j][1] for j in range(n)])
deltarget = sum([ab[j][1] for j in range(n)]) - m

while deltarget > 0:
	if deltarget - ab[len(ab)-1][1] > 0:
		total -= ab[len(ab)-1][0]*ab[len(ab)-1][1]
		deltarget -= ab[len(ab)-1][1]
		ab.pop(len(ab)-1)
	else:
		total -= ab[len(ab)-1][0]*deltarget
		break

print(total)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)

cnt = 0
for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        for k in range(j+1, N):
            c = L[k]
            if b > c and a < b+c:
                cnt += 1
print(cnt)

### FIXED CODE ###

from numba import njit
N = int(input())
L = list(map(int, input().split()))
L.sort()

@njit
def solve(L):
    cnt = 0
    for i in range(N-2):
        a = L[i]
        for j in range(i+1, N-1):
            b = L[j]
            for k in range(j+1, N):
                cnt += a+b > L[k]
    return cnt
print(solve(L))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Spyderエディタ

これは一時的なスクリプトファイルです
"""

n = int(input())

kList = []
for _ in range(n):
    keihin = input()
    if kList:
        if keihin not in kList:
            kList.append(keihin)
    else:
        kList.append(keihin)

print(len(kList))

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Spyderエディタ

これは一時的なスクリプトファイルです
"""

n = int(input())

kList = []
for _ in range(n):
    kList.append(input())  
    
print(len(set(kList)))
### BUGGY CODE ###

import math

k=int(input())
ans=[]
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans.append(math.gcd(math.gcd(i,j),l))
print(sum(ans))

### FIXED CODE ###

from math import gcd

k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans+=(gcd(i,gcd(j,l)))
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
s, ans = [], 0
dpr, dpl, dpd, dpu = {},{},{},{}
for i in range(H):
    s.append(input())

def getCount(h, w):
    if s[h][w] == '#':
        return 0
    rcnt, lcnt, dcnt, ucnt = 0,0,0,0
    rootKey = str(h) + str(w)

    # to right
    for i in range(w+1, W):
        key = str(h) + str(i)
        if s[h][i] == '.':
            if key in dpr:
                rcnt += dpr[key] + 1
                break
            else:
                rcnt += 1
        else:
            break
    dpr[rootKey] = rcnt

    # to left
    for i in reversed(range(w)):
        key = str(h) + str(i)
        if s[h][i] == '.':
            if key in dpl:
                lcnt += dpl[key] + 1
                break
            else:
                lcnt += 1
        else:
            break
    dpl[rootKey] = lcnt

    # to down
    for i in range(h+1, H):
        key = str(i) + str(w)
        if s[i][w] == '.':
            if key in dpd:
                dcnt += dpd[key] + 1
                break
            else:
                dcnt += 1
        else:
            break
    dpd[rootKey] = dcnt

    # to up
    for i in reversed(range(h)):
        key = str(i) + str(w)
        if s[i][w] == '.':
            if key in dpu:
                ucnt += dpu[key] + 1
                break
            else:
                ucnt += 1
        else:
            break
    dpu[rootKey] = ucnt

    return rcnt + lcnt + dcnt + ucnt + 1

for i in range(H):
    for j in range(W):
        ans = max(ans, getCount(i, j))

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
s, ans = [], 0
dpr = [[0] * W for _ in range(H)]
dpl = [[0] * W for _ in range(H)]
dpd = [[0] * W for _ in range(H)]
dpu = [[0] * W for _ in range(H)]

for i in range(H):
    s.append(input())

# to right
for i in range(H):
    for j in reversed(range(W)):
        if j == W-1 and s[i][j] == '.':
            dpr[i][j] = 1
        elif s[i][j] == '#':
            dpr[i][j] = 0
        else:
            dpr[i][j] = dpr[i][j+1] + 1

# to left
for i in range(H):
    for j in range(0, W):
        if j == 0 and s[i][j] == '.':
            dpl[i][j] = 1
        elif s[i][j] == '#':
            dpl[i][j] = 0
        else:
            dpl[i][j] = dpl[i][j-1] + 1

# to down
for i in reversed(range(H)):
    for j in range(W):
        if i == H-1 and s[i][j] == '.':
            dpd[i][j] = 1
        elif s[i][j] == '#':
            dpd[i][j] = 0
        else:
            dpd[i][j] = dpd[i+1][j] + 1

# to up
for i in range(0, H):
    for j in range(W):
        if i == 0 and s[i][j] == '.':
            dpu[i][j] = 1
        elif s[i][j] == '#':
            dpu[i][j] = 0
        else:
            dpu[i][j] = dpu[i-1][j] + 1

for i in reversed(range(H)):
    for j in reversed(range(W)):
        cnt = dpr[i][j] + dpl[i][j] + dpd[i][j] + dpu[i][j] - 3
        ans = max(ans, cnt)

print(ans)