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

h,n=map(int,input().split())
INF=10**9
dp=[INF]*(h+10)
A=[list(map(int,input().split())) for i in range(n)]
dp[0]=0
for a,b in A:
  for i in range(h):
    index=min(h,i+a)
    x=dp[i]+b; y=dp[index]
    dp[index]=min(x,y)
print(dp[h])


### FIXED CODE ###

def IN(): return map(int,input().split())
ans = pow(2,31); mod = pow(10,9)+7
h,n=IN()
A=[]; dp=[pow(2,31)]*111111
for i in range(n):
  x,y=IN()
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(h+1111):
    dp[i+a]=min(dp[i+a],dp[i]+b)
for i in range(h,11111):
  ans=min(ans,dp[i])
print(ans)
### BUGGY CODE ###

h,w,d = map(int,input().split())
l = [list(map(int,input().split())) for i in range(h)]
ans = [[0]*(h*w+1) for i in range(d)]

for i in range(h):
    for j in range(w):
        ans[l[i][j]%d][l[i][j]//d] = (l[i][j],i,j)

count =[0]*(h*w+1)
for i in range(2,len(ans[0])):
    if ans[0][i] == 0:
        break
    count[ans[0][i][0]] = count[ans[0][i-1][0]] + abs(ans[0][i][1]-ans[0][i-1][1])+abs(ans[0][i][2]-ans[0][i-1][2])
for i in range(1,d):
    for j in range(1,len(ans[i])):
        if ans[i][j] == 0:
            break
        count[ans[i][j][0]] = count[ans[i][j-1][0]] + abs(ans[i][j][1]-ans[i][j-1][1])+abs(ans[i][j][2]-ans[i][j-1][2])

n = int(input())
for i in range(n):
    a,b = map(int,input().split())
    print(count[b]-count[a])

### FIXED CODE ###

h,w,d = map(int,input().split())
px = [0]*(h*w+1)
py = [0]*(h*w+1)
for i in range(h):
    l = list(map(int,input().split()))
    for j in range(w):
        px[l[j]],py[l[j]] = i,j  

count =[0]*(h*w+1)
for i in range(d+1,h*w+1):
    count[i] = count[i-d]+abs(px[i]-px[i-d])+abs(py[i]-py[i-d])

n = int(input())
for i in range(n):
    a,b = map(int,input().split())
    print(count[b]-count[a])
### BUGGY CODE ###

N = int(input())

P = [int(x) for x in input().split()]

cnt = 0
for i in range(N)[::-1]:
  for j in range(N)[i::-1]:
    if P[i] > P[j]:
      break
    elif j == 0:
      cnt += 1

print(cnt)  

### FIXED CODE ###

N = int(input())

P = [int(x) for x in input().split()]

cnt = 1
m = P[0]
for i in P[1:]:
  if i < m:
    m = i
    cnt += 1

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import argparse
import numpy as np

parser = argparse.ArgumentParser(description='Range Product')
parser.add_argument('a', type=int)
parser.add_argument('b', type=int)
args = parser.parse_args()

a = args.a
b = args.b

print a, b

if a > 0 and b > 0:
    print 'Positive'
elif a < 0 and b < 0:
    if (b - a) % 2 == 0:
        print 'Negative'
    else:
        print 'Positive'
else:
    print 'Zero'

### FIXED CODE ###

input = raw_input()
a, b = input.split()
a = int(a)
b = int(b)
if a > 0 and b > 0:
    print 'Positive'
elif a < 0 and b < 0:
    if (b - a) % 2 == 0:
        print 'Negative'
    else:
        print 'Positive'
else:
    print 'Zero'
### BUGGY CODE ###

import numpy as np

# A,B = list(map(int, input().split()))

# N = int(input())
N,M = list(map(int, input().split()))
As = np.array(list(map(int, input().split())))

# As.sort(reverse=True)
#
# for i in range(N-1):
#     A = As[i]
#     A_next = As[i+1]
#     while A > A_next and M>0:
#         A = A//2
#         M -= 1
#         print("use",M)
#
#     As[i] = A
#     print(As)
# print(sum(As))


for i in range(M):
    ind = np.argmax(As)
    As[ind] = As[ind] // 2

print(np.sum(As))


### FIXED CODE ###

import numpy as np

# A,B = list(map(int, input().split()))

# N = int(input())
N,M = list(map(int, input().split()))
As = np.array(list(map(int, input().split())))

# As.sort(reverse=True)
As[::-1].sort()
max_A = As[0]

while M > 0:
    i=1
    for i in range(1, min(M, N)):
        if As[i] <= max_A//2:
            break
    # print(M)
    # print(As)
    # print(i)
    As[:min(M,i)] = As[:min(M,i)] // 2
    # print(As)
    M -= i
    As[::-1].sort()
    max_A = As[0]
    # print(As)

print(np.sum(As))
### BUGGY CODE ###

n = int(input())
s = input()
ans = set()

for i in range(0,1000):
    flag = False
    num = str(i)
    if i < 10:
        num = "00"+num
    elif i <100:
        num = "0" + num
    for j in range(n):
        if s[j] == num[0]:
            for k in range(j+1,n):
                if s[k] == num[1]:
                    for l in range(k+1,n):
                        if s[l] == num[2]:
                            flag = True
                            ans.add(i)
                if flag:
                    break
        if flag:
            break
print(len(ans))
                        

### FIXED CODE ###

n = int(input())
s = input()
ans = 0

for i in range(0,1000):
    num = str(i)
    if i < 10:
        num = "00"+num
    elif i <100:
        num = "0" + num
    f = 0
    for j in range(n):
        if s[j] == num[f]:
            f += 1
        if f == 3:
            break
    if f==3:
        ans +=1
print(ans)
### BUGGY CODE ###

N, K = [int(i) for i in input().rstrip().split(' ')]
H = [int(i) for i in input().rstrip().split(' ')]
H.sort(reverse=True)
for hit in range(K):
    if H: H.pop(0)
print(sum(H))


### FIXED CODE ###

N, K = [int(i) for i in input().rstrip().split(' ')]
H = [int(i) for i in input().rstrip().split(' ')]
H.sort(reverse=True)
if len(H) <= K:print(0)
else:
    lst = [h for k, h in enumerate(H) if k >= K]
    print(sum(lst))
### BUGGY CODE ###

H, W, M = map(int, input().split())
h_dic, w_dic = {}, {}
m = set()
for i in range(M):
    h_i, w_i = map(int, input().split())
    m.add((h_i, w_i))
    if h_i in h_dic:
        h_dic[h_i] += 1
    else:
        h_dic[h_i] = 1
    if w_i in w_dic:
        w_dic[w_i] += 1
    else:
        w_dic[w_i] = 1
        
max_h_items = [[0,0]]
max_w_items = [[0,0]]

for key, value in h_dic.items():
    if value > max_h_items[0][1]:
        max_h_items = [[key, value]]
    elif value == max_h_items[0][1]:
        max_h_items.append([key, value])
for key, value in w_dic.items():
    if value > max_w_items[0][1]:
        max_w_items = [[key, value]]
    elif value == max_w_items[0][1]:
        max_w_items.append([key, value])
s = max_h_items[0][1] + max_w_items[0][1] - 1
for mh in max_h_items:
    for mw in max_w_items:
        if (mh[0], mw[0]) not in m:
            s = mh[1]+mw[1]
print(s)

### FIXED CODE ###

H, W, M = map(int, input().split())
h_dic, w_dic = {}, {}
m = set()
for i in range(M):
    h_i, w_i = map(int, input().split())
    m.add((h_i, w_i))
    if h_i in h_dic:
        h_dic[h_i] += 1
    else:
        h_dic[h_i] = 1
    if w_i in w_dic:
        w_dic[w_i] += 1
    else:
        w_dic[w_i] = 1
        
max_h_items = [[0,0]]
max_w_items = [[0,0]]

for key, value in h_dic.items():
    if value > max_h_items[0][1]:
        max_h_items = [[key, value]]
    elif value == max_h_items[0][1]:
        max_h_items.append([key, value])
for key, value in w_dic.items():
    if value > max_w_items[0][1]:
        max_w_items = [[key, value]]
    elif value == max_w_items[0][1]:
        max_w_items.append([key, value])
s = max_h_items[0][1] + max_w_items[0][1] - 1
for mh in max_h_items:
    for mw in max_w_items:
        if (mh[0], mw[0]) not in m:
            s = mh[1]+mw[1]
            print(s)
            break
    if s == max_h_items[0][1] + max_w_items[0][1]:
        break
if s == max_h_items[0][1] + max_w_items[0][1] - 1:
    print(s)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
MOD = 1000000007  

def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    matrix = [[] for _ in range(N+1)]
    for i in range(N-1):
        matrix[a[i]].append(b[i])
        matrix[b[i]].append(a[i])
    
    visited = [0]*(N+1)

    from collections import deque
    queue = deque()
    visited[1]=1
    answer = K
    num = K-1
    for node in matrix[1]:
        answer *= num
        num -= 1
        queue.append(node)
    answer %= MOD

    while queue:
        q = queue.popleft()
        if visited[q] != 0:
            continue
        visited[q] = 1

        num = K-2
        for child_node in matrix[q]:
            if visited[child_node] == 0:
                answer *= num
                num -= 1
                queue.append(child_node)

        answer %= MOD

    print(answer%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
MOD = 1000000007  

def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    matrix = [[] for _ in range(N+1)]
    for i in range(N-1):
        matrix[a[i]].append(b[i])
        matrix[b[i]].append(a[i])
    
    visited = [0]*(N+1)

    from collections import deque
    queue = deque()
    visited[1]=1
    answer = K
    num = K-1
    for node in matrix[1]:
        answer *= num
        answer %= MOD

        num -= 1
        queue.append(node)

    while queue:
        q = queue.popleft()
        if visited[q] != 0:
            continue
        visited[q] = 1

        num = K-2
        for child_node in matrix[q]:
            if visited[child_node] == 0:
                answer *= num
                answer %= MOD
                num -= 1
                queue.append(child_node)
        answer %= MOD

    print(answer%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)

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

import numpy as np
N = int(input())
S = input()

dic_ = {}

for i in range(N):
    dic_[S[i]] = dic_.get(S[i], []) + [i]

ans = [False]*1000

def get_first_pos(i, k):
    if dic_.get(str(i)) is not None:
        for x in dic_[str(i)]:
            if x > k:
                return x
    return None

        
for i in range(10):
    x1 = get_first_pos(i, -1)
    if x1 is None:
        continue
    for j in range(10):
        x2 = get_first_pos(j, x1)
        if x2 is None:       
            continue
        for k in range(10):
            x3 = get_first_pos(k, x2)
            if x3 is None:       
                continue
            ans[int(str(i)+str(j)+str(k))] = True
print(np.count_nonzero(ans))


### FIXED CODE ###

import bisect
import numpy as np
N = int(input())
S = input()

dic_ = {}
array =  np.zeros((10, 300001), np.int8)

for i in range(N):
    array[int(S[i]), i] = 1

def get_first_pos(i, k):
    ar = array[i, k+1:]
    wh = np.where(ar>0)
    if len(wh[0]) > 0:
        return wh[0][0] + k+1
    return None

ans = 0
        
for i in range(10):
    x1 = get_first_pos(i, -1)
    if x1 is None:
        continue
    for j in range(10):
        x2 = get_first_pos(j, x1)
        if x2 is None:       
            continue
        for k in range(10):
            x3 = get_first_pos(k, x2)
            if x3 is None:       
                continue
            ans += 1

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

N = int(input())
aA = sorted([int(_) for _ in input().split()],reverse=True)
#aA1 = [ _ for _ in aA if _ % 2 ]
#aA0 = [ _ for _ in aA if _ % 2 == 0 ]


def searchPair(aD):
    iL = len(aD)
    dsT =set()
    iC = 0
    for i in range(iL):
        for j in range(i+1,iL):
            if i in dsT or j in dsT:
                continue
            iWa =  aD[i] + aD[j]
            if not ( iWa & (iWa - 1)):
                dsT.add(i)
                dsT.add(j)
                iC += 1

    return iC
iC = 0
#iC += searchPair(aA1)
#iC += searchPair(aA0)
iC += searchPair(aA)
print(iC)



### FIXED CODE ###

N = int(input())
dA1 ={}
dA0 ={}
def lenbin(a):
    return len(bin(a)) - 2
def addData(oDict,a):
    if a in oDict:
        oDict[a]+=1
    else:
        oDict[a]=1
for a in input().split():
    a = int(a)
    if a % 2 :
        addData(dA1,a)
    else:
        addData(dA0,a)
def searchPair(oD):
    iC = 0
    for a in sorted(oD.keys(),reverse=True):
        t = ( 1 << lenbin(a)) - a
        if t == a:
            iAT = oD[a] // 2
            iC += iAT
            oD[a] -= iAT *2
        elif t in oD:
            iAT = min(oD[a],oD[t])
            iC += iAT
            oD[a] -= iAT
            oD[t] -= iAT
    return iC
#iC = 0
#iC += searchPair(dA1)
#iC += searchPair(dA0)
print(searchPair(dA1)+searchPair(dA0))
### BUGGY CODE ###

N, M, Q = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for i in range(M)]
PQ = [[int(_) for _ in input().split()] for i in range(Q)]

x = [[0] * (N+1) for i in range(N+1)]
for l, r in LR:
    x[l][r] += 1

from itertools import accumulate

t = [list(accumulate(row)) for row in x]

for p, q in PQ:
    result = 0
    for i in range(p, q+1):
        result += t[i][q] - t[i][p-1]
    print(result)


### FIXED CODE ###

N, M, Q = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for i in range(M)]
PQ = [[int(_) for _ in input().split()] for i in range(Q)]

