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

"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
def main():
    import sys
    sys.setrecursionlimit(20000000)
    input = sys.stdin.readline
    N = int(input())
    AB = [[]for _ in range(N+1)]
    for i in range(N-1):
        a,b,c = map(int,input().split())
        AB[a].append((b,c))
        AB[b].append((a,c))

    Q,K = map(int,input().split())

    path = {K:""}
    dp = [0]*(N+1)
    que = []
    for n,c in AB[K]:
        que.append((n,c))
    while que:
        now,cost = que.pop(0)
        path[now]=""
        dp[now]=cost
        for n,c in AB[now]:
            if n not in path:
                que.append((n,cost+c))
    for i in range(Q):
        x,y=map(int,input().split())
        print(dp[x]+dp[y])
main()

### FIXED CODE ###

"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(20000000)
    input = sys.stdin.readline
    N = int(input())
    AB = [[]for _ in range(N+1)]
    for i in range(N-1):
        a,b,c = map(int,input().split())
        AB[a].append((b,c))
        AB[b].append((a,c))

    Q,K = map(int,input().split())

    path = {K:""}
    dp = [0]*(N+1)
    que = deque()
    for n,c in AB[K]:
        que.append((n,c))
    while que:
        now,cost = que.pop()
        path[now]=""
        dp[now]=cost
        for n,c in AB[now]:
            if n not in path:
                que.append((n,cost+c))
    for i in range(Q):
        x,y=map(int,input().split())
        print(dp[x]+dp[y])
main()
### BUGGY CODE ###

N, M = map(int, input().split())
A = []

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


A.sort(reverse=True, key=lambda x: x[1])
# print(A)
ans = 0

for i in range(1, M + 1):
    for j in (A):
        if j[0] <= i:
            ans += j[1]
            A.remove([j[0], j[1]])
            # print(i, A)
            break


print(ans)


### FIXED CODE ###

import heapq as hq

N, M = map(int, input().split())
A = []

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

A.sort()
# print(A)

ans = 0
j = 0
Q = []
hq.heapify(Q)

for i in range(1, M + 1):
    while j < len(A):
        if A[j][0] <= i:
            hq.heappush(Q, A[j][1])
            # print(Q)
        else:
            break
        j += 1
    if Q:
        ans += hq.heappop(Q) * (-1)


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

n , k = map(int, input().split())
a = list(map(int,input().split()))
a.sort()

N = 1000000007

def combi(n,r,N):
    if n<r or n<0 or r<0:
        ans = 0
        return ans
    if n==r:
        ans = 1
        return ans
    r= min(r, n-r)
    ans = f[n]*rf[r]*rf[n-r]%N
    return ans

f = [0]*(10**5+1)
f[1]=1

for i in range(2,10**5+1):
    f[i] = f[i-1]*i

rf = [0]*(10**5+1)

for i in range(1,10**5+1):
    rf[i] = pow(f[i],N-2,N)

max_sum=0
min_sum=0

for i in range(k-1,n):
    max_sum+=a[i]*combi(i,k-1,N)
    max_sum%=N
for i in range(n-k+1):
    min_sum+=a[i]*combi(n-i-1,k-1,N)
    min_sum%=N
if max_sum-min_sum<0:
    max_sum+=N
print(max_sum-min_sum)


### FIXED CODE ###

n , k = map(int, input().split())
a = list(map(int,input().split()))
a.sort()

MOD = 1000000007

factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))

