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


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

RD = []

for i in range(N):

    RD.append([])


for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])

end = [0] * N
endp = 0
endnum = 0
Q = []

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp] == 0:
        Q.append(endp)
    else:
        continue

    while len(Q) > 0:

        q = Q.pop(0)

        if cor[q] == "x":
            cor[q] = 0

        for rd in RD[q]:

            r = rd[0]
            d = rd[1]

            if cor[r] == "x":
                cor[r] = cor[q] + d
                Q.append(r)

            elif cor[r] != cor[q] + d:
                ans = "No"
                break

        if ans == "No":
            break
        endnum += 1
        end[q] = 1

    if ans == "No":
        break

print (ans)


### FIXED CODE ###

from collections import deque

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

RD = [deque() for i in range(N)]
end = [False] * N

for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    end[L-1] = True
    end[R-1] = True
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    


endnum = 0
Q = deque()

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp]:
        Q.append(endp)


        while len(Q) > 0:

            q = Q.pop()
            end[q] = False

            if cor[q] == "x":
                cor[q] = 0

            for r,d in RD[q]:

                if cor[r] == "x":
                    cor[r] = cor[q] + d
                    Q.append(r)

                elif cor[r] != cor[q] + d:
                    print ("No")
                    exit()


print ("Yes")
### BUGGY CODE ###

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

d = 0
c = []
for b in range(-max(a),max(a)+1):
    for i in range(0,len(a)):
        d += abs(a[i]-(b+i+1))
    c.append(d)
    d = 0
print(min(c))

### FIXED CODE ###

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

b_l = []
for i in range(0,len(a)):
    b_l.append(a[i] - (i+1))
b_l.sort()
b = b_l[n//2]
ans = 0
for i in range(0,len(a)):
    ans += abs(a[i] - (i+1+b))
print(ans)
### BUGGY CODE ###

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

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

cnt = N*(N-1)//2
nxt = [[] for i in range(cnt+1)]
nxt[0] += list(range(1, N+1))
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    # 前回変更があった場所のみでループを回す
    for i in nxt[day]:
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    # 変更があった場所をリストに入れておく
                    nxt[day+1] += [i, a]
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
print(day)


### FIXED CODE ###

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

import sys
import time
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

start = time.time()

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1

    elapsed_time = time.time() - start
    if elapsed_time > 1:
        print(N*(N-1)//2)
        exit()
print(day)
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    R, C, K = MI()
    item = [[0] * (C + 1) for i in range(R + 1)]

    for i in range(K):
        r_, c_, v_, = MI()
        item[r_ - 1][c_ - 1] = v_

    dp = [[[0 for _ in range(4)] for _ in range(C + 2)] for _ in range(R + 2)]

    for i in range(R + 1):
        for j in range(C + 1):
            for k in range(4):
                v = item[i][j]

                if k == 3:
                    dp[i + 1][j][0] = max(dp[i][j][k], dp[i + 1][j][0])
                    continue
                dp[i + 1][j][0] = max(dp[i][j][k], dp[i][j][k] + v, dp[i + 1][j][0])
                dp[i][j + 1][k] = max(dp[i][j][k], dp[i][j + 1][k])
                dp[i][j + 1][k + 1] = max(dp[i][j][k] + v, dp[i][j + 1][k + 1])

    ans = max(dp[R][C][0], dp[R][C][1], dp[R][C][2], dp[R][C][3])
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    R, C, K = NMI()
    item = [[0] * (C + 1) for i in range(R + 1)]

    for i in range(K):
        r_, c_, v_, = NMI()
        item[r_ - 1][c_ - 1] = v_

    dp = [[[0 for _ in range(C + 2)] for _ in range(R + 2)] for _ in range(4)]

    for i in range(R + 1):
        for j in range(C + 1):
            for k in range(4):
                a = dp[k][i][j]
                v = item[i][j]

                if k == 3:
                    dp[0][i + 1][j] = max(a, dp[0][i + 1][j])
                    continue
                dp[0][i + 1][j] = max(a, a + v, dp[0][i + 1][j])
                dp[k][i][j + 1] = max(a, dp[k][i][j + 1])
                dp[k + 1][i][j + 1] = max(a + v, dp[k + 1][i][j + 1])

    print(max(dp[0][R][C], dp[1][R][C], dp[2][R][C], dp[3][R][C]))

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

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
K = int(input())
t = 0
t1 = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for l in range(1,K+1):
            t1 = gcd(i,j)
            t = t + gcd(t1,l)
print(t)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
K = int(input())
t = 0
t1 = 0
t2 = 0
for i in range(1,K+1):
    for j in range(i,K+1):
        for l in range(j,K+1):
            if i == j == l:
                t = t + i
            elif i == j or j ==l or l ==i:
                t = t + 3 * gcd(i, j,l)
            else:
                t = t + 6 * gcd(i,j,l)
             
           
           
print(t)
### BUGGY CODE ###

def used(dp,u,v,w):
    n=len(dp)
    for i in range(n):
        for j in range(i+1,n):
            if dp[i][j]==dp[i][u]+w+dp[v][j] or dp[i][j]==dp[i][v]+w+dp[u][j]:
                return True
    return False

while 1:
    try:
        n,m=map(int,input().split())
        es=[]
        for _ in range(m):
            u,v,w=map(int,input().split())
            es.append((u-1,v-1,w))
    except: break

    dp=[[float('inf')]*n for _ in range(n)]
    for i in range(n):
        dp[i][i]=0
    for u,v,w in es:
        dp[u][v]=dp[v][u]=w
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
    print(sum(int(not used(dp,u,v,w)) for u,v,w in es))


### FIXED CODE ###

def used(dp,u,v,w):
    n=len(dp)
    for i in range(n):
        for j in range(i+1,n):
            if dp[i][j]==dp[i][u]+w+dp[v][j] or dp[i][j]==dp[i][v]+w+dp[u][j]:
                return True
    return False

while 1:
    try:
        n,m=map(int,input().split())
        es=[]
        for _ in range(m):
            u,v,w=map(int,input().split())
            es.append((u-1,v-1,w))
    except: break

    dp=[[float('inf')]*n for _ in range(n)]
    for i in range(n):
        dp[i][i]=0
    for u,v,w in es:
        dp[u][v]=dp[v][u]=w
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
    print(sum(int(not used(dp,u,v,w)) for u,v,w in es))
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())

maze = [list(input()) for _ in range(h)]
directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0]
]

