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

from heapq import heapify, heappop

nm = list(map(int, input().split()))
n, m = nm[0], nm[1]
ab_list = list()
for i in range(n):
    ab = list(map(int, input().split()))
    a, b = ab[0], ab[1]
    ab_list.append((-b, a))


result = 0

candidates = list()

for rem in range(1, m + 1):
    added_candidate = list(filter(lambda x: x[1] == rem, ab_list))
    if len(added_candidate) > 0:
        candidates.extend(added_candidate)

    if len(candidates) > 0:
        heapify(candidates)
        top = heappop(candidates)
        result += -top[0]

print(result)


### FIXED CODE ###

from heapq import heapify, heappop, heappush

nm = list(map(int, input().split()))
n, m = nm[0], nm[1]
d = {}
ab_list = list()
for i in range(n):
    ab = list(map(int, input().split()))
    rem_day, reward = ab[0], ab[1]
    if rem_day in d:
        d[rem_day].append(-reward)
    else:
        d[rem_day] = [-reward]


result = 0

candidates = list()

for rem in range(1, m + 1):
    added_candidates = d.get(rem)
    if added_candidates is not None:
        for ac in added_candidates:
            heappush(candidates, ac)

    if len(candidates) > 0:
        top = heappop(candidates)
        result += -top

print(result)
### BUGGY CODE ###

import  collections
def resolve():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    cnt=collections.Counter(a)
    ans=0
    for i in range(len(cnt.most_common())-k):
        ans+=cnt.most_common()[-1-i][1]
    print(ans)
resolve()

### FIXED CODE ###

import collections

n, k = map(int, input().split())
a = list(map(int, input().split()))
cnt = collections.Counter(a)
ans = 0
t=cnt.most_common()
if len(t) <= k:
    print(0)
    exit()

for i in range(k):
    ans += t[i][1]
print(n - ans)
### BUGGY CODE ###

def crmv(c,istr):
    if len(istr)<=1:
        return c
    
    lidx=[]
    for i in range(len(istr)-1):
        if istr[i] != istr[i+1]:
            lidx.append(i)
    if len(lidx)==0:
        return c

    rv=0
    for i in lidx:
        tstr=istr[:i]+istr[i+1+1:]
        r=crmv(c+1,tstr)
        if r>rv:
            rv=r
    return rv

istr=input()

print(crmv(0,istr)*2)

### FIXED CODE ###

istr=input()
c0=0
c1=0
for ch in istr:
    if ch == '0':
        c0+=1
    else:
        c1+=1
print(min(c0,c1)*2)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
ans = 0
if a[0] != 0:
    print(-1)
    exit()
for i in range(n-1):
    if a[i+1] - a[i] > 1:
        print(-1)
        exit()
for _ in range(n):
    if set(a) == set([-1,0]) or set(a) == set([0]):
        break
    i = a.index(max(a))
    if i == 0:
        print(-1)
        exit()
    if a[i-1] + 1 == a[i]:
        a[i] = -1
        ans += 1
    elif a[i-1] == -1:
        a[i-1] = a[i] - 1
        a[i] = -1
        ans += 1
    else:
        print(-1)
        exit()
print(ans)

### FIXED CODE ###

n = int(input())
prev = ans = -1
a = [int(input()) for _ in range(n)]
for i in a:
    if i - prev > 1:
        print(-1)
        exit()
    elif i - prev == 1:
        ans += 1
    else:
        ans += i
    prev = i
print(ans)
### BUGGY CODE ###

h, n = map(int, input().split())
l = []
for i in range(n):
  a, b = map(int, input().split())
  l.append([a, b])

dp = [10 ** 9 for i in range(h+1)]
dp[0] = 0

for i in range(h+1):
  for j in range(n):
    if dp[i] > l[j][1] + dp[max(i-l[j][0], 0)]:
      dp[i] = l[j][1] + dp[max(i-l[j][0], 0)]


print(dp[h])


### FIXED CODE ###

def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for a, b in AB:
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print(min(dp[H:]))


