Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
import copy
from operator import itemgetter

[N, M] = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
BC = []
for m in range(M):
    BC.append([int(i) for i in input().split()])

# Aをソートする
A.sort()

# BCをCが大きい順にソートする
sorted_BC = sorted(BC, key=itemgetter(1, 0), reverse=True)

new_A = []
for [B, C] in sorted_BC:
    # もしAの最小値がCを超えていたらもうやる意味ないので終了
    if A[0] > C:
        break

    # 小さいほうからB枚のカードをCに変える
    # ただし変えるのは元の数字より大きい時だけ
    I = 0
    for i in range(B):
        I = i
        if A[i] > C:
            I -=1
            break
        new_A.append(C)
        #print(new_A)

    # 変えた分はリストから除外する
    #print(A)
    #print(I)
    del A[:I+1]
    if len(A) == 0:
        break

    #print(A)

if len(A) != 0:
    new_A.extend(A)

print (sum(new_A))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import copy
from operator import itemgetter

[N, M] = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
BC = []
for m in range(M):
    BC.append([int(i) for i in input().split()])

# Aをソートする
A.sort()

# BCをCが大きい順にソートする
sorted_BC = sorted(BC, key=itemgetter(1, 0), reverse=True)

new_A = []
for [B, C] in sorted_BC:
    # もしAの最小値がCを超えていたらもうやる意味ないので終了
    if A[0] > C:
        break

    # 小さいほうからB枚のカードをCに変える
    # ただし変えるのは元の数字より大きい時だけ
    I = 0
    for i in range(B):
        I = i
        if len(A) <= i:
            I -=1
            break
        if A[i] > C:
            I -=1
            break
        new_A.append(C)
        #print(new_A)

    # 変えた分はリストから除外する
    #print(A)
    #print(I)
    del A[:I+1]
    if len(A) == 0:
        break

    #print(A)

if len(A) != 0:
    new_A.extend(A)

print (sum(new_A))
# cook your dish here
n,x,t=list(map(int,input().split()))
rate=int(x/t)
if(rate==0 or rate==1):
    answer=n*t
    print(int(answer))
elif(rate!=0 and rate!=1):
    answer=n/rate
    print(int(answer))
elif(n==20 , x=12 , t=6 ):
    print(12)

### FIXED CODE ###

import math
 
n, x, t = map(int, input().split())
 
# count = math.ceil(n / x)
# print(count * t)
 
count = n // x
if n % x != 0:
    count = count + 1
print(count * t)
a,b=int(input().split())
c=0
while a<=b:
  s=str(a)
  if s==s[::-1]:
    c+=1
  a+=1
print(c)

### FIXED CODE ###

a,b=map(int, input().split())
c=0
while a<=b:
  s=str(a)
  if s==s[::-1]:
    c+=1
  a+=1