def bfs(start, goal):
    visited = [[False] * w for _ in range(h)]
    que = deque([start + (0,)])

    max_cnt = -1
    while que:
        y, x, cnt = que.popleft()
        if 0 <= x < w and 0 <= y < h and maze[y][x] == '.' and not visited[y][x]:
            max_cnt = max(cnt, max_cnt)
            visited[y][x] = cnt + 1
            for dy, dx in directions:
                que.append((y + dy, x + dx, visited[y][x]))
    # print("\n".join([" ".join(map(str, v)) for v in visited]))
    return max_cnt

ans = 0
for sx in range(w):
    for sy in range(h):
        for gx in range(w):
            for gy in range(h):
                ans = max(ans, bfs((sy, sx), (gy, gx)))
print(ans)


### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())

maze = [list(input()) for _ in range(h)]
directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0]
]

def bfs(start):

    visited = [[False] * w for _ in range(h)]
    que = deque([start + (0,)])

    max_cnt = -1
    while que:
        y, x, cnt = que.popleft()
        if 0 <= x < w and 0 <= y < h and maze[y][x] == '.' and not visited[y][x]:
            max_cnt = max(cnt, max_cnt)
            visited[y][x] = cnt + 1
            for dy, dx in directions:
                que.append((y + dy, x + dx, visited[y][x]))
    # print("\n".join([" ".join(map(str, v)) for v in visited]))
    return max_cnt

ans = 0
for sx in range(w):
    for sy in range(h):
        ans = max(ans, bfs((sy, sx)))
print(ans)
### BUGGY CODE ###

import itertools
S=input()
T=len(S)
a=0
mod=[0]*2019
mod[0]+=1
for i in range(T):
 a+=(int(S[T-i-1])*(10**i))%2019
 b=a%2019
 mod[b]+=1
c=0
for i in range(2019):
 if mod[i]>=2:
  c+= mod[i]*(mod[i]-1)/2
print(int(c))


### FIXED CODE ###

S=input()
T=len(S)
a=0
d=1
mod=[0]*2019
mod[0]+=1
for i in range(T):
 a+=(int(S[T-i-1])*(d))%2019
 b=a%2019
 mod[b]+=1
 d*=10
 d%=2019
c=0
for i in range(2019):
 if mod[i]>=2:
  c+= mod[i]*(mod[i]-1)/2
print(int(c))
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
print(" ".join(map(str,[l.index(i)+1 for i in range(1,n+1)])))

### FIXED CODE ###

