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

from heapq import heappop , heappush

X , Y , Z , K = map(int,input().split())

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

# それぞれソート
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

# 処理済みフラグ
confilm = []

q = [(-(A[0] + B[0] + C[0]) , 0,0,0)]

for _ in range(K) :
    val , i , j , k = heappop(q)

    print(-val)

    t = (i+1,j,k)
    if i + 1 < X and not t in confilm :
        heappush(q,(-(A[i+1] + B[j] + C[k]),) + t)
        confilm.append(t)

    t = (i,j+1,k)
    if j + 1 < Y and not t in confilm :
        heappush(q,(-(A[i] + B[j+1] + C[k]),) + t)
        confilm.append(t)

    t = (i,j,k+1)
    if k + 1 < Z and not t in confilm :
        heappush(q,(-(A[i] + B[j] + C[k+1]),) + t)
        confilm.append(t)




### FIXED CODE ###

from heapq import heappop , heappush

X , Y , Z , K = map(int,input().split())

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

# それぞれソート
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

# 処理済みフラグ
confilm = []

q = [(-(A[0] + B[0] + C[0]) , 0,0,0)]

for _ in range(K) :
    val , i , j , k = heappop(q)

    print(-val)

    t = (i+1,j,k)
    if i + 1 < X and not t in confilm :
        heappush(q,(-(A[i+1] + B[j] + C[k]),) + t)
        confilm.append(t)

    t = (i,j+1,k)
    if j + 1 < Y and not t in confilm :
        heappush(q,(-(A[i] + B[j+1] + C[k]),) + t)
        confilm.append(t)

    t = (i,j,k+1)
    if k + 1 < Z and not t in confilm :
        heappush(q,(-(A[i] + B[j] + C[k+1]),) + t)
        confilm.append(t)
### BUGGY CODE ###

from collections import Counter
N=list(map(int,input().split()))
A=list(map(int,input().split()))

counter = Counter(A)

A=list(set(A))
A.sort()

check=A.copy()
search=[]

while True:
    if len(check)<=0:
        break
    
    c = check.pop(0)
    search.append(c)

    check = [ _ for _ in check if (_%c !=0)or(_ < c**(1/2)) ]

ans=[s for s in search if counter[s]==1]
print(len(ans))

### FIXED CODE ###

# %%time
# from collections import Counter

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

# A=list(range(2,10**6))

# counter = Counter(A)

A.sort()
max=A[-1]
dp=[0]*(max+1)

for i in A:
    if dp[i]!=0:
        dp[i]+=1
        continue
    for j in range(1*i,max+1,i):
        dp[j]+=1
        
ans=[]
for a_idx,a in enumerate(A):
    if dp[a] == 1:
        ans.append(a)
        
print(len(ans))
### BUGGY CODE ###

s = input()

ans = 0
while '01' in s or '10' in s:
    s_next = s.replace('01', '')
    ans += len(s) - len(s_next)
    s = s_next
    s_next = s.replace('10', '')
    ans += len(s) - len(s_next)
    s = s_next
print(ans)


### FIXED CODE ###

s = input()

ans = 0

s_0 = s.replace('0', '')
n_0 = len(s) - len(s_0)
s_1 = s.replace('1', '')
n_1 = len(s) - len(s_1)

print(2 * min(n_0, n_1))
### BUGGY CODE ###

n,k=map(int,input().split())
h=[int(i) for i in input().split()]

l=[0]+[100000000000000000000000000000 for i in range(n-1)]

for i in range(n-1):
    if i<n-k:
        for j in range(k):
            l[i+j+1]=min(l[i+j+1],abs(h[i]-h[i+j+1])+l[i])
    else:
        for j in range(n-i-1):
            l[i+j+1]=min(l[i+j+1],abs(h[i]-h[i+j+1])+l[i])

print(l[-1])
        




### FIXED CODE ###

n,k=map(int,input().split())
h=[int(i) for i in input().split()]

l=[0]+[100000000000000000000000000000 for i in range(n-1)]