print(c)
```
n = int(input())
s = []
for i in range(n):
    tmp = int(input())
    s.append(tmp)
sorted(s)
max_s = sum(s)
 
if max_s % 10 != 0:
    print(max_s)
else:
    for j in range(n):
        if s[j] % 10 != 0:
            print(max_s - s[j])
            break
        elif j == n-1:
            assert "a"
            print(0)

### FIXED CODE ###

n = int(input())
s = []
for i in range(n):
    tmp = int(input())
    s.append(tmp)
s.sort()
max_s = sum(s)
 
if max_s % 10 != 0:
    print(max_s)
else:
    for j in range(n):
        if s[j] % 10 != 0:
            print(max_s - s[j])
            break
        elif j == n-1:
            print(0)
N,K=map(int, input().split())
a=N%K
print(a,K-a)

### FIXED CODE ###

X,Y,Z = map(int, input().split())
print(Z,X,Y)
N = int(input())
kuku = []
for i in range(1,10):
  for j in range(1,10):
    kuku.append(i*j)
if N in kuku:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import math
A, B = map(int, input().split())
if A>9 or B>9:
  print(-1)
  exit()
print(A*B)
x = int(input())
y = int(input())
 
print(int(x+(y/2)))

### FIXED CODE ###

X,Y = map(int,input().split())
 
print( X + (Y // 2))
import fractions


def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    mul = a[0]
    for i in range(1, n):
        mul = mul * a[i] // fractions.gcd(mul, a[i])
    for i in a:
        if (mul // i) % 2 == 0:
            print(0)
            exit()
    if m >= mul / 2:
        ans = (m - mul / 2) // mul + 1
        print(int(ans))
    else:
        print(0)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
def div_ceil(x, y): return (x + y - 1) // y
 
N, M = map(int, input().split())
*A, = map(int, input().split())
A = list(set([a // 2 for a in A]))
L = A[0]
for a in A[1:]:
    L *= a // gcd(L, a)
for a in A:
    if (L // a) % 2 == 0:
        ans = 0
        break
else:
    ans = div_ceil(M // L, 2)
print(ans)
a,b,c=map(int,input().split())
num = a
if (a % 2 == 1 and c % 2 == 0) or (a % 2 == 0 and c % 2 == 1):
  print('NO')
else:
  pritn('YES')

### FIXED CODE ###

a,b,c=map(int,input().split())
for i in range(a,b*a+1,a):
  if i%b==c: print('YES');break
else:
  print('NO')
n=int(input())
h=map(int,input().split())
dp=[0]*n
for i in range(1,n):
  if h[i-1]>=h[i]:
    dp[i]=dp[i-1]+1
  else:
    dp[i]=0
print(max(dp))

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
  if h[i-1]>=h[i]:
    dp[i]=dp[i-1]+1
  else:
    dp[i]=0
print(max(dp))
O = input()
E = input()

ans = ''
for i in range(min(O, E)):
    ans += O[i]
    ans += E[i]

if len(O) > len(E):
    ans += O[i]
elif len(O) < len(E):
    ans += E[i]

print(ans)

### FIXED CODE ###

print("".join([a+b for a,b in zip(input(),input()+" ")]))
s=input();l = len;p = print
if (s[0]==s[-1] * l(s)%2==0) + (s[0]!=s[-1] * l(s)%2==1):
    p("First")
else:
    p("Second")
s=input();l = len;p = print
if (s[0]==s[-1] * l(s)%2==0) + (s[0]!=s[-1] * l(s)%2==1):
    p("First")
else:
    p("Second")


### FIXED CODE ###

s=input();l = len;p = print
if (s[0]==s[-1] and l(s)%2==0) or (s[0]!=s[-1] and l(s)%2==1):
    p("First")
else:
    p("Second")
x,y = input().split()
li = ["A","B","C","D","E"]
nx = li.index(x)
ny = li.index(y)
if nx > ny:
    print(">")
if nx == ny:
    print("=")
else:
    print("<")

### FIXED CODE ###

x,y = input().split()
li = ["A","B","C","D","E","F"]
nx = li.index(x)
ny = li.index(y)
if nx > ny:
    print(">")
elif nx == ny:
    print("=")
else:
    print("<")
import numpy as np

n,k=map(int,input().split())
v=[0 for _ in range(n)]
w=[0 for _ in range(n)]
for i in range(n):
	w[i],v[i] = map(int,input().split())

dp = np.full((n+1, k+1), 0, dtype=np.int64)

for i in range(n):
	for j in range(k+1):
		if j-w[i] < 0:
			dp[i+1][j] = dp[i][j]
		else:
			dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
print(dp[n][k])

### FIXED CODE ###

n,k=map(int,input().split())
v=[0 for _ in range(n)]
w=[0 for _ in range(n)]
for i in range(n):
	w[i],v[i] = map(int,input().split())

dp = [[0 for i in range(k+1)] for j in range(n+1)]

for i in range(n):
	for j in range(k+1):
		if j-w[i] < 0:
			dp[i+1][j] = dp[i][j]
		else:
			dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
print(dp[n][k])
r,D,x2000 = map(int,input().split())
xi = x2000
for i in range(1,11):
    xi = r * xi - D
    print(xi)


### FIXED CODE ###

#!/usr/bin/python3
A,B = map(int,input().split())
x = 0
if A >= 13:
    x = B
elif 6 <= A and A <= 12:
    x = B//2
else:
    x = 0
print(x)
n = int(input())
ls = sorted(list(map(int, input().split())))
dead = []
for i in range(round(n ** 0.5) + 1):
    if ls[i] not in dead:
        for j in range(ls[i], ls[-1] + 1, ls[i]):
            if j in ls: 
                dead.append(j)

print(n - len(dead))


### FIXED CODE ###

n = int(input())
ls = sorted(list(map(int, input().split())))
dp = [0] * (ls[-1] + 1)
for i in ls:
    dp[i] += 1
    if dp[i] == 1:
        for j in range(i*2, ls[-1] + 1, i):
            dp[j] += 2

print(dp.count(1))
N,T  = map(int,input().split())
if T % N == 0:
    print (int(T / N))

d = int(T / N)
else:
    for i in range(d+1,0,-1):    
        if T % i ==0:
            print(i)
            break

### FIXED CODE ###

N,T  = list(map(int,input().split()))
d = int(T / N)
def ans():
    for i in range(d+1,0,-1):    
            if T % i ==0:
                print(i)
                break
if T % N == 0:
    print (d)
else:
    ans()
int_n = int(input())

ar_int_s = list()

for i in range(int_n):
    ar_int_s.append(int(input()))

minused = list()

for i in range(int_n):
    if (sum(ar_int_s) - sum(minused)) % 10 != 0:
        break
    else:
        minused.append(sorted(ar_int_s)[i:i])

print(sum(ar_int_s) - sum(minused))



### FIXED CODE ###

int_n = int(input())

ar_int_s = list()

for i in range(int_n):
    ar_int_s.append(int(input()))


if sum(ar_int_s) % 10 != 0:
    print(sum(ar_int_s))
else:
    li_minus = list(filter(lambda x: x % 10 != 0, ar_int_s))
    if len(li_minus) == 0:
        print(0)
    else:
        print(sum(ar_int_s) - min(li_minus))
import sys
a=int(input())
b=list(map(int,input().split()))
c=[]
for i in range(a):
  c+=str(b[i])
  for i in range(len(c)):
    if i==len(c)-1:
      break
    if int(c[i+1])==b[i]:
      print('YES')
      sys.exit()
print('NO')
      
    

### FIXED CODE ###

a=int(input())
b=list(map(int,input().split()))
d=len(b)
c=len(set(b))
if c==d:
  print('YES')
else:
  print('NO')
n = (int(i) for i in input().split())  

if (n // 1.08) == (n % 1.08):
  print(int(n // 1.08))
else:
  print(':(')


### FIXED CODE ###

import math

n = int(input())

nontax = math.floor(n / 1.08)

if math.floor(nontax * 1.08) == n:
    print(nontax)
elif math.floor((nontax + 1) * 1.08) == n:
    print(nontax+1)
else:
    print(':(')
x = raw_input()
print x ** 3

### FIXED CODE ###

n = raw_input()
print int(n) ** 3
a = int(input())
s = input()
if a>=3200:
  print(s)
else
  print("red")

### FIXED CODE ###

a = int(input())
s = input()
if a>=3200:
  print(s)
else:
  print('red')
X = input()
cnt_S, cnt_T = 0, 0

for c in range(X):
    if c == "S":
        cnt_S += 1
    else:
        if cnt_S:
            cnt_S -= 1
        else:
            cnt_T += 1
print(cnt_S, cnt_T)

### FIXED CODE ###

# coding: utf-8
X = input()
tmp = " "
cnt = 0
for x in X:
    if x == "S":
        tmp += x
        cnt += 1
    elif x == "T" and tmp[-1]=="S":
            cnt -= 1
            tmp = tmp[0:len(tmp)-1]
    else:
        tmp += x
        cnt += 1
print(cnt)
n=int(input())
if n[0]==n[1]==n[2] or n[1]==n[2]==n[3]:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

n=input()
if n[0]==n[1]==n[2] or n[1]==n[2]==n[3]:
  print('Yes')
else:
  print('No')
n, q = map(int, input().split()) # input:"2 2"
s = str(input())
#どこにACがあるかを計算しておいて、あとからL,Rでsplitする
ans=[0]*n
for i in range(n):
  if s[i]=='A' and s[i+1]=='C':
    ans[i]=1
for i in range(q):
  l, r = map(int, input().split()) #ループ内で一行ずつ読み込む
  print(sum(ans[l-1:r-1]))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
  if S[i : i + 2] == 'AC':
    t[i + 1] = t[i] + 1
  else:
    t[i + 1] = t[i]
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
def main():
    N = int(input())  # 文字列または整数(一変数)
    A = list(map(int, input().split()))  # 整数のリスト

    answer = 0

    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if A[j-1] + A[i-1] == abs(j - i):
                answer += 1

    print(answer)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = input()  # 文字列または整数(一変数)

    if N == "ABC":
        print("ARC")
    else:
        print("ABC")


if __name__ == '__main__':
    main()
from math import factorial
from operator import mul
from functools import reduce

def c(n,r):
  r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
def num(k): # k段昇る場合の数
  l,r = k // 2, 0
  for i in range(l+1):
    r += c(k-i,i)
    r %= mod
  return r

n,m=map(int,input().split())
mod = 10 ** 9 + 7

if m == 0:
  print(num(n) % mod)
  exit()

a=[int(input()) for i in range(m)] # 壊れてる段

# ここから先 m > 0
a = [-1] + a + [n+1] # len(a)=m+2
sa = [a[i+1]-a[i]-2 for i in range(len(a)-1)]
ans = 1
#print(sa)
for i in sa:
  ans *= num(i)
  ans %= mod
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
broken = [int(input()) for i in range(m)]
broken.sort()
broken += [0] * (n-m)
index = 0
mod = 10**9 + 7
for i in range(1,n+1):
  if i==1:
    if i != broken[index]:
      a=1
      b=1
    else:
      a=1
      b=0
      index += 1
  else:
    if i == broken[index]:
      a,b=b,0
      index += 1
    else:
      a,b=b,(a+b)%mod
print(b)
# -*- coding: utf-8 -*-
X, Y, Z = map(int, input().split())
print(int((X-Z)/(Y+Z)))


### FIXED CODE ###

# -*- coding: utf-8 -*-
X, Y = map(str, input().split())
dic = {"A":10,"B":11,"C":12,"D":13,"E":14,"F":15,}
if dic[X]>dic[Y]:
    print(">")
elif dic[X]<dic[Y]:
    print("<")
elif dic[X]==dic[Y]:
    print("=")
size = int(input())
stones = [int(val) for val in input().split()]
memo = [-1] * size

def ans(n):
	if memo[n] != -1:
		return memo[n]
	else:
		memo[n] = min(
			ans(n - 1) + abs(stones[n] - stones[n - 1]),
			ans(n - 2) + abs(stones[n] - stones[n - 2])
		)
		return memo[n]

if size == 1:
	print(0)
else:
	memo[0] = 0
	memo[1] = abs(stones[0] - stones[1])
	print(ans(size - 1))



### FIXED CODE ###


size = int(input())
stones = [int(val) for val in input().split()]
memo = [-1] * (size + 5)

def ans(n):
	if memo[n] != -1:
		return memo[n]
	else:
		memo[n] = min(
			ans(n - 1) + abs(stones[n] - stones[n - 1]),
			ans(n - 2) + abs(stones[n] - stones[n - 2])
		)
		return memo[n]


def ans_iterative(n):
	if memo[n] != -1:
		return memo[n]
	else:
		for idx in range(2, n):
			memo[idx] = min(
				memo[idx - 1] + abs(stones[idx] - stones[idx - 1]),
				memo[idx - 2] + abs(stones[idx] - stones[idx - 2])
			)
		return memo[n - 1]


if size == 1:
	print(0)
else:
	memo[0] = 0
	memo[1] = abs(stones[0] - stones[1])
	print(ans_iterative(size))
import numpy as np

n = int(input())

l = np.array(list(map(int,input().split())))
l.sort()
def num(first,second,third):
    if l[first] < l[second] + l[third]:
        dp[first] += 1
        if third > 0:
            num(first,second,third-1)
        elif second > 1:
            num(first,second-1,second-2)
        else:
            return
    else:
        if second == third + 1:
            return
        else:
            num(first,second-1,second-2)


            


dp = np.array([0]*n)

for i in range(n-1,1,-1):
    num(i,i-1,i-2)
print(np.sum(dp))

### FIXED CODE ###

import numpy as np
n = int(input())

l = np.array(list(map(int,input().split())))

l.sort()
l = l[::-1]
ans = 0
for i in range(n-2):
    j = i+1
    k = n-1
    while j < k:
        if l[i] < l[j] + l[k]:
            ans += k - j
            j += 1
        else:
            k -= 1
print(ans)
n=int(input())

def prime_factorize(n):
    d=defaultdict(int) 
    while n % 2 == 0:
        d[2]+=1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            d[f]+=1
            n //= f
        else:
            f += 2
    if n != 1:
        d[n]+=1
    return d

u=prime_factorize(n) 
cnt=0
for key,value in u.items():
    r=10**12
    l=0 
    while r-l>1:
        mid=(r+l)//2
        if mid*(mid+1)//2<=value:
            l=mid 
        else:
            r=mid
    cnt+=l
print(cnt)

### FIXED CODE ###

from  collections import defaultdict

n=int(input())

def prime_factorize(n):
    d=defaultdict(int) 
    while n % 2 == 0:
        d[2]+=1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            d[f]+=1
            n //= f
        else:
            f += 2
    if n != 1:
        d[n]+=1
    return d

u=prime_factorize(n) 
cnt=0
for key,value in u.items():
    r=10**12
    l=0 
    while r-l>1:
        mid=(r+l)//2
        if mid*(mid+1)//2<=value:
            l=mid 
        else:
            r=mid
    cnt+=l
print(cnt)
N, K = [int(i) for i in input().split()]
a = [0]*N
b = [0]*N
for i in range(N):
    a[i], b[i] = [int(i) for i in input().split()]

c = 0
d = 0
for i in b:
    c += i
    if c >= K:
        break
    d += 1
    
A = []
for i in range(d):
    A += [a[i]]*b[i]
A.sort()
print(A[K])

### FIXED CODE ###

N, K = map(int, input().split())
a = []
for i in range(N):
    a.append(list(map(int, input().split())))
a.sort()
sum = 0
for i, x in enumerate(a):
    sum += x[1]
    if sum >= K:
        print(a[i][0])
        break
import numpy as np
N = int(input())
a  = [int(i) for i in input().split()]
b = np.zeros_like(a)
t = 0
while [i % 2 for i in a] == b:
  a = [i / 2 for i in a]
  t = t + 1
print(t)


### FIXED CODE ###

N = int(input())
a  = [int(i) for i in input().split()]
t = 0
while all(i % 2 == 0 for i in a):
  a = [i / 2 for i in a]
  t = t + 1
print(t)
import math

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

a = [-1] * (M+2)

for i in range(1,M+1) :
    a[i] = int(input())

flag = True # 可能かどうか
for i in range(1,M) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

if flag :
    a[M+1] = N + 1

    ans = 1

    for i in range(M+1) :
        length = a[i+1] - a[i] - 2 # 上がる長さ
        max2step = math.floor(length / 2) # 2段の回数
        count = 1
        for j in range(1,max2step+1) :
            step2 = math.factorial(j)
            step1 = math.factorial(length-2*j)
            count += math.factorial(length - j) / step1 / step2
        ans *= count

    print(int(ans % 1000000007))
else :
    print(0)

### FIXED CODE ###

import math

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

if M == 0:
    a = [-1 , N+1]
else :
    a = [-1] * (M+2)

    for i in range(1,M+1) :
        a[i] = int(input())


flag = True # 可能かどうか
for i in range(0,M+1) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

fib = [1] * (N+1) # フィボナッチ数列
for i in range(2,N+1) :
    fib[i] = fib[i-1] + fib[i-2]

if flag :
    a[M+1] = N + 1

    ans = 1

    for i in range(M+1) :
        length = a[i+1] - a[i] - 2 # 上がる長さ
        ans *= fib[length]

    print(ans % 1000000007)
else :
    print(0)
K = int(input())
if(K%2 == 0):
  print(int((K/2)**2)
else:
  print(int((K/2)*(K/2+1)))

### FIXED CODE ###

K = int(input())
if(K%2 == 0):
  print(int((K/2)**2))
else:
  print(int(((K-1)/2)*((K+1)/2)))
N,M,Q = list(map(int, input().split()))
C = []
for i in range(Q):
    C.append(list(map(int, input().split())))
    
import itertools
res = 0
ls=list(range(1,M+1))
for a in itertools.combinations_with_replacement(ls, N):
    p = 0
    for c in C:
        if a[c[1]]-a[c[0]]==c[2]:
            p += c[3]
        res = max(res,p)
print(res)

### FIXED CODE ###

N,M,Q = list(map(int, input().split()))
C = []
for i in range(Q):
    C.append(list(map(int, input().split())))
    
import itertools
res = 0
ls=list(range(1,M+1))
for a in itertools.combinations_with_replacement(ls, N):
    p = 0
    for c in C:
        if a[c[1]-1]-a[c[0]-1]==c[2]:
            p += c[3]
        res = max(res,p)
print(res)
N = int(input())
A = list(map(int, input().split()))

ans = []
mx = max(A)
mi = min(A)

if mx * mi < 0:
    if abs(mi) > abs(mx):
        x = A.index(mi)
        for y in range(N):
            if y == x:
                continue
            A[y] += mi
            ans.append((x, y))
    else:
        x = A.index(mx)
        for y in range(N):
            if x == y:
                continue
            A[y] += mx
            ans.append((x, y))

for i in range(N - 1)[::(-1)**(max(A) < 0)]:
    l, r = A[i], A[i + 1]

    if l > r:
        if r <= 0 <= l:
            if l * r < 0:
                exit()
        if r > 0:
            A[i + 1] += l
            ans.append((i, i + 1))
        if l < 0:
            A[i] += r
            ans.append((i + 1, i))

print(len(ans))
for x, y in ans:
    print(x + 1, y + 1)

if list(sorted(A)) != A:
    print(A)
    1 / 0


### FIXED CODE ###

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

ans = []
mx = max(A)
mi = min(A)

if mx * mi < 0:
    if abs(mi) > abs(mx):
        x = A.index(mi)
        for y in range(N):
            if y == x:
                continue
            A[y] += mi
            ans.append((x, y))
    else:
        x = A.index(mx)
        for y in range(N):
            if x == y:
                continue
            A[y] += mx
            ans.append((x, y))

for i in range(N - 1)[::(-1)**(min(A) < 0)]:
    l, r = A[i], A[i + 1]

    if l > r:
        if r >= 0:
            A[i + 1] += l
            ans.append((i, i + 1))
        elif l <= 0:
            A[i] += r
            ans.append((i + 1, i))

print(len(ans))
for x, y in ans:
    print(x + 1, y + 1)

if list(sorted(A)) != A:
    print(A)
    1 / 0
from sys import stdin
from collections import defaultdict
from math import gcd


def main():
    MOD = 1000000007

    N, *AB = map(int, stdin.buffer.read().split())

    d = defaultdict(int)
    n_zeros = 0

    for a, b in zip(AB[::2], AB[1::2]):
        if a == 0 and b == 0:
            n_zeros += 1
            continue

        g = gcd(a, b)
        a, b = a // g, b // g

        if a * b > 0 or b == 0:
            c = (abs(a), abs(b))
        else:
            c = (-abs(b), -abs(a))

        d[c] += 1

    ans = 1
    n_not_paired = 0
    for ab, n in d.items():
        ab_pair = (-ab[1], -ab[0])
        if ab_pair in d:
            if ab[0] > 0:
                ans = ans * (pow(2, n, MOD) + pow(2, m, MOD) - 1) % MOD
        else:
            n_not_paired += n

    ans = (ans * pow(2, n_not_paired, MOD) + n_zeros - 1) % MOD
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin
from collections import defaultdict
from math import gcd


def main():
    MOD = 1000000007

    N, *AB = map(int, stdin.buffer.read().split())

    d = defaultdict(int)
    n_zeros = 0

    for a, b in zip(AB[::2], AB[1::2]):
        if a == 0 and b == 0:
            n_zeros += 1
            continue

        g = gcd(a, b)
        a, b = a // g, b // g

        if a * b > 0 or b == 0:
            c = (abs(a), abs(b))
        else:
            c = (-abs(a), -abs(b))

        d[c] += 1

    ans = 1
    n_not_paired = 0
    for ab, n in d.items():
        ab_pair = (-ab[1], -ab[0])
        if ab_pair in d:
            if ab[0] > 0:
                m = d[ab_pair]
                ans = ans * (pow(2, n, MOD) + pow(2, m, MOD) - 1) % MOD
        else:
            n_not_paired += n

    ans = (ans * pow(2, n_not_paired, MOD) + n_zeros - 1) % MOD
    print(ans)


if __name__ == '__main__':
    main()
def chkp(i,j):
	tmp=j+1
	count=1
	while tmp<W and s[i][tmp]==".":
		count+=1
		tmp+=1
	return count

def chkv(i,j):
	tmp=i+1
	count=1
	while tmp<H and s[tmp][j]==".":
		count+=1
		tmp+=1
	return count

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

p=[[0 for j in range(W)] for i in range(H)]
v=[[0 for j in range(W)] for i in range(H)]

for i in range(H):
	if W==1:
		if s[i][j]==".": p[i][0]=1
	else:
		if s[i][0]==".": p[i][0]=chkp(i,0)
		for j in range(1,W):
			if s[i][j]==".":
				if s[i][j-1]==".": p[i][j]=p[i][j-1]
				else: p[i][j]=chkp(i,j)

for j in range(W):
	if H==1:
		if s[i][j]==".": v[0][j]=1
	else:
		if s[0][j]==".": v[0][j]=chkv(0,j)
		for i in range(1,H):
			if s[i][j]==".":
				if s[i-1][j]==".": v[i][j]=v[i-1][j]
				else: v[i][j]=chkv(i,j)
					
print(max( max(v[i][j]+p[i][j] for j in range(W)) for i in range(H)  )-1)

### FIXED CODE ###

h,w=map(int,input().split())
ans=[[-3]*w for _ in range(h)]
s=[input() for _ in range(h)]
for i in range(h):
    tmp=0
    for j in range(w):
        if s[i][j]=="#": tmp=0
        else: tmp+=1
        ans[i][j]+=tmp
    tmp=0
    for j in range(w-1,-1,-1):
        if s[i][j]=="#": tmp=0
        else: tmp+=1
        ans[i][j]+=tmp

for j in range(w):
    tmp=0
    for i in range(h):
        if s[i][j]=="#": tmp=0
        else: tmp+=1
        ans[i][j]+=tmp
    tmp=0
    for i in range(h-1,-1,-1):
        if s[i][j]=="#": tmp=0
        else: tmp+=1
        ans[i][j]+=tmp

print(max( max(ans[i]) for i in range(h) ))