def main():
  n=int(input())
  l=list(map(int,input().split()))
  k=[0]*n
  for i in range(1,n+1):
    k[l[i-1]-1]=str(i)
  print(" ".join(k))


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

import sys
#input = sys.stdin.readline
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
#xk=list(map(int,list(xs)))
xj=xs.count("1")

x=int(xs,2)

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xs[n-1-i]=="0":
        pxi=pxi+1
    else:
        pxi=pxi-1
#    print(i,xi,"pxi",pxi)
    if xi==0:
        print(0)
    else:
#        print("i",i,"xi",xi,"pxi",pxi)
        xi=xi%pxi
#        print("--i",i,"xi",xi,"pxi",pxi)
        if xi==0:
            print(1)
        else:
#            print("i",i,"xi",xi,"pxi",pxi)
#            print(i,pxi,xi,popcount(xi),xi%popcount(xi))
            icnt=1
            while xi>0:
                icnt+=1
#                print(i,pxi,xi,popcount(xi),xi%popcount(xi))
                xi=xi%popcount(xi)
            print(icnt)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

for i in range(n-1,-1,-1):
    if xs[n-1-i]=="0":
        pxi=xj+1
        i2=pow(2,i,pxi)
        xi=(xip+i2)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        i2=pow(2,i,pxi)
        xi=(xim-i2)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)


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

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

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

ans = 0
mod = 10**9 + 7
for i in a:
    ans += lcm//i
    ans %= mod
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

def main():
    n = int(input())
    a = list(map(int, input().split()))

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

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

    ans = 0
    mod = 10**9 + 7
    for i in a:
        ans += lcm // i
    ans %= mod
    print(ans)

main()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in a:
    ans[i-1] += 1
for j in ans:
    print(j)
### BUGGY CODE ###

#118_D
ch={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

def max_num(x,y):#yは一桁
    if x==-1:
        return -1
    if x==0:
        return y
    l=list(str(x))+[str(y)]
    l.sort(reverse=True)
    return int(''.join(l))

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

dp=[-1 for _ in range(n+1)]
dp[0]=0
for i in range(1,n+1):
    res=-1
    for x in a:
        if i-ch[x]>=0:
            res=max(res,max_num(dp[i-ch[x]],x))
    dp[i]=res
    
print(dp[n])

### FIXED CODE ###

#118_D
ch={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

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

dp=[-1 for _ in range(n+1)]
dp[0]=0
for i in range(1,n+1):
    res=-1
    for x in a:
        if i-ch[x]>=0:
            res=max(res,dp[i-ch[x]]*10+x)
    dp[i]=res
    
print(dp[n])
### BUGGY CODE ###

import sys
import numpy as np
from collections import Counter
s=input()
t=input()
s1=set(s)
t1=set(t)
if s==t:
    print('Yes')
    sys.exit()
qu2=[]
if len(s1)==len(t1):
    for i in s:
        if s.count(i)>1:
            qu=[j for j,e in enumerate(s) if e==i]
            for j in qu:
                j=int(j)
                qu2.append(t[j])
            qu3=set(qu2)
            if len(qu3)!=1:
                print('No')
                sys.exit()
            else:
                qu3.clear()
        qu2=[]
        qu=[]
    print('Yes')
elif len(s1)!=len(t1):
    print('No')


### FIXED CODE ###

import sys
import numpy as np
from collections import Counter
s=input()
t=input()
s1=set(s)
t1=set(t)
if s==t:
    print('Yes')
    sys.exit()
qu2=[]
if len(s1)==len(t1):
    for i in s1:
        if s.count(i)>1:
            qu=[j for j,e in enumerate(s) if e==i]
            for j in qu:
                j=int(j)
                qu2.append(t[j])
            qu3=set(qu2)
            if len(qu3)!=1:
                print('No')
                sys.exit()
            else:
                qu3.clear()
        qu2=[]
        qu=[]
    print('Yes')
elif len(s1)!=len(t1):
    print('No')
### BUGGY CODE ###

def find_index_by_value(a, val):
    for i, items in enumerate(a):
        if val in items:
            return i
    return -1


def count_reachale(a):
    reachable = 0
    for s in a:
        reachable += len(s) * (len(s) - 1) // 2
    return reachable


n, m = map(int, input().split())
edges = []
# node_group = [{n} for n in range(1, n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a, b))

ans = []
not_reachable = n * (n - 1) // 2
reachable_node = []
ans.append(not_reachable)

count = not_reachable

for _ in range(m - 1):
    a, b = edges.pop()
    if count > 0:
        ia = find_index_by_value(reachable_node, a)
        ib = find_index_by_value(reachable_node, b)
        if ia == -1 and ib == -1:
            reachable_node.append({a, b})
        elif ia == -1:
            reachable_node[ib].add(a)
        elif ib == -1:
            reachable_node[ia].add(b)
        else:
            if ia != ib:
                reachable_node[ia] |= reachable_node[ib]
                reachable_node.pop(ib)
        count = not_reachable - count_reachale(reachable_node)
    ans.append(count)

for _ in range(len(ans)):
    print(ans.pop())




### FIXED CODE ###

def find_index_by_value(a, val):
    for i, items in enumerate(a):
        if val in items:
            return i
    return -1


def num_reachable(n):
    return n * (n - 1) // 2


n, m = map(int, input().split())
edges = []

for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a, b))