from collections import defaultdict
from itertools import accumulate

C = [[0]*(N+1) for i in range(N+2)]

for l, r in LR:
    C[1][r] += 1
    C[l + 1][r] -= 1

#print(C)

T = [list(accumulate(row)) for row in C]
T = [list(accumulate(row)) for row in zip(*T)]

#print(T)

for p, q in PQ:
    print(T[q][p])
### BUGGY CODE ###

N=int(input())

i=0
sortedSet=[]

while i<N:
  temp=input()
  tempSet={}
  j=0
  while j<len(temp):
    if temp[j] in tempSet:
      tempSet[temp[j]]=tempSet[temp[j]]+1
    else:
      tempSet[temp[j]]=1
    j=j+1
  #print(tempSet)
  sortedSet.append(tempSet)
  i=i+1

result=0
i=0
while i<N:
  j=i+1
  while j<N:
    if sortedSet[i]==sortedSet[j]:
      result=result+1
      #print(i,j)
    j=j+1
  i=i+1

print(result)

### FIXED CODE ###

N=int(input())
 
i=0
sortedSet={}
while i<N:
  temp=''.join(sorted(input()))
  
  if temp in sortedSet:
    sortedSet[temp]=sortedSet[temp]+1
  else:
    sortedSet[temp]=1
  i=i+1

  
