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

import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
heapq.heapify(A)
for i in range(M):
    b,c = map(int,input().split())
    for j in range(b):
        a = heapq.heappushpop(A,c)
        if a > c:
            heapq.heappushpop(A,a)
            break
print(sum(A))

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for i in range(M)]
A.sort(key=lambda x:-x)
BC.sort(key=lambda x:x[1])
C = []
while BC and len(C) < N:
    b,c = BC.pop()
    for i in range(b):
        C.append(c)
        if len(C) == N:
            break
C.sort()
ans = 0
while C:
    a = A.pop()
    c = C.pop()
    ans += max(a,c)
ans += sum(A)
print(ans)
### BUGGY CODE ###

N,K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
before = 1
for i in A[:K]:
    before *= i

for i in range(K+1,len(A)+1):
    val = 1
    for j in A[i-K:i]:
        val *= j

    if(val > before):
        print("Yes")
    else:
        print("No")
    before = val

### FIXED CODE ###

N,K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

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

a,b,k=map(int,input().split());n=[i for i in range(a,b+1)];k-=1
for i in n:
  if i<=a+k or b-k<=i:print(i)

### FIXED CODE ###

a,b,k=map(int,input().split())
for i in range(k):
  if a+i<=b:print(a+i)
for i in range(k):
  if a+k<=b-k+1+i:print(b-k+1+i)
### BUGGY CODE ###


num = input()
l = []
for i in range(0,int(num)):
    l.append(input())

cnt = []
l_t = list(set(l))
for item in l_t:
    cnt.append(l.count(item))

max_v = max(cnt)

keys = []

for i in range(0,len(cnt)):
    if cnt[i] == max_v:
        keys.append(l_t[i])

for i in sorted(keys):
    print(i)

### FIXED CODE ###

from collections import Counter
N = int(input())
S = Counter(input() for _ in range(N))
m = max(S.values())
for v in sorted(k for k, v in S.items() if v == m):
	print(v)
### BUGGY CODE ###

#

def main():
    n = int(input())
    agrid = []
    agrid_pointer = [0] * n

    for i in range(n):
        al = list(map(int, input().split()))
        for j in range(len(al)):
            al[j] -= 1
        agrid.append(al)

    ans = 0
    while True:
        match = set()
        for i in range(n):
            if agrid_pointer[i] == n - 1 or i in match:  # もう全部対戦済み or この日対戦済み
                continue

            target = agrid[i][agrid_pointer[i]]
            if agrid_pointer[target] == n - 1 or target in match:  # もう全部対戦済み or この日対戦済み
                continue

            if agrid[target][agrid_pointer[target]] != i:  # 次対戦できない
                continue

            # can match
            agrid_pointer[i] += 1
            agrid_pointer[target] += 1

            match.add(i)
            match.add(target)
            if len(match) == n or len(match) == n - 1:  # 全員試合することが決まったら
                break

        # print(match)
        if len(match) == 0:  # 対戦がなくなったら
            break
        ans += 1

    # print(aconditions)
    # 対戦が残ってたら
    for p in agrid_pointer:
        if p != n - 1:
            print(-1)
            return
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#
import sys
import time

def input(): return sys.stdin.readline().strip()