main()
### BUGGY CODE ###

import sys

X, K, D=list(map(int, input().split()))

if X < 0:
    X = -X

if X-K*D>=0:
    print(X-K*D)
    sys.exit()

temp_X = X
temp_K = K

while temp_X-D >= 0:
    temp_X -= D
    temp_K -= 1

if temp_K%2==0:
    print(temp_X)
else:
    print( abs(temp_X-D) )


### FIXED CODE ###

import sys

X, K, D=list(map(int, input().split()))

if X < 0:
    X = -X

if X-K*D>=0:
    print(X-K*D)
    sys.exit()

temp_X = X
temp_K = K

#while temp_X-D >= 0:
#    temp_X -= D
#    temp_K -= 1

k = X//D

temp_X = X-k*D
temp_K = K-k

if temp_K%2==0:
    print(temp_X)
else:
    print( abs(temp_X-D) )
### BUGGY CODE ###

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

order_sort = [i for i in range(1, n+1)]
for order in order_sort:
    people = people_count.index(order) + 1
    print(people, end=" ")

### FIXED CODE ###

import numpy as np
n = int(input())
people_count = list(map(int, input().split()))


people_count = np.array(people_count)
arg = people_count.argsort()
for i in arg:
    print(i+1, end=" ")
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, K = LI()

def fact(n):
    if (n==0) or (n==1):
        return 1

    ret = 1
    for i in range(1, n+1):
        ret *= i
        if (ret >= mod):
            ret
    return ret


for i in range(1, K+1):
    t1 = fact(N-K+1)
    t2 = fact(i)
    t3 = fact(N-K-i+1)
    tmp1 = t1//(t2*t3)

    t4 = fact(K-1)
    t5 = fact(i-1)
    t6 = fact(K-i)
    tmp2 = t4//(t5*t6)

    print(tmp1 * tmp2 % mod)

### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, K = LI()

def fact(n):
    if (n==0) or (n==1):
        return 1
    ret = 1
    for i in range(1, n+1):
        ret *= i
    return ret