result=0
for v in sortedSet.values():
  result=int(result+v*(v-1)/2)
 
print(result)
### BUGGY CODE ###

N = int(input())

Dist = [[0 for i in range(N)] for j in range(N)]
Seen = [-1] * N

for i in range(N-1):
    u, v, w = map(int, input().split())
    Dist[u-1][v-1] = w
    Dist[v-1][u-1] = w

que = [0]
Seen[0] = 0
flag = True
while -1 in Seen:
    now = que.pop()
    for next in range(N):
        if Dist[now][next] == 0:
            continue
        elif Seen[next] == -1:
            que.insert(0, next)
            if Dist[now][next] % 2 == 0:
                Seen[next] = Seen[now]
            else:
                Seen[next] = 1 - Seen[now]
for i in range(N):
    print(Seen[i])


### FIXED CODE ###

N = int(input())

Dist = [[] for j in range(N)]
Seen = [-1] * N

for i in range(N-1):
    u, v, w = map(int, input().split())
    Dist[u-1].append([v-1, w])
    Dist[v-1].append([u-1, w])

que = [0]
Seen[0] = 0
flag = True
while -1 in Seen:
    now = que.pop()
    for next, distance in Dist[now]:
        if Seen[next] == -1:
            que.insert(0, next)
            if distance % 2 == 0:
                Seen[next] = Seen[now]
            else:
                Seen[next] = 1 - Seen[now]