def main():
    n = int(input())
    agrid = []
    agrid_pointer = [0] * n

    start = time.time()

    for i in range(n):
        al = list(map(int, input().split()))
        agrid.append(al)

    ans = 0

    while True:
        match = set()
        for i in range(n):
            if agrid_pointer[i] == n - 1 or i in match:  # もう全部対戦済み or この日対戦済み
                continue

            target = agrid[i][agrid_pointer[i]] - 1
            if agrid_pointer[target] == n - 1 or target in match:  # もう全部対戦済み or この日対戦済み
                continue
            # i, target は対戦可能

            if agrid[target][agrid_pointer[target]] - 1 != i:
                continue

            # can match
            agrid_pointer[i] += 1
            agrid_pointer[target] += 1

            match.add(i)
            match.add(target)

            if len(match) == n or len(match) == n - 1:  # 全員試合することが決まったら
                break

        # print(match)
        if len(match) == 0:  # 対戦がなくなったら
            break
        elapsed_time = time.time() - start
        if elapsed_time > 1.5:
            print(n * (n-1)//2)
            return

        ans += 1

    # print(aconditions)
    # 対戦が残ってたら
    for p in agrid_pointer:
        if p != n - 1:
            print(-1)
            return
    print(ans)


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

a, b, c, d = map(int, input().split())

x, y = max(c, d), min(c, d)
r = x - y
while r != 0:
    x, y = max(y, r), min(y, r)
    r = x - y
gcd = x
lcm = c * d // gcd

nc = b // c - (a - 1) // c
nd = b // d - (a - 1) // d
nlcm = b // lcm - (a - 1) // lcm

print((b - a + 1) - (nc + nd - nlcm))


### FIXED CODE ###

a, b, c, d = map(int, input().split())

x, y = c, d
r = x % y
while r != 0:
    x, y = y, r
    r = x % y
gcd = y
lcm = c * d // gcd

nc = b // c - (a - 1) // c
nd = b // d - (a - 1) // d
nlcm = b // lcm - (a - 1) // lcm

print((b - a + 1) - (nc + nd - nlcm))
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [a - 1 for a in A]

log_K = 1
while 1 << log_K < K:
    log_K += 1
# print(f'{log_K=}')
D = [[0] * N for _ in range(log_K)]
for i in range(N):
    D[0][i] = A[i]
for k in range(log_K - 1):
    for i in range(N):
        D[k + 1][i] = D[k][D[k][i]]
# print(f'{D=}')

now = 0
k = 0
while K > 0:
    if K & 1:
        now = D[k][now]
    K = K >> 1
    k += 1
print(now + 1)


### FIXED CODE ###

from collections import deque

N, K = map(int, input().split())
A = list(map(int, input().split()))
T = set([0])  # 0-indexed

c = 0  # 0-indexed
for i in range(N + 1):
    c = A[c] - 1
    # print('c', c)
    if c not in T:
        T.add(c)
    else:
        break
C = deque([c])
T = set([c])  # 0-indexed
for i in range(N + 1):
    c = A[c] - 1
    # print('c', c)
    if c not in T:
        T.add(c)
        C.append(c)
    else:
        break
c2 = 0  # 0-indexed
S = deque([0])
for i in range(N + 1):
    c2 = A[c2] - 1
    if c2 == c:
        break
    else:
        S.append(c2)
# print('C', C)
# print('S', S)
# print('len(C), len(S)', len(C), len(S))

if C[0] == 0:
    mod = K % len(C)
    ans = C[mod]
else:
    if len(S) > K:
        ans = S[K]
    else:
        mod = (K - len(S)) % len(C)
        ans = C[mod]
print(ans + 1)
### BUGGY CODE ###

ans,n = 0,int(input())
a_list = list(map(int,input().split()))
a_set = set(a_list)
a_dict = {val:a_list.count(val) for val in a_set}
for key,value in a_dict.items():
    if value>key:
        ans += value-key
    elif value<key:
        ans += value
print(ans)

### FIXED CODE ###

from collections import defaultdict

ans,n = 0,int(input())
a_list = list(map(int,input().split()))
a_dict = defaultdict(int)
for i in range(n):
    a_dict[a_list[i]]+=1
for key,value in a_dict.items():
    if value>key:
        ans += value-key
    elif value<key:
        ans += value
print(ans)
### BUGGY CODE ###

N = int(input())
*A, = map(int, input().split())
A.sort()
ans = A[0]
if ans == 0:
    print(0)
    exit()
for i in range(1, N):
    ans *= A[i]
if ans > 10 ** 18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
*A, = map(int, input().split())
if 0 in A:
    print(0)
    exit()
ans = A[0]
for i in range(1, N):
    ans *= A[i]
    if ans > 10 ** 18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

n = int(input())
aa = list(map(int, input().split()))
mod = 10**9+7
res = 1
pow2 = 1
ans = 0
for i in range(60):
    cnt = 0
    for a in aa:
        if a&pow2:
            cnt +=1
    ans = (ans + cnt * (n-cnt) * res)%mod
    res = (res*2)%mod
    pow2*=2
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
aa = list(map(int, input().split()))
mod = 10**9+7
res = 1
pow2 = 1
ans = 0
for i in range(60):
    cnt = np.count_nonzero(np.array(aa)&pow2)
    ans = (ans + cnt * (n-cnt) * res)%mod
    res = (res*2)%mod
    pow2*=2
print(ans)
### BUGGY CODE ###

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

all_count = 0
blue_count = 0

while all_count < N:
    if all_count + A >= N:
        blue_count += N - all_count
        break
    all_count += A
    all_count += B
    blue_count += A

print(blue_count)

### FIXED CODE ###

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

operation_count = N // (A+B)
blue_count = A * operation_count
if N % (A+B) > 0:
    rest = N % (A+B)
    blue_count += min([rest, A])

print(blue_count)
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from collections import Counter
[N, X, Y] = [int(item) for item in input().split()]
X -= 1
Y -= 1
gyoretu=np.full((N,N),2000)
gyoretu[0][0]=0
gyoretu[0][1]=1
for i in range(1,N-1):
    gyoretu[i][i-1]=1
    gyoretu[i][i]=0
    gyoretu[i][i+1]=1
gyoretu[N-1][N-2]=1
gyoretu[N-1][N-1]=0

gyoretu[X][Y]=1
gyoretu[Y][X]=1

G=csgraph_from_dense(gyoretu)
#print(G)
d=floyd_warshall(G)
#print(d)
#for k in range(N):
#    for i in range(N):
#        for j in range(N):
#            if gyoretu[i][j]> gyoretu[i][k] + gyoretu[k][j]:
#                gyoretu[i][j] =gyoretu[i][k] + gyoretu[k][j]
array=[]
for i in range(N):
        #array += gyoretu[i][i:]
        array += list(d[i][i:])
c=Counter(array)
for i in range(1, N):
    print(c[i])

### FIXED CODE ###

[N, X, Y] = [int(item) for item in input().split()]
X -= 1
Y -= 1
count=[0 for _ in range(N)]
for i in range(N):
    for j in range(i,N):
        count[min(abs(i-j),abs(i-X)+1+abs(Y-j),abs(i-Y)+1+abs(X-j))]+=1
#print(array)


for i in range(1,N):
        print(count[i])

#print(count)
### BUGGY CODE ###

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

A_list = [1 for i in range(A)]
B_list = [0 for v in range(B)]
S = A+B
S_list = A_list + B_list
total = []
for _ in range(N//S + 1):
  total.extend(S_list)
cnt = 0

for x in range(N):
  cnt = cnt + total[x]

print(cnt)

### FIXED CODE ###

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

S = A+B
count = N//S
pre_cnt = A*count
S_amari  = N-S*count
if S_amari >= A:
  cnt  = pre_cnt + A
else:
  cnt = pre_cnt + S_amari

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

n,h = map(int,input().split())
x = []
for i in range(n):
	x.append(list(map(int,input().split())))

t = 0
c = []#強い投げ刀たち
for i in range(n):
	if x[i][1]>max(x[i][0] for i in range(n))-1:
		c.append(x[i][1])
c.sort()
c.reverse()

if sum(c)>h-1:
	for i in range(len(c)):
		t += 1
		h -= c[i]
		if h<1:
			print(t)
			break
else:
	h -=sum(c)
	q = (h-1)//max(x[i][0] for i in range(n))+1
	print(q+len(c))

### FIXED CODE ###

n,h = map(int,input().split())
x = []
for i in range(n):
	x.append(list(map(int,input().split())))

t = 0
c = []#強い投げ刀たち
M = max(x[i][0] for i in range(n))

for i in range(n):
	if x[i][1]>M-1:
		c.append(x[i][1])
c.sort()
c.reverse()

if sum(c)>h-1:
	for i in range(len(c)):
		t += 1
		h -= c[i]
		if h<1:
			print(t)
			break
else:
	h -=sum(c)
	q = (h-1)//M+1
	print(q+len(c))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
len_s = len(s)
for i in range(q):
    l, r = map(int, input().split())
    cnt = s[l-1:r].count("AC")
    print(cnt)


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ans = [0] * (n + 1)
for i in range(n):
    ans[i + 1] = ans[i] + (1 if s[i:i+2] == "AC" else 0)
for j in range(q):
    l,r = map(int, input().split())
    res = ans[r-1] - ans[l-1]
    print(res)
### BUGGY CODE ###

import numpy as np
b = list(map(int, input().split()))
a = list(map(int, input().split()))

p = np.append(np.diff(np.sort([i for i in a if i > 0] + [0])),[10**10])
m = np.append(np.diff(np.sort(np.abs([i for i in a if i <= 0] + [0]))),[10**10])

lp = []
lm = []
for i in range(b[1]):
    if p[0] > m[0]:
        lm.append(m[0])
        m = np.delete(m, 0)
    else:
        lp.append(p[0])
        p = np.delete(p, 0)

res = sum(lp) + sum(lm) + min(sum(lp),sum(lm))

print(res)

### FIXED CODE ###

import numpy as np
b = list(map(int, input().split()))
a = list(map(int, input().split()))
x = b[0]-b[1]+1
res = 10**100
 
for i in range(x):
    tmp = i + b[1] - 1
    res = min( a[tmp]-a[i] + min(abs(a[i]),abs(a[tmp])),res)
        
print(res)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
l = []
for i in range(N):
    a, b = map(int, input().split())
    l.extend([a] * b)
print(sorted(l)[K-1])

### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [0] * 10 ** 5
for i in range(N):
    a, b = map(int, input().split())
    l[a-1] += b
count = 0
for j in range(10**5):
    count += l[j]
    if count >= K:
        print(j+1)
        break
### BUGGY CODE ###

from collections import deque
N,H = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB_a = sorted(AB, reverse = True, key=lambda x: x[0])
AB_b = deque(sorted(AB, reverse = True, key=lambda x: x[1]))
damage = 0
count = 0

while damage < H:
  if AB_b != deque([]):
    if AB_b[0][1] >= AB_a[0][0]:
      damage += AB_b[0][1]
      AB_b.popleft()
    else:
      damage += AB_a[0][0]
  else:
    count += (H-damage)//AB_a[0][0]
    damage = H - (H-damage)%AB_a[0][0]
    if damage == H:
      break
    else:
      count += 1
      break
  count += 1
print(count)

### FIXED CODE ###

from bisect import bisect_left
N,H = map(int,input().split())
A = [0]*N
B = [0]*N

for i in range(N):
  a,b = map(int,input().split())
  A[i] = a
  B[i] = b

A = max(A)
B = sorted(B)

count,damage = 0,0
b = bisect_left(B,A)

for i in range(len(B)-1,b-1,-1):
  damage += B[i]
  count += 1
  if damage >= H:
    print(count)
    exit()

count,damage = 0,0
damage = sum(B[b:])
count += len(B[b:])
count += (H-damage)//A
damage = H - (H-damage)%A
if damage == H:
  pass
else:
  count += 1
print(count)
### BUGGY CODE ###

#ABC 104 C - All Green
#順列総当たりでやる

import itertools

d, g = map(int, input().split())
#print(d)
p=[]
c=[]
ld = []
for i in range(d):
  pk, ck = map(int, input().split())
  p.append(pk)
  c.append(ck)
  ld.append(i)

jun = list(itertools.permutations(ld))
ans_list=[]

for j in jun:
  #順列の数だけ試す。j[番号]で調べてる順列の番号番目の数を返す
  ten = 0
  mondaisu = 0
  for k in range(d):
    bango = j[k]
    katen = (bango + 1)*100*p[bango] + c[bango]
#    print("n問目"+str(bango +1) + "加点"+ str(katen))
    if ten + katen > g:
      nokori = ((g-ten)-1)//((bango + 1)*100) + 1
      if nokori > p[bango]:#ボーナス点がないと届かない場合
        mondaisu += p[bango]
      else:
        mondaisu += nokori
      break
    else:
      ten += katen
      mondaisu += p[bango]
  ans_list.append(mondaisu)
#  print(str(j) + "問題数" + str(mondaisu) +"答えリスト")
#  print(ans_list)
        
print(min(ans_list))      
  
#print(jun[0][1])

  
#print(p)
#print(c)

### FIXED CODE ###

#ABC 104 C - All Green

#ビット総当たりでやる

d, g = map(int, input().split())
#print(d)

p=[]
c=[]

for i in range(d):
  pk, ck = map(int, input().split())
  p.append(pk)
  c.append(ck)
#print(p)
#print(c)
  
ans = 10000#仮の答え

#2^d通り試す
for i in range(2 ** d):
  #右からn番目の桁が1→n+1の配点の問題を完全に解く
  ten = 0
  mondaisu = 0
  for j in range(d):
    if (i>>j)&1 == 1:
      #p[j]個あるj+1の配点の問題を完全に解く
      ten += (j+1)*100*p[j] + c[j]
      mondaisu += p[j]
    else:
      #p[j]個あるj+1の配点の問題は完全にとかない
      k = j
  #フラグの立った配点の問題を全部といた
  if ten > g:
    if ans > mondaisu:
      ans = mondaisu
  else:
    #中途半端に解かないと行けない場合p[k]の問題を中途半端に解く
    if g-ten <= (k+1)*100*p[k] :
      mondaisu += (g-ten-1)//((k+1)*100) +1
      if ans > mondaisu:
        ans = mondaisu
      #中途半端に解いて届かない場合スルー
#  print(mondaisu)    
print(ans)
### BUGGY CODE ###

h,w=map(int,input().split())
g=[['#']*(w+2)]
for _ in range(h):
  g.append(list('#'+input()+'#'))
g.append(['#']*(w+2))

ans=0
for i in range(1,h+1):
  for j in range(1,w+1):
    c=0
    if g[i][j]=='.':
      c+=1
      u,d,r,l=0,0,0,0
      while g[i-(u+1)][j]=='.':
        u+=1
        c+=1
      while g[i+(d+1)][j]=='.':
        d+=1
        c+=1
      while g[i][j-(l+1)]=='.':
        l+=1
        c+=1
      while g[i][j+(r+1)]=='.':
        r+=1
        c+=1
    ans=max(ans,c)
print(ans)

### FIXED CODE ###

import numpy as np

h,w=map(int,input().split())
g = np.array([list(input()) for _ in range(h)])
g = np.where(g=='.',1,0)

l = np.zeros((h,w),dtype=np.int)
r = np.zeros((h,w),dtype=np.int)
u = np.zeros((h,w),dtype=np.int)
d = np.zeros((h,w),dtype=np.int)

for i in range(w):
  l[:,i] = (l[:,i-1]+1)*g[:,i]
  r[:,-i-1] = (r[:,-i]+1)*g[:,-i-1]

for i in range(h):
  u[i,:]=(u[i-1,:]+1)*g[i,:]
  d[-i-1,:]=(d[-i,:]+1)*g[-i-1,:]

print(np.max(l+r+u+d)-3)
### BUGGY CODE ###

S = input()
n= int(input())
condition=True

for i in range(n):
  Q = [i for i in input().split()]
  if Q[0] =='1':
    if condition ==True:
      condition=False
    else:
      condition=True
  else:
    if Q[1]=='1':
      if condition ==True:
        S = Q[2]+S
      else:
        S =S+Q[2]
    else:
      if condition==True:
        S =S+Q[2]
      else:
        S = Q[2]+S
    #print(S)

if condition ==False:
  S=S[::-1]
print(S)

### FIXED CODE ###

from collections import deque

S = deque(input())
n= int(input())
condition=True

for i in range(n):
  Q = [i for i in input().split()]
  if Q[0] =='1':
    if condition ==True:
      condition=False
    else:
      condition=True
  else:
    if Q[1]=='1':
      if condition ==True:
        S.appendleft(Q[2])
      else:
        S.append(Q[2])
    else:
      if condition==True:
        S.append(Q[2])
      else:
        S.appendleft(Q[2])
    #print(S)

if condition ==False:
  S.reverse()

for i in S:
  print(i, end='')
### BUGGY CODE ###

n, m = list(map(int, input().split(" ")))
s = input()
t = input()
if n<m:
  s, t = t, s
  n, m = m, n
def gcd(a,b):
  while b > 0:
    a, b = b, a % b
  return a
d = gcd(n, m)
l = n*m // d
a = ['' for i in range(l)]
res = l
for i in range(n):
  a[i*(l//n)] = s[i]
for i in range(m):
  if a[i*(l//m)]!='' and a[i*(l//m)]!=t[i]:
    res = -1
    break
print(res)

### FIXED CODE ###

n, m = list(map(int, input().split(" ")))
s = input()
t = input()
def gcd(a,b):
  while b > 0:
    a, b = b, a % b
  return a
d = gcd(n, m)
l = n*m // d
res = l

s_sep = n//d
t_sep = m//d

for si,ti in zip(s[::s_sep], t[::t_sep]):
  if si!=ti:
    res = -1
    break
print(res)
### BUGGY CODE ###

import numpy as np
# import math
# import collections
import sys
input = sys.stdin.readline

H,W,N = map(int,input().split())

ab = []

eff = []

for i in range(N):
    temp = list(map(int,input().split()))
    ab.append(temp)
    for j in range(3):
        for k in range(3):
            if (temp[0]-j >= 1) & (temp[0]-j <= H-2):
                if (temp[1]-k >= 1) & (temp[1]-k <= W-2):
                    eff.append([temp[0]-j,temp[1]-k])

count = [0 for i in range(10)]

while True:
    if eff == []:
        break
    num = eff.count(eff[0])
    count[num] += 1
    eff = [i for i in eff if i != eff[0]]

count[0] = (H-2) * (W-2) - sum(count)

for i in range(10):
    print(count[i])


### FIXED CODE ###

import numpy as np
# import math
import collections
import sys
input = sys.stdin.readline

H,W,N = map(int,input().split())

ab = []

eff = collections.defaultdict(int)

for i in range(N):
    temp = list(map(int,input().split()))
    ab.append(temp)
    for j in range(3):
        for k in range(3):
            if (temp[0]-j >= 1) & (temp[0]-j <= H-2):
                if (temp[1]-k >= 1) & (temp[1]-k <= W-2):
                    eff[(temp[0]-j,temp[1]-k)] += 1

count = collections.Counter(eff.values())

count0 = (H-2) * (W-2) - sum(count.values())

print(count0)
for i in range(1,10):
    if i in count:
        print(count[i])
    else:
        print(0)
### BUGGY CODE ###

n,k=map(int,input().split())
p = [(int(v)+1)/2 for v in input().split()]
e = [sum(p[i:i+k]) for i in range(n-k+1)]
print(max(e))
  
  

### FIXED CODE ###

n,k=map(int,input().split())
p = [(int(v)+1)/2 for v in input().split()]
e = [sum(p[:k])]
for i in range(n-k):
  e.append(e[-1]-p[i]+p[i+k])
print(max(e))
### BUGGY CODE ###

N=int(input())
tmp=0

while N!=0:
  tmp += N % 10
  N=N//10
  
if tmp % 9 == 0:
  ans="Yes"
else:
  ans="No"
  
print(ans)


### FIXED CODE ###

N=input()
tmp=0

for i in range(len(N)):
  tmp += int(N[i])

#print(tmp)
if tmp % 9 == 0:
  ans="Yes"
else:
  ans="No"
  
print(ans)
### BUGGY CODE ###

from bisect import bisect_left
import sys

input = sys.stdin.readline

H, W = map(int, input().split())
s = [input() for _ in range(H)]

row_blocks = []
for r in range(H):
    t = [-1]
    for c in range(W):
        if s[r][c] == '#':
            t.append(c)
    t.append(W)
    row_blocks.append(t)
# print(row_blocks)

col_blocks = []
for c in range(W):
    t = [-1]
    for r in range(H):
        if s[r][c] == '#':
            t.append(r)
    t.append(H)
    col_blocks.append(t)
# print(col_blocks)

rr = [[None] * W for _ in range(H)]
cc = [[None] * W for _ in range(H)]

for r in range(H):
    for c in range(W):
        ri = bisect_left(row_blocks[r], c)
        rr[r][c] = (row_blocks[r][ri] - 1) - row_blocks[r][ri - 1]
        ci = bisect_left(col_blocks[c], r)
        cc[r][c] = (col_blocks[c][ci] - 1) - col_blocks[c][ci - 1]

ans = 0
for r in range(H):
    for c in range(W):
        t = rr[r][c] + cc[r][c] - 1
        ans = max(ans, t)
print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.readline

H, W = map(int, input().split())
s = [input() for _ in range(H)]

row_blocks = []
for r in range(H):
    t = []
    x = 0
    for c in range(W):
        if s[r][c] == '.':
            x += 1
        else:
            x = 0
        t.append(x)

    x = 0
    for i in range(W - 1, -1, -1):
        if t[i] > 0:
            x = max(x, t[i])
        else:
            x = 0
        t[i] = x
    row_blocks.append(t)
# print(row_blocks)

col_blocks = []
for c in range(W):
    t = []
    x = 0
    for r in range(H):
        if s[r][c] == '.':
            x += 1
        else:
            x = 0
        t.append(x)

    x = 0
    for i in range(H - 1, -1, -1):
        if t[i] > 0:
            x = max(x, t[i])
        else:
            x = 0
        t[i] = x
    col_blocks.append(t)
# print(col_blocks)

ans = 0
for r in range(H):
    for c in range(W):
        t = row_blocks[r][c] + col_blocks[c][r] - 1
        ans = max(ans, t)
print(ans)
### BUGGY CODE ###

import itertools
from sys import stdin
N=list(map(int,stdin.readline().strip().split()))[0]
st=list(stdin.readline().strip())
count=0
stt=set(st)
num=list(stt)
# num=["0","1","2","3","4","5","6","7","8","9"]
# num = [s for s in num if s in stt ]
num_list= ["".join(i) for i in itertools.product(num,repeat=3)]

for number in num_list:
    cnt = 0
    for i in range(N):
        if number[cnt]==st[i]:
            cnt+=1
            if cnt==3:
                count += 1
                break


print(count)

### FIXED CODE ###

def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()
### BUGGY CODE ###

import numpy as np
nkq = list(map(int, (input().split())))
ans = [int(input()) for i in range(nkq[2])]
total = nkq[1] - nkq[2]
hold_point = np.array([])
for i in range(nkq[0]):
    hold_point = np.insert(hold_point, i, total)
for i in ans:
    hold_point[i - 1] += 1
for i in hold_point:
    if i > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

import numpy as np
nkq = list(map(int, (input().split())))
ans = [int(input()) for i in range(nkq[2])]
total = nkq[1] - nkq[2]
hold_point = np.array([total]*nkq[0])
for i in ans:
    hold_point[i - 1] += 1
for i in hold_point:
    if i <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

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

for i in range(N-1):
  p[i+1] = p[i] * p[i+1]
if p[i+1] > 10**18:
  print('-1')
else:
  print(p[i+1])

### FIXED CODE ###

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

if 0 in p:
  print(0)
  exit()

for i in range(N-1):
  p[i+1] = p[i] * p[i+1]
  if p[i+1] > 10**18:
    print('-1')
    exit()
print(p[i+1])