for i in range(1, K+1):
    if (N-K-i+1>= 0):
        t1 = math.factorial(N-K+1)
        t2 = math.factorial(i)
        t3 = math.factorial(N-K-i+1)
        tmp1 = (t1//(t2*t3))%mod

        t4 = math.factorial(K-1)
        t5 = math.factorial(i-1)
        t6 = math.factorial(K-i)
        tmp2 = (t4//(t5*t6))%mod

        print(tmp1 * tmp2 % mod)
    else:
        print(0)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math
import numpy as np
H,W,D = map(int, raw_input().split())

Ah = np.array([0]*(H*W))
Aw = np.array([0]*(H*W))

# for h in range(H):
#     As = list(map(int, input().split()))
#     for w in range(W):
#         Ah[As[w]-1] = h
#         Aw[As[w]-1] = w

for h in range(H):
    As = np.array(list(map(int, raw_input().split())))
    Aw[As-1] = np.arange(W)
    Ah[As-1] = h

Q = int(raw_input())

def solve(l, r):
    ans = 0
    ah = Ah[l-1:r][::D]
    ans += np.sum(np.abs(ah[1:] - ah[0:-1]))
    aw = Aw[l-1:r][::D]
    ans += np.sum(np.abs(aw[1:] - aw[0:-1]))
    #ans = sum(Ah[l-1:l+D][::D])
    # while l != r:
    #     x,y = A[l-1]
    #     x2,y2 = A[l+D-1]
    #     ans += abs(x-x2) + abs(y-y2)
    #     l += D
    return ans

lrs = []
for q in range(Q):
    L, R = map(int, raw_input().split())
    print(solve(L, R))
    #lrs.append((L,R))

# for info in lrs:
#     L,R = info
#     print(solve(L, R))




### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
H,W,D = map(int, input().split())

# Ah = np.array([0]*(H*W))
# Aw = np.array([0]*(H*W))
A = [0]*(H*W)
for h in range(H):
    As = list(map(int, input().split()))
    for w in range(W):
        A[As[w]-1] = (h,w)
    # Aw[As-1] = np.arange(W)
    # Ah[As-1] = h


Q = int(input())

# def solve(l, r):
#     ans = 0
#     # ah = Ah[l-1:r][::D]
#     # ans += np.sum(np.abs(ah[1:] - ah[0:-1]))
#     # aw = Aw[l-1:r][::D]
#     # ans += np.sum(np.abs(aw[1:] - aw[0:-1]))
#     ans = sum(Ah[l-1:l+D][::D])
#     while l != r:
#         x,y = A[l-1]
#         x2,y2 = A[l+D-1]
#         ans += abs(x-x2) + abs(y-y2)
#         l += D
#     return ans

Ans = [0]*(H*W)
aa = (H*W) // D
bb = (H*W) % D
for dth in range(1,aa+1):
    for d in range(D):
        if dth*D+d >=H*W:
            break
        x,y = A[(dth-1)*D+d]
        x2,y2 = A[dth*D+d]
        ans = abs(x-x2) + abs(y-y2)
        Ans[dth*D+d] = Ans[(dth-1)*D+d] + ans



lrs = []
for q in range(Q):
    L, R = map(int, input().split())
    print(Ans[R-1] - Ans[L-1])
    #lrs.append((L,R))

# for info in lrs:
#     L,R = info
#     print(solve(L, R))
### BUGGY CODE ###

casen=0
if casen==0:
    a=[]
    c=[]
    n=int(input())
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append([ai,bi])
    for i in range(n):
        ci,di=map(int,input().split())
        c.append([ci,di])
elif casen==1:
    n=3
    a=[[2,0],[3,1],[1,3]]
    c=[[4,2],[0,4],[5,5]]
elif casen==2:
    n=3
    a=[[0,0],[1,1],[5,2]]
    c=[[2,3],[3,4],[4,5]]
elif casen==3:
    n=2
    a=[[2,2],[3,3]]
    c=[[0,0],[1,1]]
elif casen==4:
    n=5
    a=[[0,0],[7,3],[2,2],[4,8],[1,6]]
    c=[[8,5],[6,9],[5,4],[9,1],[3,7]]
elif casen==5:
    n=5
    a=[[0,0],[1,1],[5,5],[6,6],[7,7]]
    c=[[2,2],[3,3],[4,4],[8,8],[9,9]]

t=[]
for ia in range(n):
    s=set()
    for ic in range(n):
        if a[ia][0]<c[ic][0] and a[ia][1]<c[ic][1]:
            s.add(ic)
    t.append(s)

icnt=0

from collections import deque
tyn3 = deque()

def pcnt(icnt,ia,t,n,tyn3,icntmax,r,t2,it):
    ia1=ia
    if ia>=n-1:
        icnt2=len(r)
        icntmax=max(icnt2,icntmax)
        if len(tyn3)>0:
            it2=tyn3.pop()
            r.remove(it2)
        ia=ia-1
        return icntmax,ia
    t3=t[ia]-r
    r1=r.copy()
    for it in t3:
        ia=ia1+1
        t2=t[ia]
        r1.add(it)
        tyn3.append(it)
        icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax,r1,t2,it)
    ia=ia+1
    t2=t[ia]
    icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax,r,t2,it)
    return icntmax,ia

ia=-1    
icntmax=0
r=set()
t2=t[0]
it=0
icntmax,ia=pcnt(icnt,ia,t,n,tyn3,icntmax,r,t2,it)

print(icntmax)        
    

### FIXED CODE ###

casen=0
if casen==0:
    a=[]
    c=[]
    n=int(input())
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append([ai,bi])
    for i in range(n):
        ci,di=map(int,input().split())
        c.append([ci,di])
elif casen==1:
    n=3
    a=[[2,0],[3,1],[1,3]]
    c=[[4,2],[0,4],[5,5]]