for i in range(N):
    print(Seen[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
ans = 0
for i in range(1, N+1):
    divsum = sum(range(1, N//i + 1))
    ans += divsum*i
print(ans)


### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N+1):
    til = N//i
    divsum = int(til*(til+1)/2)
    ans += divsum*i
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
MAXBIT=60
MOD=10**9+7
bits=[[0 for _ in range(MAXBIT)] for _ in range(N)]
for i in range(N):
    tmp=A[i]
    j=0
    while tmp>0:
        bits[i][j]=tmp%2
        tmp=tmp//2
        j+=1
ans=0
for j in range(MAXBIT):
    cnt0=0
    for i in range(N):
        if bits[i][j]==0:
            cnt0+=1
    ans=(((cnt0*(N-cnt0))%MOD*(2**j))%MOD+ans)%MOD
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
MAXBIT=60
MOD=10**9+7
bits=[[0 for _ in range(MAXBIT)] for _ in range(N)]
for i in range(N):
    tmp=A[i]
    j=0
    while tmp>0:
        bits[i][j]=tmp%2
        tmp=tmp//2
        j+=1
ans=0
for j in range(MAXBIT):
    cnt0=0
    for i in range(N):
        if bits[i][j]==0:
            cnt0+=1
    ans=(((cnt0*(N-cnt0))%MOD*(2**j))%MOD+ans)%MOD
print(ans)
### BUGGY CODE ###

if __name__=="__main__":
    N = int(input())
    l = list(map(int,input().split(" ")))
    s = list(set(l))
    count = 0
    for i in s:
        if l.count(i)<i:
            count+=l.count(i)
        if l.count(i)>i:
            count+=l.count(i)-i
    print(count)

### FIXED CODE ###

def main():
    N = int(input())
    l = list(map(int,input().split(" ")))
    dic = {}
    count = 0
    for i in l:
        try:
            dic[i] += 1
        except Exception:
            dic[i] = 1

    for j in dic.items():
        count += j[1] - j[0] if j[1] >= j[0] else j[1]
    print(count)


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

import sys
from operator import itemgetter
from itertools import permutations
from math import sqrt

def solve(a: list):
    length = len(a)
    if length <= 3:
        return min(sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2) for p1, p2 in permutations(a, 2))

    med = length//2
    x_l, x_r = a[:med], a[med:]
    delta = min(solve(x_l), solve(x_r))
    median_x = a[med][0]
    m_a = []
        
    for p in x_l[::-1]:
        if p[0] < median_x-delta:
            break
        m_a.append(p)
    for p in x_r:
        if p[0] > median_x+delta:
            break
        m_a.append(p)
    m_a.sort(key=itemgetter(1))

    for i, (x1, y1) in enumerate(m_a):
        to_y = y1 + delta
        for j, (x2, y2) in enumerate(m_a[i+1:]):
            if y2 > to_y:
                break
            delta = min(delta, sqrt((x1-x2)**2+(y1-y2)**2))

    return delta

if __name__ == "__main__":
    N = int(input())
    a = sorted([tuple(map(float, l.split())) for l in sys.stdin.readlines()])
    print("{:.10f}".format(solve(a)))


### FIXED CODE ###

import sys
from operator import itemgetter
from itertools import combinations, takewhile
from math import sqrt

def solve(a: list, sorted_axis: int = -1):
    length = len(a)
    if length <= 3:
        return sqrt(min((x1-x2)**2+(y1-y2)**2 for (x1, y1), (x2, y2) in combinations(a, 2)))

    x_set_len = len(set(x for x, _ in a))
    axis1 = 0 if x_set_len > length/2 else 1

    if sorted_axis != axis1:
        a.sort(key=itemgetter(axis1))

    mid_index = length//2
    left, right = a[:mid_index], a[mid_index:]
    delta = min(solve(left, axis1), solve(right, axis1))

    axis2 = not axis1
    median = a[mid_index][axis1]
    mid_a = sorted([p for _iter in (
        (takewhile(lambda p: median-delta < p[axis1], left[::-1])),
        (takewhile(lambda p: p[axis1] < median+delta, right))
    ) for p in _iter], key=itemgetter(axis2))

    for i, (x1, y1) in enumerate(mid_a):
        ub = (x1 if axis1 else y1) + delta
        for x2, y2 in takewhile(lambda p: p[axis2] < ub, mid_a[i+1:]):
            delta = min(delta, sqrt((x1-x2)**2+(y1-y2)**2))

    return delta

if __name__ == "__main__":
    N = int(input())
    a = [tuple(map(float, l.split())) for l in sys.stdin.readlines()]
    print("{:.10f}".format(solve(a)))
### BUGGY CODE ###

N,M=map(int,input().split())
a=[]
b=[]
flag=0
for i in range(M):
    c,d = map(int,input().split())
    a.append(c)
    b.append(d)
for j in range(M):
    for k in range(M):
        if (b[j]==a[k]) and (a[j]==1) and (b[k]==N):
            flag += 1
        else:
            pass
if flag>0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

N,M=map(int,input().split())
island=[[] for i in range(N)]
for j in range(M):
    c,d=map(int,input().split())
    island[d-1].append(c)
    island[c-1].append(d)
f = 0
for k in range(N):
    if 1 in island[k]:
        if N in island[k]:
            f += 1
            break
        else:
            pass
    else:
        pass
if f>0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

N,M=map(int,input().split())
dp=[float("inf") for _ in range(2**N)]
dp[0]=0
for _ in range(M):
    a,b=map(int,input().split())
    C=list(map(int,input().split()))
    for v in range(2**N):
        nv=int(v)
        for c in C:
            bi=2**(c-1)
            if (v//bi)%2==0:
                nv+=bi
        dp[nv]=min(dp[nv],dp[v]+a)
if dp[-1]==float("inf"):
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

N,M=map(int,input().split())
dp=[float("inf") for _ in range(2**N)]
dp[0]=0
for _ in range(M):
    a,b=map(int,input().split())
    c=sum([2**(int(i)-1) for i in input().split()])
    for v in range(2**N):
        nv=v|c
        dp[nv]=min(dp[nv],dp[v]+a)
if dp[-1]==float("inf"):
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

import numpy as np
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]

# 横
A = np.array([[-10000] * W for i in range(H)])
B = np.array([[-10000] * W for i in range(H)])

S = np.array(S)
for i in range(H):
    jj = 0
    s = 0
    for j in range(W+1):
        if j == W or S[i, j] == '#':
            A[i, jj:j] = s
            s = 0
            jj = j + 1
        else:
            s += 1

S2 = S.T
B2 = B.T
for i in range(W):
    jj = 0
    s = 0
    for j in range(H+1):
        if j == H or S2[i, j] == '#':
            B2[i, jj:j] = s
            s = 0
            jj = j + 1
        else:
            s += 1

B = B2.T
X = A + B - 1
print(np.max(X))        


### FIXED CODE ###

H, W = map(int, input().split())
S = [list(input()) for i in range(H)]

# 横
A = [[-10000] * W for i in range(H)]
B = [[-10000] * W for i in range(H)]

for i in range(H):
    jj = 0
    s = 0
    for j in range(W+1):
        if j == W or S[i][j] == '#':
            for x in range(jj, j):
                A[i][x] = s
            s = 0
            jj = j + 1
        else:
            s += 1


for j in range(W):
    ii = 0
    s = 0
    for i in range(H+1):
        if i == H or S[i][j] == '#':
            for y in range(ii, i):
	            B[y][j] = s
            s = 0
            ii = i + 1
        else:
            s += 1

m = 0
for i in range(H):
    for j in range(W):
        m = max(A[i][j] + B[i][j] - 1, m)
            
print(m)
### BUGGY CODE ###

MOD = 1000000007

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

digits = [0] * 60
for i in A:
    for j in range(60):
        if i>>j&1 == 1:
            digits[j] += 1

ans = 0
for i in range(60):
    ans += (digits[i] * (N - digits[i]) % MOD) * ((1<<i) % MOD)
    ans %= MOD

print(ans)

### FIXED CODE ###

MOD = 1000000007

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

digits = [0] * 60
for i in A:
    for j in range(60):
        if i>>j&1 == 1:
            digits[j] += 1

ans = 0
for i in range(60):
    ans += digits[i] * (N - digits[i]) * (1<<i)
    ans %= MOD

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

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

s = 0
for i in range(N-K+1):
    s_tmp = sum(p[i:i+K])
    if s < s_tmp:
        s = s_tmp

print((s+K)/2)


### FIXED CODE ###

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

s = s_tmp = sum(p[0:K])
for i in range(N-K):
    s_tmp = s_tmp - p[i] + p[i+K]
    if s < s_tmp:
        s = s_tmp

print((s+K)/2)