for i in range(n-1):
    if i<n-k:
        for j in range(k):
            l[i+j+1]=min(l[i+j+1],abs(h[i]-h[i+j+1])+l[i])
    else:
        for j in range(n-i-1):
            l[i+j+1]=min(l[i+j+1],abs(h[i]-h[i+j+1])+l[i])

print(l[-1])
### BUGGY CODE ###

H, N = map(int,input().split())
magic = []
for i in range(N):
    a,b = map(int,input().split())
    magic.append((a, b))
magic.sort(reverse=True)
amax, _ = magic[0]

INF = 1<<60

def solve():
    btab = [INF] * (H+1)
    btab[0] = 0
    for h in range(1, min(amax, H)+1):
        btab[h] = min([b for a, b in magic if a >= h])
    for h in range(2, H+1):
        for a, b in magic:
            c = b + btab[max(h-a, 0)]
            if c < btab[h]:
                btab[h] = c
    return btab[H]

print(solve())

### FIXED CODE ###

H, N = map(int,input().split())
magic = []
for i in range(N):
    a,b = map(int,input().split())
    magic.append((a, b))
magic.sort(reverse=True)
amax, _ = magic[0]

INF = 1<<60

def solve():
    btab = [INF] * (H+1)
    btab[0] = 0
    oneshot = min(amax, H)
    for h in range(1, oneshot+1):
        btab[h] = min([b for a, b in magic if a >= h])
    for h in range(2, H+1):
        for a, b in magic:
            c = b + btab[max(h-a, 0)]
            if c < btab[h]:
                btab[h] = c
    return btab[H]

print(solve())
### BUGGY CODE ###

def main():  
  N,M=map(int,input().split())
  A=list(map(int,input().split()))
  dp=[2,5,5,4,5,6,3,7,6]
  p=[]
  q=[]
  for i in range(M):
    p.append(dp[A[i]-1])
    q.append(str(A[i]))
  bp=['0']*(N+1)
  for i in range(N-1):
    for j in range(len(p)):
      if i+p[j]>N:
        continue
      if bp[i]=='0':
          if i!=0:
              continue
      bp[i+p[j]]=str(max(int(bp[i+p[j]]),int(q[j]+bp[i])))
  ans=bp[N]
  ans=ans.rstrip('0')
  print(ans)
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():  
  N,M=map(int,input().split())
  A=list(map(int,input().split()))
  dp=[2,5,5,4,5,6,3,7,6]
  p=[]
  q=[]
  for i in range(M):
    p.append(dp[A[i]-1])
    q.append(A[i])
  bp=[[0,0]for i in range(N+1)]
  for i in range(N-1):
    for j in range(len(p)):
      if i+p[j]>N:
        continue
      if bp[i][0]==0:
          if i!=0:
              continue
      bp[i+p[j]][0]=max(bp[i+p[j]][0],bp[i][0]+(10**bp[i][1])*q[j])
      bp[i+p[j]][1]=bp[i][1]+1
  print(bp[N][0])
if __name__=='__main__':
  main()
### BUGGY CODE ###

n = int(input())
s = input()

r_list = []
g_list = []
b_list = []
for _ in range(n):
    if s[_] == "R":
        r_list.append(_)
    elif s[_] == "G":
        g_list.append(_)