elif casen==2:
    n=3
    a=[[0,0],[1,1],[5,2]]
    c=[[2,3],[3,4],[4,5]]
elif casen==3:
    n=2
    a=[[2,2],[3,3]]
    c=[[0,0],[1,1]]
elif casen==4:
    n=5
    a=[[0,0],[7,3],[2,2],[4,8],[1,6]]
    c=[[8,5],[6,9],[5,4],[9,1],[3,7]]
elif casen==5:
    n=5
    a=[[0,0],[1,1],[5,5],[6,6],[7,7]]
    c=[[2,2],[3,3],[4,4],[8,8],[9,9]]

c.sort()
a.sort(key=lambda x:x[1])
#a.reverse()

icnt=0
ic2=0
for ic in range(len(c)):
    for ia in range(len(a)-1,-1,-1):
        if a[ia][0]<c[ic][0] and a[ia][1]<c[ic][1]:
            icnt=icnt+1
            del a[ia]
            break
        else:
            continue
        break

print(icnt)
### BUGGY CODE ###

s = input()


a =[ int(i) for i in list(s)]
s_val = 0
for n_bit, bit in enumerate(a[::-1]):
    s_val += bit *(2**n_bit)


s1 = 0
for i in range(len(s)):
    if i%2==0:
        s1 += 2**i
        
s2 = 0
for i in range(len(s)):
    if i%2==1:
        s2 += 2**i

num = min(str(bin(s_val^s1)).count('1'), str(bin(s_val^s2)).count('1'))
print(num)

### FIXED CODE ###

s = input()

s_val = int(s, 2)


s1 = ''
s2 = ''
for i in range(len(s)):
    if i%2==0:
        s1 = s1 + '1'
        s2 = s2 + '0'
    else:
        s1 = s1 + '0'
        s2 = s2 + '1'

num = min(str(bin(s_val^int(s1,2))).count('1'), str(bin(s_val^int(s2,2))).count('1'))
print(num)
### BUGGY CODE ###

def main():
    mod = 998244353
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [0] * (S + 1)
    dp[0] = pow(2, N, mod)
    div2 = pow(2, mod - 2, mod)
    m = 0
    for a in A:
        for i in reversed(range(a, min(S, a + m) + 1)):
            dp[i] = dp[i] + dp[i - a] * div2
        m += a
    return dp[S] % mod

print(main())


### FIXED CODE ###

def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    return solve(N, S, A)

def solve(N, S, A):
    mod = 998244353
    dp = [0] * (S + 1)
    dp[0] = pow(2, N, mod)
    div2 = pow(2, mod - 2, mod)
    m = 0
    for a in A:
        m += a
        for i in reversed(range(a, min(S, m) + 1)):
            dp[i] = (dp[i] + dp[i - a] * div2) % mod
    return dp[S]

print(main())
### BUGGY CODE ###

import collections

n,m = map(int,input().split())
friend = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    if a not in friend[b]:
        friend[a].append(b)
        friend[b].append(a)

q = collections.deque()
visited = [0 for i in range(n)]

ans = 0
for i in range(n):
    if visited[i] == 0:
        visited[i] = 1
        tmp = 1
        for j in friend[i]:
            if visited[j] == 0:
                visited[j] = 1
                tmp += 1
                q.append(j)
        while q:
            s = q.pop()
            for k in friend[s]:
                if visited[k] == 0:
                    tmp += 1
                    q.append(k)
    ans = max(ans,tmp)

print(ans)

### FIXED CODE ###

import collections

n,m = map(int,input().split())
friend = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    friend[a].append(b)
    friend[b].append(a)

q = collections.deque()
visited = [0 for i in range(n)]

ans = 0
for i in range(n):
    tmp = 0
    if visited[i] == 0:
        visited[i] = 1
        tmp += 1
        for j in friend[i]:
            if visited[j] == 0:
                visited[j] = 1
                tmp += 1
                q.append(j)
        while q:
            s = q.pop()
            for k in friend[s]:
                if visited[k] == 0:
                    visited[k] = 1
                    tmp += 1
                    q.append(k)
    ans = max(ans,tmp)

