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


MOD = 10**9 + 7
S = input()

if len(S) % 3 == 1:
    S = '00' + S
elif len(S) % 3 == 2:
    S = '0' + S

L = (len(S) // 3)
dp = [[0 for i in range(14)] for j in range(L + 1)]
# print(rec(S, 0, 0) % MOD)
# print(memo)

dp[0][0] = 1

for k in range(L):
    for m in range(13):
        s = S[k*3:k*3+3]
        d1 = [i for i in range(10)] if s[0] == '?' else [int(s[0])]
        d2 = [i for i in range(10)] if s[1] == '?' else [int(s[1])]
        d3 = [i for i in range(10)] if s[2] == '?' else [int(s[2])]

        for i1 in d1:
            for i2 in d2:
                for i3 in d3:
                    num = 100 * i1 + 10 * i2 + i3
                    dp[k + 1][(13 + num - m) % 13] += dp[k][m]

        for i in range(13):
            dp[k+1][i] %= MOD

print(dp[L][5])


### FIXED CODE ###

MOD = 10**9 + 7

S = input()
L = len(S)
memo = [[0 for i in range(14)] for j in range(L + 1)]
dp = [[0 for i in range(14)] for j in range(L + 1)]

dp[0][0] = 1

for k in range(L):
    for m in range(13):
        if S[k] == '?':
            for i in range(10):
                dp[k + 1][(m * 10 + i) % 13] += dp[k][m]
        else:
            dp[k + 1][(m * 10 + int(S[k])) % 13] += dp[k][m]

        for i in range(13):
            dp[k+1][i] %= MOD

print(dp[L][5])
### BUGGY CODE ###

import math

Q = int(input())
LR = []

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    # print(int(math.sqrt(n)))
    for i in range(2,int(math.sqrt(n))+1):
        for j in range(i*2, n+1 ,i):
            is_prime[j] = False

    return is_prime

def like2017(is_prime,n):
    solve = [False] * (n+1)
    for i in range(3,n+1,2):
        if i < n and i >2:
            solve[i] = is_prime[i] and is_prime[int((i+1)/2)]

    return solve

for _ in range(Q):
    t = [int(i) for i in input().split(' ')]
    LR.append(t)

L = 10**5 
is_prime = primes(L)
solve = like2017(is_prime,L)
for l, r in LR:
    # print(solve[l:r+1])
    print(solve[l:r+1].count(True))


### FIXED CODE ###

import math
from itertools import accumulate

Q = int(input())
LR = []

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    # print(int(math.sqrt(n)))
    for i in range(2,int(math.sqrt(n))+1):
        for j in range(i*2, n+1 ,i):
            is_prime[j] = False

    return is_prime

def like2017(is_prime,n):
    solve = [0] * (n+1)
    for i in range(3,n+1,2):
        if is_prime[i] and is_prime[int((i+1)/2)]:
            solve[i] = 1
        
    return solve

for _ in range(Q):
    t = [int(i) for i in input().split(' ')]
    LR.append(t)

L = 10 ** 5
is_prime = primes(L)
solve = like2017(is_prime,L)
# print(solve)
ans = list(accumulate(solve))
# print(ans)

for l, r in LR:
    print(ans[r] - ans[l-1])
### BUGGY CODE ###

l=list(map(int,input().split()))
x=l[0]
k=l[1]
d=l[2]
x1=abs(x)
cou=0
while x1>0:
  x1-=d
  cou+=1
if k<cou:
  x2=abs(x)-k*d
  print(x2)
  # if x<=0:
  #   x3=x2*(-1)
  #   print(x3)
  # else:
  #   print(x2)

else:
  a=cou%2
  b=k%2
  x4=x1*(-1)
  if a==b:
    print(abs(x1))
  if a!=b:
    print(x1+d)


### FIXED CODE ###

l=list(map(int,input().split()))
x=l[0]
k=l[1]
d=l[2]
x1=abs(x)

cou=x1//d
cou+=1
x1=x1-d*cou
# while x1>0:
#   x1-=d
#   cou+=1
if k<cou:
  x2=abs(x)-k*d
  print(x2)


else:
  a=cou%2
  b=k%2
  x4=x1*(-1)
  if a==b:
    print(abs(x1))
  if a!=b:
    print(x1+d)
### BUGGY CODE ###

from collections import deque
n,m = map(int,input().split())
to = [[] for _ in range(n)]
v = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    v.append((a,b))
ans = m
seen = [False]*n
stk = deque()
for i in range(m):
    a,b = v[i]
    stk.clear()
    stk.append((a,-1))
    for j in range(n): seen[j] = False
    seen[a] = True
    flag = True
    while stk and flag:
        cur,prev = stk.pop()
        for nxt in to[cur]:
            if nxt == b:
                if cur == a: continue
                ans -= 1
                flag = False
                break
            if nxt == prev: continue
            if seen[nxt]: continue
            stk.append((nxt,cur))

print(ans)

### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
to = [[] for _ in range(n)]
v = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    v.append((a,b))
ans = m
seen = [False]*n
stk = deque()
for i in range(m):
    a,b = v[i]
    stk.clear()
    stk.append((a,-1))
    for j in range(n): seen[j] = False
    seen[a] = True
    flag = True
    while stk and flag:
        cur,prev = stk.pop()
        seen[cur] = True
        for nxt in to[cur]:
            if nxt == b:
                if cur == a: continue
                ans -= 1
                flag = False
                break
            if nxt == prev: continue
            if seen[nxt]: continue
            stk.append((nxt,cur))

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

#Grid Repainting
from collections import deque
import sys
h,w=map(int,input().split())
field=[list(input()) for _ in range(h)]
white=0
for i in range(h):
    for j in range(w):
        if field[i][j]==".":
            white+=1
start=[0,0]
goal=[h-1,w-1]
dx=[1,0,-1,0]
dy=[0,1,0,-1]
count=0
que=deque([[[0,0]]])
field[0][0]="#"
while que:
    q=que.popleft()
    count+=1
    k=[]
    while q:
        p=q.pop()
        x=p[0]
        y=p[1]
        if x==h-1 and y==w-1:
            break
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx and nx<h and 0<=ny and ny<w:
                if field[nx][ny]!="#":
                    k.append([nx,ny])
                    field[nx][ny]="#"
    else:
        que.append(k)
        continue
    break
else:
    print(-1)
    sys.exit()
print(white-count)

### FIXED CODE ###

#Grid Repainting
from collections import deque
import sys
h,w=map(int,input().split())
field=[list(input()) for _ in range(h)]
white=0
for i in range(h):
    for j in range(w):
        if field[i][j]==".":
            white+=1
start=[0,0]
goal=[h-1,w-1]
dx=[1,0,-1,0]
dy=[0,1,0,-1]
count=0
que=deque([[[0,0]]])
field[0][0]="#"
while que:
    q=que.popleft()
    count+=1
    k=[]
    while q:
        p=q.pop()
        x=p[0]
        y=p[1]
        if x==h-1 and y==w-1:
            break
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx and nx<h and 0<=ny and ny<w:
                if field[nx][ny]!="#":
                    k.append([nx,ny])
                    field[nx][ny]="#"
    else:
        if k:
            que.append(k)
        continue
    break
else:
    print(-1)
    sys.exit()
print(white-count)
### BUGGY CODE ###

INF = 10 ** 10

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

dp = [INF for _ in range(N)]
dp[0] = 0
# 0-indexed

for i in range(1, N):
    for k in range(1, K + 1):
        if i - k >= 0:
            dp[i] = min(dp[i], dp[i - k] + abs(h[i] - h[i - k]))

print(dp[N - 1])


### FIXED CODE ###

INF = 10 ** 10

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

dp = [INF for _ in range(N)]
dp[0] = 0
# 0-indexed

for i in range(1, N):
    for k in range(1, K + 1):
        if i - k >= 0:
            dp[i] = min(dp[i], dp[i - k] + abs(h[i] - h[i - k]))

print(dp[N - 1])
### BUGGY CODE ###

N = int(input())

count = 0
for i in range(N):
    count += i
    
print(count)


### FIXED CODE ###

N = int(input())

count = 0

#for i in range(N):
#    count += i

count = N*(N-1)//2

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

from collections import deque
import sys
sys.setrecursionlimit(10**9)
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
q=deque([0])
v=[0]*n
v[0]=1
gp=[[] for i in range(n)]
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==0:
            v[i]=1
            gp[p].append(i)
            q.append(i)
MOD=10**9+7
flag=[0]*n
dp=[[0,0] for i in range(n)]
def f(i):
    if flag[i]:
        return 0
    flag[i]=1
    dp[i][0]=1
    dp[i][1]=1
    for j in gp[i]:
        f(j)
        dp[i][0]=dp[i][0]*(dp[j][0]+dp[j][1])%MOD
        dp[i][1]=dp[i][1]*dp[j][0]
        dp[i][0]%=MOD
        dp[i][1]%=MOD
    return 0
f(0)
print((dp[0][0]+dp[0][1])%MOD)


### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**9)
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
q=deque([0])
v=[0]*n
v[0]=1
gp=[[] for i in range(n)]
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==0:
            v[i]=1
            gp[p].append(i)
            q.append(i)
MOD=10**9+7
flag=[0]*n
dp=[[0,0] for i in range(n)]
def f(i):
    if flag[i]:
        return 0
    flag[i]=1
    dp[i][0]=1
    dp[i][1]=1
    for j in gp[i]:
        f(j)
        dp[i][0]=dp[i][0]*(dp[j][0]+dp[j][1])%MOD
        dp[i][1]=dp[i][1]*dp[j][0]
        dp[i][0]%=MOD
        dp[i][1]%=MOD
    return 0
f(0)
print((dp[0][0]+dp[0][1])%MOD)
### BUGGY CODE ###

#

import sys
input=sys.stdin.readline

kl=set()

def pf(n):
    ret={}
    for i in range(2,int((n)**0.5)+1):
        if n%i==0:
            cnt=0
            while(n%i==0):
                n/=i
                cnt+=1
            ret[i]=cnt
            kl.add(i)
    if n!=1:
        ret[int(n)]=1
        kl.add(int(n))
    return ret
            
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    p=[{} for i in range(N)]
    for i in range(N):
        p[i]=(pf(A[i]))
    lcm=1
    for i in kl:
        maxipow=0
        for j in range(N):
            maxipow=max(maxipow,p[j].get(i,0))
        lcm*=i**maxipow
    MOD=10**9+7
    lcm%=MOD
    ans=0
    for i in range(N):
        ans+=lcm*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()


### FIXED CODE ###

#

import sys
from fractions import gcd
input=sys.stdin.readline

def main():
    MOD=10**9+7
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    l=(A[0]*A[1])//gcd(A[0],A[1])
    for i in range(2,N):
        l=(l*A[i])//gcd(A[i],l-A[i])
    l%=MOD
    ans=0
    for i in range(N):
        ans+=l*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

class UF():
  def __init__(self, N):
    self.parents = [ i for i in range(N+1) ]

  def union(self, f, t):
    p1 = self.find(f)
    p2 = self.find(t)

    if p1 == p2:
      return

    self.parents[p2] = p1

  def find(self, node):
    if self.parents[node] == node:
      return node
    else:
      return self.find(self.parents[node])

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

for _ in range(M):
  x,y = map(int, input().split())
  uf.union(x,y)

res = 0
for i in range(N):
  if uf.find(i+1) == uf.find(p[i]):
    res += 1

print(res)

### FIXED CODE ###

class UF():
  def __init__(self, N):
    self.parents = [-1] * (N+1)

  def union(self, f, t):
    p1 = self.find(f)
    p2 = self.find(t)
    if p1 == p2:
      return

    if self.parents[p1] > self.parents[p2]:
      p1,p2 = p2,p1
    self.parents[p1] += self.parents[p2]
    self.parents[p2] = p1

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

  def same(self, n1, n2):
    return self.find(n1) == self.find(n2)

N,M = map(int, input().split())
p = list(map(int, input().split()))
uf = UF(N)
xy = [ list(map(int, input().split())) for _ in range(M) ]

# for _ in range(M):
#   x,y = map(int, input().split())
#   uf.union(x,y)
for x,y in xy:
  uf.union(x,y)

res = 0
for i in range(N):
  if i+1 == p[i] or uf.same(i+1, p[i]):
    res += 1

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

n,k = map(int,input().split())
a = list(map(int,input().split()))
x = 1
for i in range(n):
    if i<k:
        x *= a[i]
    else:
        c = x//a[i-k]*a[i]
        print('Yes' if c>x else 'No')
        x = c

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n):
    if i>=k:
        print('Yes' if a[i-k]<a[i] else 'No')