count = 0
for r in r_list:
    for g in g_list:
        if min(r, g) - abs(r - g) > 0:
            if s[min(r, g) - abs(r - g)] == "B":
                count += 1
        if max(r, g) + abs(r - g) < n:
            if s[max(r, g) + abs(r - g)] == "B":
                count += 1
        if (r + g) % 2 == 0:
            if s[(r + g) // 2] == "B":
                count += 1


print(len(r_list) * len(g_list) * (n - len(r_list) - len(g_list)) - count)

### FIXED CODE ###

n = int(input())
s = input()

r_list = []
g_list = []
for _ in range(n):
    if s[_] == "R":
        r_list.append(_)
    elif s[_] == "G":
        g_list.append(_)

count = 0
for r in r_list:
    for g in g_list:
        if min(r, g) - abs(r - g) > 0:
            if s[min(r, g) - abs(r - g)] == "B":
                count += 1
        if max(r, g) + abs(r - g) < n:
            if s[max(r, g) + abs(r - g)] == "B":
                count += 1
        if (r + g) % 2 == 0:
            if s[(r + g) // 2] == "B":
                count += 1


print(len(r_list) * len(g_list) * (n - len(r_list) - len(g_list)) - count)
### BUGGY CODE ###

# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
#import math
import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    N=int(input())
    X=list(map(int,input().split()))
    Z=[np.median(X[:i]+X[i+1:]) for i in range(N)]

    for i in range(N):
        print(int(Z[i]))



resolve()

### FIXED CODE ###

def resolve():
    N=int(input())
    X=list(map(int,input().split()))
    Y=sorted(X)
    l=Y[N // 2-1]
    r=Y[N//2]


    for i in X:
        if i<r:
            print(r)
        else:
            print(l)






resolve()
### BUGGY CODE ###

def main():
    n = int(input())
    l = sorted(list(map(int, input().split())), reverse=True)
    count = 0
    for i in range(n-2):
        a = l[i]
        for j in range(i+1,n-1):
            b = l[j]
            x = a-b
            z = a+b
            for k in range(j+1, n):
                c = l[k]
                if x >= c:
                    break
                if c < z:
                    count += 1
    print(count)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import bisect

def main():
    n = int(input())
    l = sorted(list(map(int, input().split())))
    count = 0
    for i in range(n-2):
        a = l[i]
        for j in range(i+1, n-1):
            b = l[j]
            kmax = bisect.bisect_left(l, a+b)
            #print("k", kmax, "j", j, "k-j", kmax-(j+1), a, b)
            count += max(kmax-(j+1),0)
    print(count)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

s = input()
n = int(input())

try_list = []
for i in range(n):
    t = input().split()
    try_list.append(t)

for t in try_list:
    if t[0] == '1':
        s = ''.join(list(reversed(s)))
    if t[0] == '2':
        if t[1] == '1':
            s = t[2] + s
        else:
            s = s + t[2]

print(s)

### FIXED CODE ###

s = input()
n = int(input())

t = ''
for i in range(n):
    q = input().split()
    if len(q) == 1:
        t, s = s, t
    elif len(q) == 3:
        if q[1] == '1':
            t += q[2]
        elif q[1] == '2':
            s += q[2]

t = t[::-1]
print(t + s)
### BUGGY CODE ###

A,B,K = [int(x) for x in input().split()]
c = [i for i in range(A,B+1)]
d = c[:K]
d+=c[-K:]
d = list(set(d))
d.sort()
print(*d)

### FIXED CODE ###

A,B,K = [int(x) for x in input().split()]
if B-A<K:
  c = [i for i in range(A,B+1)]
  print(*c)
  exit()
c = [i for i in range(A,A+K)]
d = [i for i in range(B-K+1,B+1)]
d =c+d
d = list(set(d))
d.sort()
print(*d)
### BUGGY CODE ###

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    def popcounter(n):
        cnt = 0
        if n == 0:
            return 0
        for _ in range(INF):
            tmp = bin(n).count("1")
            n = n % tmp
            cnt += 1
            if n == 0:
                return cnt

    n = ni()
    x = sys.stdin.readline()
    x_1 = x.count("1")

    num = int(x, 2)
    num1 = num % (x_1 - 1) if x_1 - 1 > 0 else 0
    num0 = num % (x_1 + 1)

    ans = []
    for i in range(n):
        if x[n - 1 - i] == "1":
            if x_1 - 1 < 1:
                ans.append(0)
                continue
            else:
                tmp_n = (num1 - pow(2, i)) % (x_1 - 1)
        else:
            tmp_n = (num0 + pow(2, i)) % (x_1 + 1)
        ans.append(popcounter(tmp_n) + 1)

    l = len(ans)
    for i in range(l - 1, -1, -1):
        print(ans[i])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    def popcounter(n):
        cnt = 0
        if n == 0:
            return 0
        for _ in range(INF):
            tmp = bin(n).count("1")
            n = n % tmp
            cnt += 1
            if n == 0:
                return cnt

    n = ni()
    x = sys.stdin.readline()
    x_1 = x.count("1")

    num = int(x, 2)
    num1 = num % (x_1 - 1) if x_1 - 1 > 0 else 0
    num0 = num % (x_1 + 1)

    ans = []
    for i in range(n):
        if x[n - 1 - i] == "1":
            if x_1 - 1 < 1:
                ans.append(0)
                continue
            else:
                tmp_n = (num1 - pow(2, i, x_1 - 1)) % (x_1 - 1)
        else:
            tmp_n = (num0 + pow(2, i, x_1 + 1)) % (x_1 + 1)
        ans.append(popcounter(tmp_n) + 1)

    l = len(ans)
    for i in range(l - 1, -1, -1):
        print(ans[i])


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

from sys import stdin


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def mygcd(lst):
    result = lst[0]
    for x in lst[1:]:
        result = gcd(result, x)
    return result


def main():
    _ = int(stdin.readline().rstrip())
    As = [int(x) for x in stdin.readline().rstrip().split()]
    max_ = 0
    for a in As:
        tmp = As[:]
        tmp.remove(a)
        max_ = max(max_, mygcd(tmp))
    print(max_)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from functools import lru_cache
from sys import stdin


@lru_cache(maxsize=None)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def make_acc_gdbs(As):
    result = []
    tmp = 0
    for x in As:
        tmp = gcd(tmp, x)
        result.append(tmp)
    return result


def main():
    N = int(stdin.readline().rstrip())
    As = [int(x) for x in stdin.readline().rstrip().split()]
    lAs = make_acc_gdbs(As)
    rAs = make_acc_gdbs(As[::-1])[::-1]
    max_ = 0
    for i in range(N):
        left = 0 if i == 0 else lAs[i - 1]
        right = 0 if i == (N - 1) else rAs[i + 1]
        max_ = max(max_, gcd(left, right))
    print(max_)


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

N,M=map(int,input().split())
LA=list(map(int,input().split()))
LA.sort()
for m in range(M):
    B,C=map(int,input().split())
    for b in range(B):
        if LA[b]<=C:
            LA[b]=C
        else:
            break
    LA.sort()

print(sum(LA))

### FIXED CODE ###

N,M=map(int,input().split())
LA=list(map(int,input().split()))
L=[]
for i in LA:
    L.extend([[1,i]])
for m in range(M):
    B,C=map(int,input().split())
    L.extend([[B,C]])
L.sort(key=lambda _:_[1] ,reverse=True)

ans=0
n=0
x=0
while x<=N-1:
    y=0
    while y<=L[n][0]-1:
        ans+=L[n][1]
        y+=1
        x+=1
        if x==N:
            break
        else:
            pass
    n+=1

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

#coding:utf-8
import sys
import bisect
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    N = II()
    L = LMIIS()
    L.sort()
    count = 0
    for i in range(N):
        a = L[i]
        for j in range(i+1,N):
            b = L[j]
            k = j+1
            while k < N and a+b > L[k]:
                k += 1
                count += 1
    print(count)



if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys
import bisect
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    N = II()
    L = LMIIS()
    L.sort()
    count = 0
    for i in range(N):
        for j in range(i+1,N):
            a = L[i]
            b = L[j]
            l = bisect.bisect_right(L,a-b,lo=j+1)
            r = bisect.bisect_left(L,a+b,lo=j+1)
            count += max(r - l ,0)
    print(count)



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

#  =========     /\       /|    |====/|
#      |        /  \       |    |   / |
#      |       /____\      |    |  /  |
#      |      /      \     |    | /   |
#  ========= /        \  =====  |/====|  
#  code

def main():
    n , m = map(int , input().split())
    print(1 , n)
    k = 2
    diff = 1
    p = set(list(range(1 , n + 1)))
    p.remove(1)
    p.remove(n)
    m -= 1
    while m > 0:
        if k in p and diff + k + 1 in p:
            print(k , diff + k + 1)
            p.remove(k)
            p.remove(diff + k + 1)
            diff += 1
            m -= 1
        k += 1
    return

if __name__ == "__main__":
    main()

### FIXED CODE ###

#  =========     /\       /|    |====/|
#      |        /  \       |    |   / |
#      |       /____\      |    |  /  |
#      |      /      \     |    | /   |
#  ========= /        \  =====  |/====|  
#  code

def main():
    n , m = map(int , input().split())
    if n % 2 == 0:
        n -= 1
    k = (n + 1) // 2
    j = 1

    while j < k and m > 0:
        print(j , k)
        j += 1
        k -= 1
        m -= 1

    j = (n + 1) // 2 + 1
    k = n

    while j < k and m > 0:
        if k <= n:
            print(j , k)
            m -= 1
        j += 1
        k -= 1
    
    return

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

from itertools import combinations
N = int(input())
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def judgecomp(n,ans):
    lena = len(ans)
    for i in combinations(ans,min(4,lena)):
        if sum(i)+n in primes:
            return False
    return True
    
primes = primes(55555)
primes.pop(0)
ans = [2]
count = 1
suma = 2
for i in primes:
    if judgecomp(i,ans):
        ans.append(i)
        count += 1
        suma += i
    if count == N:
        break
print(*ans)


### FIXED CODE ###

N = int(input())
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
    
primes = primes(55555)
primes2 = [i for i in primes if i%5 == 1]
print(*primes2[:N])
### BUGGY CODE ###

N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
for i in range(N):
  A[i][i]=10**9+1
ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    d=float('inf')
    for k in range(N):
      if k!=i and k!=j:
        d=min(d,A[i][k]+A[k][j])
    if d > A[i][j]:
      ans+=A[i][j]
    elif d < A[i][j]:
      print(-1)
      exit()

print(ans)

### FIXED CODE ###

import numpy as np
 
N = int(input())
A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N,N)

np.fill_diagonal(A, 10**9+1)

ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    d = np.min(A[i]+A[j])
    if d > A[i][j]:
      ans+=A[i][j]
    elif d < A[i][j]:
      print(-1)
      exit()

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

from collections import deque
import copy
def solve(maze, start, end):
  memo = []
  q = deque()
  q.append([start,[]])
  ans = 0
  while q:
    cur, path = q.popleft()
    if cur == end:
      ans = path
      break
    elif cur in memo:
      continue
    else:
      memo.append(cur)
      for y, x in zip((0,0,1,-1),(1,-1,0,0)):
        if maze[cur[0]+y][cur[1]+x] == ".":
          q.append([[cur[0]+y,cur[1]+x],copy.deepcopy(path)+[cur]])
  return ans


H, W = map(int, input().split())
Maze = [["#"]*(W+2)]+[["#"]+list(input())+["#"] for _ in range(H)] + [["#"]*(W+2)]
Ans = 0
memo = [[False]*(W+2) for _ in range(H+2)]
for sy in range(1, H+1):
  for sx in range(1, W+1):
    if Maze[sy][sx] == "#":
      continue
    for ey in range(sy, H+1):
      for ex in range(1, W+1):
        if Maze[ey][ex] == "#" or memo[ey][ex]:
          continue
        P = solve(Maze, [sy, sx], [ey,ex])
        Ans = max(Ans, len(P))
        for p in P:
          memo[p[0]][p[1]] = True
print(Ans)

### FIXED CODE ###

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


def f(i, j):
    t = [[-1] * W for _ in range(H)]
    t[i][j] = 0
    q = [(i, j)]
    while q:
        y, x = q.pop(0)
        if y - 1 >= 0 and S[y - 1][x] != '#' and t[y - 1][x] == -1:
            t[y - 1][x] = t[y][x] + 1
            q.append((y - 1, x))
        if y + 1 < H and S[y + 1][x] != '#' and t[y + 1][x] == -1:
            t[y + 1][x] = t[y][x] + 1
            q.append((y + 1, x))
        if x - 1 >= 0 and S[y][x - 1] != '#' and t[y][x - 1] == -1:
            t[y][x - 1] = t[y][x] + 1
            q.append((y, x - 1))
        if x + 1 < W and S[y][x + 1] != '#' and t[y][x + 1] == -1:
            t[y][x + 1] = t[y][x] + 1
            q.append((y, x + 1))
    return max(max(tt) for tt in t)


result = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '#':
            result = max(result, f(i, j))
print(result)
### BUGGY CODE ###

import copy
h,w = map(int, input().split())
s = [list(input()) for _ in range(h)]
t = copy.deepcopy(s)
for i in range(h):
    count = 0
    for j in range(w):
        if (s[i][j]=='.'):
            count += 1
            
        else:
            for k in range(j-1,j-count-1,-1):
                s[i][k]=count
            count = 0
    for k in range(w-1,w-count-1,-1):
        s[i][k]=count
    count = 0

for i in range(w):
    count = 0
    for j in range(h):
        if (t[j][i]=='.'):
            count += 1
            
        else:
            for k in range(j-1,j-count-1,-1):
                t[k][i]=count
            count = 0
    for k in range(h-1,h-count-1,-1):
        t[k][i]=count
    count = 0

ans = 0
for i in range(h):
    for j in range(w):
        if (s[i][j]!="#"):
            if (s[i][j]+t[i][j]-1 > ans):
                ans = s[i][j]+t[i][j]-1
print(ans)

### FIXED CODE ###

h,w = map(int, input().split())
a = [list(input()) for _ in range(h)]
s = [[0]*w for i in range(h)]
for i in range(h):
    count = 0
    for j in range(w):
        if (a[i][j]=='.'):
            count += 1
            
        else:
            for k in range(j-1,j-count-1,-1):
                s[i][k]=count
            count = 0
    for k in range(w-1,w-count-1,-1):
        s[i][k]=count
    count = 0

t = [[0]*w for i in range(h)]
for i in range(w):
    count = 0
    for j in range(h):
        if (a[j][i]=='.'):
            count += 1
            
        else:
            for k in range(j-1,j-count-1,-1):
                t[k][i]=count
            count = 0
    for k in range(h-1,h-count-1,-1):
        t[k][i]=count
    count = 0

ans = 0
for i in range(h):
    for j in range(w):
        if (s[i][j]!=0):
            if (s[i][j]+t[i][j]-1 > ans):
                ans = s[i][j]+t[i][j]-1
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
H,N=map(int,input().split())

cost=[]
for _ in range(N):
    A,B=map(int,input().split())
    cost.append([A/B,A,B])
"""
mx=0
mi=10**12
ind=-1
for index,item in enumerate(cost):
    mx=max(mx,item[0])
    if mx==item[0] and mi>item[1]:
        ind=index

ans=0
temp=cost[ind][1]
ans+=H//(temp)*cost[ind][2]

H-=temp*(H//temp-1)
"""

dp=[10**12]*H
dp[0]=0
sans=10**12
for item in cost:
    for i in range(len(dp)):
        if dp[i]!=10**12:
            if i+item[1]>=H:
                sans=min(sans,dp[i]+item[2])
            else:
                dp[i+item[1]]=min(item[2]+dp[i],dp[i+item[1]])
    
print(sans)
    



### FIXED CODE ###

# coding: utf-8
# Your code here!
H,N=map(int,input().split())

cost=[]
for _ in range(N):
    A,B=map(int,input().split())
    cost.append([A/B,A,B])
"""
mx=0
mi=10**12
ind=-1
for index,item in enumerate(cost):
    mx=max(mx,item[0])
    if mx==item[0] and mi>item[1]:
        ind=index

ans=0
temp=cost[ind][1]
ans+=H//(temp)*cost[ind][2]

H-=temp*(H//temp-1)
"""

dp=[10**12]*H
dp[0]=0
sans=10**12
for item in cost:
    for i in range(len(dp)):
        if dp[i]!=10**12:
            if i+item[1]>=H:
                sans=min(sans,dp[i]+item[2])
            else:
                dp[i+item[1]]=min(item[2]+dp[i],dp[i+item[1]])
    
print(sans)