print(max(ans,1))
### BUGGY CODE ###

from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

lcm = 1
for a in A:
    lcm = lcm * a // gcd(lcm, a)


ans = 0
for a in A:
    ans += lcm // a

print(ans % MOD)

### FIXED CODE ###

from fractions import gcd


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


    l = 1

    for a in A:
        l = l * a // gcd(l, a)


    ans = 0
    for a in A:
        ans += (l // a)
    ans %= MOD

    print(ans)


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

import sys
input = sys.stdin.readline

lunlun = []

def main():
    n = int(input())
    for i in range(3234566667):
        flag = True
        if len(str(i)) == 1:
            lunlun.append(i)
        else:
            for a in range(1, len(str(i))):
                if len(lunlun) > n:
                    print(lunlun[n])
                    exit()
                elif abs(int(str(i)[a - 1]) - int(str(i)[a])) >= 2:
                    flag = False
                    break
            if flag:
                lunlun.append(i)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
import itertools

lunlun = [[] for i in range(11)]

def main():
    n = int(input())
    for i in range(100):
        flag = True
        l = len(str(i))
        if l == 1:
            lunlun[l - 1].append(i)
        else:
            for a in range(1, len(str(i))):
                if abs(int(str(i)[a - 1]) - int(str(i)[a])) >= 2:
                    flag = False
                    break
            if flag:
                lunlun[l - 1].append(i)
            else:
                continue
    for j in range(1, 9):
        for a in lunlun[j]:
            for b in range(10):
                if abs(int(str(a)[-1]) - b) < 2:
                    lunlun[j+1].append(int(str(a)+str(b)))
    lunlun2 = list(itertools.chain.from_iterable(lunlun))
    print(lunlun2[n])

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

import numpy as np

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
ope=[]
for i in range(Q):
  ope.append(list(map(int,input().split())))

A=np.array(A)
for b,c in ope:
  A[A==b]=c
  print(sum(A))


### FIXED CODE ###

import numpy as np

N=int(input())
A=list(map(int,input().split()))
Adic={}
for i in A:
  if Adic.get(i)==None:
    Adic[i]=1
  else:
    Adic[i]+=1
Q=int(input())
ope=[]

for i in range(Q):
  ope.append(list(map(int,input().split())))

A=np.array(A)

sum=0
for key,value in Adic.items():
  sum+=key*value
for b,c in ope:
  if Adic.get(b)!=None:
    if Adic.get(c)==None:Adic[c]=0
    sum=sum-b*Adic[b]+c*Adic[b]
    Adic[c]+=Adic.pop(b)
    print(sum)
  else:
    print(sum)
### BUGGY CODE ###

N,K=list(map(int, input().split()))
A=list(map(int, input().split()))
S=set(A)
B=[]
for i in S:
  k=A.count(i)
  B.append(k)
B.sort()
# print(B)
C=B[:len(S)-K]
print(sum(C))

### FIXED CODE ###

from collections import Counter

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

dic = dict(Counter(A))
ls = list(dic.items())
ls.sort(key=lambda x: x[1])

i=0
ans=0
res=len(ls)
while 1:
  if res <= K or i >= N:
    break
  ans += ls[i][1]
  i+=1
  res-=1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
a = []
for _ in range(m):
    a.append(int(input()))

memo = [0]*(n+1)
memo[0]=1
if not(1 in a):
    memo[1]=1

for i in range(2,n+1):
    #print(i)
    if i in a:
        continue
    #print(memo[i-1],memo[i-2])
    memo[i]=memo[i-2]+memo[i-1]
            

#print(memo)
print(memo[n]% 1000000007)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
a = []
for _ in range(m):
    a.append(int(input()))
a=set(a)

memo = [0]*(n+1)
memo[0]=1
if not(1 in a):
    memo[1]=1

for i in range(2,n+1):
    #print(i)
    if i in a:
        continue
    #print(memo[i-1],memo[i-2])
    memo[i]=memo[i-2]+memo[i-1]
            

#print(memo)
print(memo[n]% 1000000007)
### BUGGY CODE ###

S=list(input())
L=len(S)
a=1
while a==1:
    l=len(S)
    a=0
    for i in range(l-1):
        if S[i]!=S[i+1]:
            S.pop(i)
            S.pop(i)
            a=1
            break
print(L-len(S))

### FIXED CODE ###

S=list(input())
a=S.count('0')
b=S.count('1')
if a>b:
    print(2*b)
else:
    print(2*a)
### BUGGY CODE ###

from itertools import combinations
n, m = map(int, input().split())
a = list(map(int, input().split()))
total = sum(a)
must = total / (4 * m)
cnt = 0
for c in combinations(a, m):
    flag = True
    for i in c:
        if i < must:
            flag = False
            break
    if flag:
        print("Yes")
        exit()
    else:
        continue
print("No")

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    total = sum(a)
    must = total / (4 * m)
    cnt = 0
    for i in a:
        if i >= must:
            cnt += 1
            if cnt == m:
                print("Yes")
                exit()
    print("No")


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

n,m = list(map(int,input().split()))
l = sorted([int(a) for a in input().split()])
for i in range (m):
  l.sort()
  l.reverse()
  l[0]=l[0]//2
print(sum(l))

### FIXED CODE ###

import heapq
n,m = list(map(int,input().split()))
l = sorted([(int(a)*-1) for a in input().split()])
for i in range (m):
  high = heapq.heappop(l)
  heapq.heappush(l,-(-high//2))
print(abs(sum(l)))
### BUGGY CODE ###

import sys
from collections import deque

input = sys.stdin.readline
H, W = map(int, input().split())

grid = []
for _ in range(H):
    grid.append(list(input().strip()))

q = deque()
# x, y, count, pre color
q.append((0, 0, 1 if grid[0][0] == "#" else 0, grid[0][0]))

visited = [[-1 for _ in range(W)] for _ in range(H)]
ans = float("inf")
while q:
    x, y, count, pre = q.popleft()
    # print(x, y, count, pre)
    v_score = visited[y][x]
    if v_score != -1 and v_score < count:
        continue
    visited[y][x] = count

    for dx, dy in ((1, 0), (0, 1)):
        nx = x + dx
        ny = y + dy
        nc = count
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        n_color = grid[ny][nx]
        if n_color != pre and n_color == "#":
            nc += 1
        if nx == W-1 and ny == H-1:
            ans = min(ans, nc)
            print(ans)
            sys.exit()
        else:
            if count == nc:
                q.appendleft((nx, ny, nc, n_color))
            else:
                q.append((nx, ny, nc, n_color))

# print(visited)
print(ans)

### FIXED CODE ###

import sys
from collections import deque

input = sys.stdin.readline
H, W = map(int, input().split())

grid = []
for _ in range(H):
    grid.append(list(input().strip()))

q = deque()
# x, y, count, pre color
q.append((0, 0, 1 if grid[0][0] == "#" else 0, grid[0][0]))

visited = [[-1 for _ in range(W)] for _ in range(H)]
ans = float("inf")
while q:
    x, y, count, pre = q.popleft()
    # print(x, y, count, pre)
    v_score = visited[y][x]
    if v_score != -1 and v_score <= count:
        continue
    visited[y][x] = count

    for dx, dy in ((1, 0), (0, 1)):
        nx = x + dx
        ny = y + dy
        nc = count
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        n_color = grid[ny][nx]
        if n_color != pre and n_color == "#":
            nc += 1
        if nx == W-1 and ny == H-1:
            ans = min(ans, nc)
            print(ans)
            sys.exit()
        else:
            if visited[ny][nx] != -1 and visited[ny][nx] <= nc:
                continue
            if count == nc:
                q.appendleft((nx, ny, nc, n_color))
            else:
                q.append((nx, ny, nc, n_color))

# print(visited)
print(ans)