def combi(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD

max_sum=0
min_sum=0

for i in range(k-1,n):
    t = combi(i,k-1)
    max_sum+=a[i]*t
    max_sum%=MOD
    min_sum+=a[n-i-1]*t
    min_sum%=MOD
if max_sum-min_sum<0:
    max_sum+=MOD
print(max_sum-min_sum)
### BUGGY CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance


N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
S, T = map(int, input().split())
G2 = [[] for _ in range(N+1)]


def dfs(s, v, depth):
    if depth == 3:
        G2[s].append((v, 1))
        return
    if depth < 3:
        for u in G[v]:
            dfs(s, u, depth+1)


for i in range(1, N+1):
    dfs(i, i, 0)
dist = dijkstra(G2, N+1, S)
print(dist[T] if dist[T] != float('inf') else -1)


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
S, T = map(int, input().split())
queue = deque()
queue.append((S, 0))
visited = [[False] * 3 for _ in range(N+1)]
while queue:
    u, d = queue.popleft()
    if visited[u][d % 3]:
        continue
    visited[u][d % 3] = True
    if d % 3 == 0 and u == T:
        print(d // 3)
        exit()
    for v in G[u]:
        queue.append((v, d+1))
print(-1)
### BUGGY CODE ###

# 入力文字列
get_str = input()

# 操作回数
N = int(input())

# リバースフラグ
r_flag = 0

# 操作
for i in range(N):
    # 取得操作
    inp_cmd = input().split()
    # inp_cmd[0] = 1 ならリバースフラグ更新
    if(int(inp_cmd[0]) == 1):
        r_flag = (r_flag+1) % 2
    else:
        # inp_cmd[1]=1、かつリバースフラグなし
        # inp_cmd[1]=2、かつリバースフラグあり
        # 、先頭に文字追加
        if((int(inp_cmd[1]) == 1 and r_flag == 0) or (int(inp_cmd[1]) == 2 and r_flag == 1)):
            get_str = inp_cmd[2] + get_str
        # 上記以外は後ろに追加
        else:
            get_str = get_str + inp_cmd[2]
# リバースフラグあり
if(r_flag == 1):
    get_str = get_str[::-1]

print(get_str)

### FIXED CODE ###

# 入力文字列
get_str = list(input())

# 操作回数
N = int(input())

# リバースフラグ
r_flag = 0

left_str = []
right_str = []
# 操作
for i in range(N):
    # 取得操作
    inp_cmd = list(input().split())
    # inp_cmd[0] = 1 ならリバースフラグ更新
    if(inp_cmd[0] == '1'):
        r_flag = (r_flag+1) % 2
    else:
        # inp_cmd[1]=1、かつリバースフラグなし
        # inp_cmd[1]=2、かつリバースフラグあり
        # 先頭に文字追加
        if((inp_cmd[1] == '1' and r_flag == 0) or (inp_cmd[1] == '2' and r_flag == 1)):
            left_str.append(inp_cmd[2])
        # 上記以外は後ろに追加
        else:
            right_str.append(inp_cmd[2])

# 左文字列リストを反転
left_str = left_str[::-1]

# 文字列結合
list_str = []
list_str = left_str + get_str + right_str

# リバースフラグあり
if(r_flag == 1):
    list_str = list_str[::-1]

out_str = ''.join(list_str)
print(out_str)
### BUGGY CODE ###

N = int(input())
A = input().split()

pear = 0

for i in range(N-1, 0, -1):
  for j in range(i):
    if int(A[i]) >= (i - j):
      break
    if (i - j) == (int(A[i]) + int(A[j])):
      pear += 1
      
print(pear)

### FIXED CODE ###

N = int(input())
A = input().split()

pear = 0

i_result = {}
j_result = {}

for i in range(N):
  result = str(i + int(A[i]))
  if result in i_result:
    i_result[result] += 1
  else:
    i_result[result] = 1

for j in range(N):
  result = str(j - int(A[j]))
  if result in j_result:
    j_result[result] += 1
  else:
    j_result[result] = 1

for k in i_result.keys():
  if k in j_result:
    pear += (i_result[k] * j_result[k])
      
      
print(pear)
### BUGGY CODE ###

from collections import deque
n = int(input())
g = [[] for i in range(n)]
l = [0] * (n-1)
for i in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  l[i] = (min(a,b),max(a,b))
  g[a].append(b)
  g[b].append(a)
m = 0
for i in range(n):
  m = max(m,len(g[i]))
  mi = i
print(m)
g2 = [set() for i in range(n)]
deq = deque([mi])
vi = [0] * n
vi[mi] = 1
d = dict()
while deq:
  cur = deq.popleft()
  for i in g[cur]:
    if vi[i] == 1:
      continue
    else:
      vi[i] = 1
      deq.append(i)
      cs = g2[cur]|g2[i]
      for k in range(1,m+1):
        if k in cs:
          continue
        else:
          g2[cur].add(k)
          g2[i].add(k)
          d[(min(cur,i),max(cur,i))] = k
          break
for i in l:
  print(d[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
g = [[] for i in range(n)]
l = [0] * (n-1)
for _ in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  l[_] = (min(a,b),max(a,b))
  g[a].append(b)
  g[b].append(a)
m = 0
for _ in range(n):
  if len(g[_]) > m:
    m = len(g[_])
    mi = _
print(m)
g2 = [[] for i in range(n)]
stack = [(mi,-1)]
vi = [0] * n
vi[mi] = 1
d = dict()
while stack:
  pre,prei = stack.pop()
  c = 0
  for i in g[pre]:
    if vi[i] == 1:
      continue
    else:
      vi[i] = 1
      c += 1
      if c == prei:
        c += 1
      d[(min(pre,i),max(pre,i))] = c
      stack.append((i,c))
for i in l:
  print(d[i])
### BUGGY CODE ###

N = int(input())
AAA = sorted([int(i) for i in input().split()])
BBB = sorted([int(i) for i in input().split()])
CCC = sorted([int(i) for i in input().split()])


def binary_search(T,SSS):#スライスの値を返す。同じ値があったら右寄りに出す
    left = 0 #SSS[left]はTより真に小さい
    right = len(SSS)-1 #SSS[right]はTと同じかそれ以上

    if T<SSS[left]:
        return 0
    if T>=SSS[right]:
        return right+1

    while True:
        mid = (left+right)//2
        #print(left,mid,right)
        #print(SSS[left],SSS[mid],SSS[right])
        #print()
        if right-left==1:
            return right
        if SSS[mid]<=T:
            left = mid
        else:
            right=mid


ans = 0
for A in AAA:
    for B in BBB[binary_search(A,BBB):]:
        ans += len(CCC)-binary_search(B,CCC)

print(ans)


### FIXED CODE ###

N = int(input())
AAA = sorted([int(i) for i in input().split()])
BBB = sorted([int(i) for i in input().split()])
CCC = sorted([int(i) for i in input().split()])

def upper_bound(T,SSS):#スライスの値を返す。同じ値があったら右寄りに出す
    left = 0 #SSS[left]はTより真に小さい
    right = len(SSS)-1 #SSS[right]はTと同じかそれ以上

    if T<SSS[left]:
        return 0
    if T>=SSS[right]:
        return right+1

    while True:
        mid = (left+right)//2
        #print(left,mid,right)
        #print(SSS[left],SSS[mid],SSS[right])
        #print()
        if right-left==1:
            return right
        if SSS[mid]<=T:
            left = mid
        else:
            right = mid

def lower_bound(T,SSS):#スライスの値を返す。同じ値があったら左寄りに出す
    left = 0 #SSS[left]はTと同じかそれより小さい
    right = len(SSS)-1 #SSS[right]はTより真に大きい

    if T<=SSS[left]:
        return 0
    if T>SSS[right]:
        return right+1

    while True:
        mid = (left+right)//2
        #print(left,mid,right)
        #print(SSS[left],SSS[mid],SSS[right])
        #print()
        if right-left==1:
            return right
        if SSS[mid]<T:
            left = mid
        else:
            right = mid

ans=0
lenCCC = len(CCC)
for B in BBB:
    nA = lower_bound(B,AAA)
    nC = lenCCC-upper_bound(B,CCC)
    ans+=nA*nC
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
pis = list(map(int, input().split()))
sum_max = 0
pikmax = []
for i in range(n-k+1):
  pik = pis[i:i+k]
  sumk = sum(pik)
  if sumk > sum_max:
    sum_max = sumk
    pikmax.append(pik)
expect = 0
expect += sum_max/2 + k / 2
print(expect)

### FIXED CODE ###

n, k = map(int, input().split())
pis = list(map(int, input().split()))
sum_max = 0
sum_cd = 0
for i in range(k):
  sum_max += pis[i]
  sum_cd += pis[i]
for j in range(1,n-k+1):
  sum_cd -= pis[j-1]
  sum_cd += pis[j+k-1] 
  if sum_cd > sum_max:
    sum_max = sum_cd
expect = sum_max/2 + k / 2
print(expect)
### BUGGY CODE ###

from math import sqrt
from decimal import *

a, b, c = map(int, input().split())
getcontext().prec = 100000
if (Decimal(a).sqrt() + Decimal(b).sqrt() < Decimal(c).sqrt()): print('Yes')
else: print('No')


### FIXED CODE ###

from math import sqrt
a, b, c = map(int, input().split())
l = (a ** 2) + (b ** 2) + (c ** 2)
r = 2 * (a * b + b * c + c * a)

if (c-a-b > 0 and l > r): print('Yes')
elif(sqrt(c) == sqrt(a) + sqrt(b)): print('No')
else: print('No')
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for _ in range(M):
  bc = list(map(int, input().split()))
  A.extend([bc[1]] * bc[0])
A = sorted(A, reverse=True)
print(sum(A[:N]))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for _ in range(M):
  BC.append(list(map(int, input().split())))
BC = sorted(BC, key=lambda x:x[1],reverse=True)  
for b, c in BC:
  A.extend([c] * b)
  if len(A)>=2*N:
    break
A = sorted(A, reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

N,s = input().split()
S = int(s)
a = []
for i in range(int(N)):
    a.append(int(input()))

a.sort()

mindiff = 1000000000

for i in range(int(N)-(S - 1)):
    v = 0
    for j in range(int(S)-1):
        v += a[i+j+1]-a[i+j]
        if i%3 == 0 and mindiff < v:break

    if mindiff > v: mindiff = v

print(mindiff)



### FIXED CODE ###

N,s = input().split()
S = int(s)
a = []
for i in range(int(N)):
    a.append(int(input()))

a.sort()

mindiff = 1000000000

for i in range(int(N)-(S - 1)):
    v = a[i+S-1]-a[i]

    if mindiff > v: mindiff = v

print(mindiff)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

from collections import Counter
import bisect
import numpy as np

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l = np.sort(l)
m = np.cumsum(l)
p = m[-1]

maximum_operation = [0] * N

ll = []
for x in range(1, N+1):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = m[a-1] 
    ll.append((b + c)/x)
ll = np.sort(ll)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

#output
from collections import Counter
import bisect

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
p = sum(l)

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = sum(l[0:a]) 
    ll.append((b + c)/x)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)
### BUGGY CODE ###

n = input()
a = [int(i) for i in input().split()]
q = int(input())
bb = []
cc = []
for i in range(q):
    btmp, ctmp = [int(j) for j in input().split()]
    bb.append(btmp)
    cc.append(ctmp)



atol = sum(a)
for b,c in zip(bb,cc):
    
    count = len([ i for i in a  if i == b])
    a = [ c if b == i else i for i in a ]
    atol +=  (c - b) * count
    print(atol)


### FIXED CODE ###

n = input()
a = [int(i) for i in input().split()]
q = int(input())
bb = []
cc = []
for i in range(q):
    btmp, ctmp = [int(j) for j in input().split()]
    bb.append(btmp)
    cc.append(ctmp)


amap = {}
for i in a :
    if i not in amap :
        amap[i] = 1
    else:
        amap[i] += 1

atol = sum(a)

for b,c in zip(bb,cc):
    
    if b in amap:
        atol +=  (c - b) * amap[b]
    
        if c in amap :
            amap[c] += amap[b]
        else:
            amap[c] = amap[b]
        
        amap.pop(b)
        
    print(atol)
### BUGGY CODE ###

def f():
  N,M=map(int,input().split())
  *A,=map(int,input().split())
  l=[]
  for a in A:
      k=a
      while k>=1:
          l+=[k-k//2]
          k=k//2
  print(sum(A)-sum(sorted(l)[-M:]))
if __name__=="__main__":
  f()

### FIXED CODE ###

def f():
  N,M=map(int,input().split())
  *A,=map(int,input().split())
  l=[]
  for a in A:
      k=a
      while k>=1:
          l+=[k-k//2]
          k=k//2
  print(sum(A)-sum(sorted(l)[-M:]))
if __name__=="__main__":
  f()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

L,R=map(int, input().split())

ans = 2 * (10**9)

for i in range(L,R+1):
    for j in range(i+1,R+1):
        ans = min(ans, ((i%2019)*(j%2019)%2019))

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-

L,R=map(int, input().split())

ans = 2 * (10**9)

for i in range(L,min(R+1,L+2019)):
    for j in range(i+1,min(R+1,L+2019)):
        ans = min(ans, ((i%2019)*(j%2019)%2019))

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

# encoding: utf-8
N, K = map(int, input().split())
h = list(map(int, input().split()))

def mysub(a, b): return a - b if a > b else b - a

import heapq

pq = []
d = [0] * N
prev = [None] * N

heapq.heappush(pq, (0, 0))
for i in range(1, N): d[i] = 10 ** 9 + 7

while len(pq) > 0:
    Qu, u = heapq.heappop(pq)
    if Qu > d[u]: continue
    for i in range(1, min(K + 1, N - u)):
        v = u + i
        cost = mysub(h[u], h[v])
        if Qu + cost < d[v]:
            d[v] = Qu + cost
            heapq.heappush(pq, (Qu + cost, v))
            prev[v] = u

print(d[-1])

### FIXED CODE ###

# encoding: utf-8
N, K = map(int, input().split())
h = list(map(int, input().split()))
 
def mysub(a, b): return a - b if a > b else b - a
 
import heapq
 
pq = []
d = [0] * N
prev = [None] * N
 
heapq.heappush(pq, (0, 0))
for i in range(1, N): d[i] = 10 ** 9 + 7
 
while len(pq) > 0:
    Qu, u = heapq.heappop(pq)
    if Qu > d[u]: continue
    for i in range(1, min(K + 1, N - u)):
        v = u + i
        cost = mysub(h[u], h[v])
        if Qu + cost < d[v]:
            d[v] = Qu + cost
            heapq.heappush(pq, (Qu + cost, v))
            prev[v] = u
 
print(d[-1])
### BUGGY CODE ###

n = int(input())

res = 1

a = list(map(int, input().split()))

for i in range(n):
    res *= a[i]


if (res > 1000000000000000000):
    res = -1

print(res)

### FIXED CODE ###

n = int(input())

res = 1

a = list(map(int, input().split()))

for i in a:
    res *= i
    
    if (res > 1000000000000000000):
        res = -1
        break
        

if res == -1:
    for i in a:
        if i == 0:
            res = 0
            break

print(res)
### BUGGY CODE ###

import sys

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

input = sys.stdin.readline

N, M = map(int, input().split())
relations = []
for _ in range(M):
    a, b = map(int, input().split())
    relations.append((a-1, b-1))

uf = UnionFind(N)
for a, b in relations:
    uf.union(a, b)

max_n = 0
for i in range(uf.group_count()):
    max_n = max(max_n, len(uf.members(i)))

print(max_n)

### FIXED CODE ###

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
relations = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    relations[a].append(b)
    relations[b].append(a)

ans = 0
visited = set()
for i in range(N):
    q = deque()
    q.append(i)
    start = len(visited)
    while q:
        pos = q.popleft()
        if pos in visited:
            continue
        visited.add(pos)
        for n_pos in relations[pos]:
            if n_pos in visited:
                continue
            q.appendleft(n_pos)
    end = len(visited)
    ans = max(ans, end - start)

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

from collections import deque
from numba import jit


@jit
def BFS():
    point=0
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[0 for _ in range(w)] for _ in range(h)]

    queue=deque([])
    for i in range(h):
        for j in range(w):
            if A[i][j]=="#":
                color[i][j]="gray"
                queue.append([i,j])
                D[i][j]=0

    while len(queue)>0:
        x,y=queue.popleft()
        for a,b in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=x+a,y+b
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]=="white":
                    color[X][Y]="gray"
                    D[X][Y]=D[x][y]+1
                    point=max(point,D[X][Y])
                    queue.append([X,Y])
        color[x][y]="black"

    return point


h,w=map(int,input().split())
A=[list(input()) for _ in range(h)]
print(BFS())

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)
inf=10**7


def BFS():
    color=[["white" for _ in range(w+2)] for _ in range(h+2)]
    D=[[inf for _ in range(w+2)] for _ in range(h+2)]

    queue=deque([])
    for i in range(1,h+1):
        for j in range(1,w+1):
            if A[i][j]=="#":
                queue.append([i,j])
                D[i][j]=0
                color[i][j]="gray"

    cnt=0
    while len(queue)!=0:
        a,b=queue.popleft()
        for c,d in ((1,0),(0,1),(-1,0),(0,-1)):
            X,Y=a+c,b+d
            if A[X][Y]=="." and color[X][Y]=="white":
                color[X][Y]="gray"
                D[X][Y]=D[a][b]+1
                cnt=max(cnt,D[X][Y])
                queue.append([X,Y])
        color[a][b]="black"

    return cnt


h,w=map(int,input().split())
A=[["#"]+list(input())+["#"] for _ in range(h)]
A.insert(0,["#"]*(w+2))
A.append(["#"]*(w+2))
print(BFS())
### BUGGY CODE ###

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

base_2_cnt = [0]*60 
for a in al:
    for i in range(60):
        if ((a >> i) & 1): base_2_cnt[i] += 1

ans = 0
for i in range(60):
    base_01_comb = base_2_cnt[i] * (n-base_2_cnt[i])
    ans += base_01_comb * (2**i)
    ans %= 10**9+7

print(ans%(10**9+7))

### FIXED CODE ###

def main():
    MOD = 10**9+7
    n = int(input())
    al = list(map(int, input().split()))

    base_2_cnt = [0]*60 
    for a in al:
        for i in range(60):
            if ((a >> i) & 1): base_2_cnt[i] += 1

    ans = 0
    curr_2 = 1
    for i in range(60):
        base_01_comb = base_2_cnt[i] * (n-base_2_cnt[i])
        ans += base_01_comb * curr_2
        ans %= MOD
        curr_2*=2
        curr_2%=MOD

    print(ans%MOD)

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

n, m = list(map(int, input().split()))
job_r = [[] for _ in range(m)]

for i in range(n):
    d, r = list(map(int, input().split()))
    if d-1 < m:
        job_r[d-1].append(r)

total_reward = 0
aaa_list = []
for i in range(m):
    aaa_list.extend(job_r[i])
    if len(aaa_list) >0:
        reward = max(aaa_list)
        total_reward += reward
        aaa_list.remove(reward)
print(total_reward)

### FIXED CODE ###

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

hq = []
ans, j = 0, 0

for i in range(1, M + 1):  # M - i 日後にするバイトを考える
    while (j < N) and (X[j][0] <= i):
        heappush(hq, -X[j][1])  # 候補の追加
        j += 1
    if len(hq):
        ans += -heappop(hq)  # 候補があるとき、候補から最大値を取り出す

print(ans)