### BUGGY CODE ###

from scipy.sparse.csgraph import csgraph_from_dense,dijkstra
from numpy.linalg import norm
from numpy import array
xs, ys, xt, yt = map(int, input().split())
N = int(input())
p=[(xs, ys, 0), (xt, yt, 0)]
edge = [[-1]*(N+2) for _ in range(N+2)]
edge[0][1] = edge[1][0] = norm(array([xs-xt, ys-yt]))
for i in range(N):
    x, y, r = map(int, input().split())
    for j in range(len(p)):
        x1, y1, r1 = p[j]
        edge[i+2][j] = edge[j][i+2] = max(norm(array([x-x1, y-y1]))-r-r1, 0.0)
    p.append((x, y, r))
G = csgraph_from_dense(edge,null_value=-1)  
print(dijkstra(G,indices=0)[1])   

### FIXED CODE ###

from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

xs, ys, xt, yt = map(int, input().split())
n = int(input())

p = [(xs,ys,0),(xt,yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
edge = [[-1]*(n+2)for i in range(n+2)]
 
for i in range(n+2):
    for j in range(i+1,n+2):
        edge[i][j] = edge[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0.0)

#ここから
G = csgraph_from_dense(edge,null_value=-1)
print(dijkstra(G,indices=0)[1])
### BUGGY CODE ###

s=list(str(input()))
b=0
while len(s)>=5:
  if s[-1]=='r' and len(s)>=7:
    sd=[s[-7],s[-6],s[-5],s[-4],s[-3],s[-2],s[-1]]
    se=[s[-6],s[-5],s[-4],s[-3],s[-2],s[-1]]
    if ''.join(sd)=='dreamer':
      del s[-7:]
    elif ''.join(se)=='eraser':
      del s[-6:]
    else:
      print('NO')
      b+=1
      break
  elif len(s)==6:
    if ''.join(s)=='eraser':
      print('YES')
    else:
      print('NO')
      b+=1
      break
  elif s[-1]=='m':
    sd=[s[-5],s[-4],s[-3],s[-2],s[-1]]
    if ''.join(sd)=='dream':
      del s[-5:]
    else:
      print('NO')
      b+=1
      break
  elif s[-1]=='e':
    sd=[s[-5],s[-4],s[-3],s[-2],s[-1]]
    if ''.join(sd)=='erase':
      del s[-5:]
    else:
      print('NO')
      b+=1
      break  
  else:
    print('NO')
    b+=1
    break
if len(s)==0:
  print('YES')
elif b!=1:
  print('NO')

### FIXED CODE ###

s=list(str(input()))
b=0
while len(s)>=7:
  if s[-1]=='r':
    sd=[s[-7],s[-6],s[-5],s[-4],s[-3],s[-2],s[-1]]
    se=[s[-6],s[-5],s[-4],s[-3],s[-2],s[-1]]
    if ''.join(sd)=='dreamer':
      del s[-7:]
    elif ''.join(se)=='eraser':
      del s[-6:]
    else:
      print('NO')
      b+=1
      break
  elif s[-1]=='m':
    sd=[s[-5],s[-4],s[-3],s[-2],s[-1]]
    if ''.join(sd)=='dream':
      del s[-5:]
    else:
      print('NO')
      b+=1
      break
  elif s[-1]=='e':
    sd=[s[-5],s[-4],s[-3],s[-2],s[-1]]
    if ''.join(sd)=='erase':
      del s[-5:]
    else:
      print('NO')
      b+=1
      break  
  else:
    print('NO')
    b+=1
    break
if len(s)==0 or (len(s)==6 and ''.join(s)=='eraser') or (len(s)==5 and ''.join(s)=='dream') or (len(s)==5 and ''.join(s)=='erase'):
  print('YES') 
elif b!=1:
  print('NO')
### BUGGY CODE ###

Q = int(input())
INF = 10 ** 9

queries = []
for _ in range(Q):
    queries.append(input())

from bisect import insort_left

ary, absum, bsum, c = [], 0, 0, 0
left, right = -INF, INF
for query in queries:
    if query[0] == '2':
        # absum = sum(abs(a - ary[(c-1)//2]) for a in ary)
        # absum = asum - (c//2 + 1) * ary[(c-1)//2]
        # print(' '.join(map(str, (ary[(c-1)//2], absum + bsum))))
        print(str(ary[(c-1)//2]) + ' ' + str(absum + bsum))
    else:
        _, a, b = map(int, query.split())
        insort_left(ary, a)
        c += 1
        if left <= a <= right:
            absum += 0
        elif a < left:
            absum += left - a
        else:
            absum += a - right
        left, right = ary[(c-1)//2], ary[c - (c-1)//2 - 1]        
        bsum += b


### FIXED CODE ###

Q = int(input())
INF = 10 ** 9

queries = []
for _ in range(Q):
    queries.append(input())

from bisect import insort_left
from heapq import heappush, heappop

absum, bsum, c = 0, 0, 0
# left, right = -INF, INF
lefts, rights = [INF], [INF]
for query in queries:
    if query[0] == '2':
        # absum = sum(abs(a - ary[(c-1)//2]) for a in ary)
        # absum = asum - (c//2 + 1) * ary[(c-1)//2]
        # print(' '.join(map(str, (ary[(c-1)//2], absum + bsum))))
        # print(str(ary[(c-1)//2]) + ' ' + str(absum + bsum))
        print(-lefts[0], absum + bsum)
    else:
        _, a, b = map(int, query.split())
        if c % 2 == 0:
            if -lefts[0] <= a <= rights[0]:
                heappush(lefts, -a)
                heappush(rights, a)
                absum += 0
            elif a < -lefts[0]:
                heappush(lefts, -a)
                heappush(rights, -lefts[0])
                absum += -lefts[0] - a
            else:
                heappush(rights, a)
                heappush(lefts, -rights[0])
                absum += a - rights[0]
        else:
            if a < -lefts[0]:
                absum += -lefts[0] - a
                heappop(lefts)
                heappush(lefts, -a)
            else:
                absum += a - rights[0]
                heappop(rights)
                heappush(rights, a)
        # left, right = ary[(c-1)//2], ary[c - (c-1)//2 - 1]        
        bsum += b
        c += 1
### BUGGY CODE ###

import re
N, Q = map(int, input().split())
S = input()
qs = [tuple(map(int, input().split())) for _ in range(Q)]

# print(qs)

regex =  re.compile('AC')
for q in qs:
    # print(q)
    print(len(regex.findall(S[q[0]-1:q[1]])))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
query = [list(map(int,input().split())) for _ in range(Q)]

cum_sum = [0,0]
tmp = 0
for i in range(1,N):
    if S[i-1] == "A" and S[i] == "C":
        tmp += 1
    cum_sum.append(tmp)
# print(cum_sum)

for q in query:
    print(cum_sum[q[1]] - cum_sum[q[0]])
### BUGGY CODE ###

from collections import defaultdict
import heapq
import sys


        
def dijkstra(startvertex,V,graph):
    distances=[sys.maxsize]*V
    distances[startvertex]=0
    heap=[(0,startvertex)]
    while heap:
        current_distance,current_vertex=heapq.heappop(heap)
        if current_distance>distances[current_vertex]:
            continue
        for neighbor in range(len(graph[current_vertex])):
            if graph[current_vertex][neighbor]>0:
                distance=current_distance+graph[current_vertex][neighbor]
                
                
                if distance<distances[neighbor]:
                    distances[neighbor]=distance
                    heapq.heappush(heap,(distance,neighbor))
                    
    return distances
n=int(input())            
    
graph=[[0 for i in range(n)]for j in range(n)]
for i in range(n-1):
    a=[int(x) for x in input().split()]
    # print(a)
    graph[a[0]-1][a[1]-1]=a[2]
    graph[a[1]-1][a[0]-1]=a[2]

# print(graph)
w=[int(x) for x in input().split()]
m=dijkstra(w[1]-1,n,graph)
# print(m)
c=0
for i in range(w[0]):
    s=[int(x) for x in input().split()]
    # print(s)
    c=abs(m[s[0]-1])+abs(m[s[1]-1])
    print(c)

### FIXED CODE ###

N=int(input())
import sys
sys.setrecursionlimit(10**6)
T=[[] for _ in range(N)]
for i in range(N-1):
    a,b,c=map(int, input().split())
    T[a-1].append((b-1,c))
    T[b-1].append((a-1,c))

Q,K=map(int, input().split())
D=[-1]*N
D[K-1]=0
def dfs(start, nowd):
    to=T[start]
    for t in to:
        next_node,c=t
        if D[next_node]!=-1:
            continue
        nextd=nowd+c
        D[next_node]=nextd
        dfs(next_node, nextd)
dfs(K-1,0)
# print(D)
for i in range(Q):
    x,y=map(int, input().split())
    print(D[x-1]+D[y-1])
### BUGGY CODE ###

import math
import queue

mod = 1e9+7

def swap(a,b):
    return (b,a)

def gcd(a,b):
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def divisors(a):
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def main():
    n,m = map(int,input().split())
    a = [x for x in map(int,input().split())]
    for i in range(m):
        id = a.index(max(a))
        a[id] //= 2
    print(sum(a))
    return

if __name__ == '__main__':
    main()

### FIXED CODE ###

import math
import queue
import bisect
import heapq

mod = 1e9+7

def swap(a,b):
    return (b,a)

def gcd(a,b):
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def divisors(a):
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def main():
    n,m = map(int,input().split())
    a = [-x for x in map(int,input().split())]
    heapq.heapify(a)
    for i in range(m):
        x = heapq.heappop(a)
        if x%2==0:
            heapq.heappush(a,x//2)
        else:
            heapq.heappush(a,x//2+1)
    ans = 0
    for i in range(n):
        ans += heapq.heappop(a)*(-1)
    print(ans)
    return

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

# coding: utf-8
# Your code here!

from collections import deque

H, W = map(int, input().rstrip().split(' '))

field = []
for _ in range(H):
    temp_field = []
    for s in input():
        if s == '.':
            temp_field.append(0)
        else:
            temp_field.append(1)
    field.append(temp_field)

dp = [[H + W] * W for _ in range(H)]
dp2 = [[False] * W for _ in range(H)]
lists = deque()
for i in range(H):
    for j in range(W):
        if field[i][j] == 1:
            dp[i][j] = 0
            dp2[i][j] = True
            if i > 0:
                lists.append([i-1, j])
            if i < H - 1:
                lists.append([i+1, j])
            if j > 0:
                lists.append([i, j-1])
            if j < W - 1:
                lists.append([i, j+1])
           
count = 0
while True:
    if len(lists) == 0:
        break
    
    i, j = lists.popleft()
    if dp2[i][j] == True:
        continue
    else:
        dp2[i][j] = True
        
        min_dist = H + W
        if i > 0:
            min_dist = min(min_dist, dp[i-1][j] + 1)
            if dp2[i-1][j] == False:
                lists.append([i-1, j])
        if i < H - 1:
            min_dist = min(min_dist, dp[i+1][j] + 1)
            if dp2[i+1][j] == False:
                lists.append([i+1, j])
        if j > 0:
            min_dist = min(min_dist, dp[i][j-1] + 1)
            if dp2[i][j-1] == False:
                lists.append([i, j-1])
        if j < W - 1:
            min_dist = min(min_dist, dp[i][j+1] + 1)
            if dp2[i][j+1] == False:
                lists.append([i, j+1])
            
        dp[i][j] = min_dist
        
print(max([max(temp_dp) for temp_dp in dp]))

### FIXED CODE ###

# coding: utf-8
# Your code here!

from collections import deque

H, W = map(int, input().rstrip().split(' '))

field = [[0] * W for _ in range(H)]
d = deque()
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            field[i][j] = 1
            d.append([i, j, 0])

max_dist = 0
while len(d) > 0:
    cur_h, cur_w, dist = d.popleft()
    for i, (dh, dw) in enumerate([[0, 1], [0, -1], [1, 0], [-1, 0]]):
        if (cur_h + dh) >= 0 and (cur_h + dh) < H and (cur_w + dw) >= 0 and (cur_w + dw) < W:
            if field[cur_h+dh][cur_w+dw] == 0:
                field[cur_h+dh][cur_w+dw] = 1
                d.append([cur_h+dh, cur_w+dw, dist+1])
                max_dist = max(max_dist, dist+1)

print(max_dist)