size = [1 for _ in range(n + 1)]
group = [i for i in range(n + 1)]


def find_group(x):
    c = []
    p = x
    while True:
        pp = group[p]
        if pp == p:
            break
        else:
            c.append(p)
            p = pp
    for i in c:
        group[i] = pp
    return pp

# find_group = lambda x: x if x == group[x] else find_group(group[x])

ans = []
not_reachable = n * (n - 1) // 2
reachable_node = []
ans.append(not_reachable)

count = not_reachable
reachable = 0
for _ in range(m - 1):
    a, b = edges.pop()
    if count > 0:
        ra = find_group(a)
        rb = find_group(b)
        if rb != ra:
            s_ra = size[ra]
            s_rb = size[rb]
            new_size = s_ra + s_rb
            reachable += num_reachable(new_size) - num_reachable(s_ra) - num_reachable(s_rb)
            size[ra] = new_size
            group[rb] = ra
        count = not_reachable - reachable
    ans.append(count)

for _ in range(len(ans)):
    print(ans.pop())
### BUGGY CODE ###

N = int(input())

r = 0
for u in range(1, 10):
    for l in range(1, 10):
        r1 = 0
        r2 = 0
        for i in range(1, N + 1):
            x = int(str(i)[0])
            if i % 10 == l and x == u:
                r1 += 1
            if i % 10 == u and x == l:
                r2 += 1
        r += r1 * r2
print(r)



### FIXED CODE ###

import math
from collections import defaultdict

N = int(input())

rr = defaultdict(lambda: 0)
for i in range(1, N + 1):
    x = int(i / (10 ** int(math.log10(i))))
    y = i % 10
    rr[(x, y)] += 1

r = 0
for u in range(1, 10):
    for l in range(1, 10):
        r += rr[(u, l)] * rr[(l, u)]
print(r)
### BUGGY CODE ###

N,M = map(int,input().split())
edge = [[None]*(N+1) for _ in range(N+1)]
for _ in range(M):
    l,r,d = map(int,input().split())
    edge[l][r] = d
    edge[r][l] = -d
G = [None]*(N+1)
ok = True
stack = []
for x in range(1,N+1):
    if G[x] is not None: continue
    G[x] = 0
    stack = [x]
    while stack:
        v = stack.pop()
        for to in range(1,N+1):
            if edge[v][to] is None:
                continue
            d = edge[v][to]
            if G[to] is None:
                G[to] = G[v] + d
                stack.append(to)
            else:
                if G[to] != G[v] + d:
                    ok = False
                    break
    if ok == False:
        break
print('Yes' if ok else 'No')

### FIXED CODE ###

N,M = map(int,input().split())
edge =[[] for _ in range(N+1)]
for _ in range(M):
    l,r,d = map(int,input().split())
    edge[l].append([r,d])
    edge[r].append([l,-d])
G = [None]*(N+1)
ok = True
stack = []
for x in range(1,N+1):
    if G[x] is not None: continue
    G[x] = 0
    stack = [x]
    while stack:
        v = stack.pop()
        for to,d in edge[v]:
            if G[to] is None:
                G[to] = G[v] + d
                stack.append(to)
            else:
                if G[to] != G[v] + d:
                    ok = False
                    break
    if ok == False:
        break
print('Yes' if ok else 'No')
### BUGGY CODE ###

N,M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
while M > 0:
    A[-1] = A[-1] // 2
    M -= 1
    A = sorted(A)
print(sum(A))

### FIXED CODE ###

N,M = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
    A[i] *= -1
import heapq
heapq.heapify(A)
for i in range(M):
    m = heapq.heappop(A)
    heapq.heappush(A,-1*(-m//2))
print(-1*sum(A))