Harryxun/stf_run huggingface dataset:
X,N = map(int,input().split())
lst = list(map(int,input().split()))
lst.sort()
if len(lst) == 0 :
    print(x)
    exit()
a = X
while a in lst :
    a += 1
b = X
while b in lst:
    b -= 1
if X-b > X-a :
    print(a)
else :
    print(b)

### FIXED CODE ###

X, N = map(int, input().split())
lst = list(map(int, input().split()))
lst.sort()
if len(lst) == 0:
    print(X)
    exit()
A = X
while A in lst:
    A -= 1
B = X
while B in lst:
    B += 1
if X-A > B-X:
    print(B)
else:
    print(A)
# E

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

res = [0] * (K+1)
res[0] = (M * (M-1)**(N-1 - K)) % p
p = 998244353
for n in range(1, K+1):
    res[n] = (res[n-1] * (N-n) * pow(n, p-2, p)) % p

print(sum(res) % p)

### FIXED CODE ###

N, M, K = list(map(int, input().split()))
p = 998244353
comb = 1
res = 0
for n in range(K+1):
    res = (res + comb * M * pow(M-1, N-1-n, p)) % p
    comb = (comb * (N -1 -n) * pow(n + 1, p - 2, p)) % p
print(res)
s = list(map(int, input().split()))

for i in s:
  if i == 5:
    count5+=1
  else:
    count7+=1

if count5 == 2 and count7 == 1:
  print("YES")

else:
  print("NO")
    

### FIXED CODE ###

s = list(map(int, input().split()))
count5 = 0
count7 = 0
for i in s:
  if i == 5:
    count5+=1
  else:
    count7+=1

if count5 == 2 and count7 == 1:
  print("YES")

else:
  print("NO")
if ab[0] == "H" and ab[1] == "H":
    print("H")
    
elif ab[0] == "H" and ab[1] == "D":
    print("D")
    
elif ab[0] == "D" and ab[1] == "H":
    print("D")
    
elif ab[0] == "D" and ab[1] == "D":
    print("H")

### FIXED CODE ###

ab = list(input().split())

if ab[0] == "H" and ab[1] == "H":
    print("H")
    
elif ab[0] == "H" and ab[1] == "D":
    print("D")
    
elif ab[0] == "D" and ab[1] == "H":
    print("D")
    
elif ab[0] == "D" and ab[1] == "D":
    print("H")
import sys
n = int(input())
ans = [0]*(n+1) #ans[k]:入力値kでの答え
#初期値３、４、５
ans[3] = 1
ans[4] = 1
ans[5] = 1

if n == 1 or n == 2:
  print(0)
  sys.exit()
  
if 3<= n <=5:
  print(1)
  sys.exit()
for i in range(6,n+1):
  start = 3
  stop = i-3
  s = 1
  for j in range(start,stop+1):
    s = (s+ans[j]) % (10**9+7)
    
  ans[i] = s
  
print(ans[-1])  

### FIXED CODE ###

n = int(input())
s = n // 3

def cmb2(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10**9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


total = 0
for i in range(s):
  y = n - 3*(i+1)
  x = cmb2(y+i,i,p)
  total = (total + x) % (10**9+7)
  
print(total)
# coding: utf-8
# Your code here!
import itertools
import math
from scipy.special import comb

N,K = map(int,input().split())
m = 10**9 + 7
for i in range(1,K+1):
    b = comb(K-1, i-1, True)
    r = comb(N-K+1, i, True)
    print(int(b * r % m))

### FIXED CODE ###

# coding: utf-8
# Your code here!
from operator import mul
from functools import reduce

def cmb(n, r):
	if n < r:
		return 0
	r = min(n - r, r)
	if r == 0:
		return 1
	numer = reduce(mul, range(n, n - r, -1))
	denom = reduce(mul, range(1, r + 1))
	return numer // denom % INF

N,K = map(int,input().split())
INF = 10**9 + 7
for i in range(1,K+1):
    print(cmb(K-1, i-1) * cmb(N-K+1, i) % INF)
N, X, M = map(int, input().split())
tx = X % M
tl = []
ts = set()
ttl = []
for i in range(N):
    tl.append(tx)
    ts.add(tx)
    tx = pow(tx, 2, M)
    if tx in ts:
        ttl = tl[tl.index(tx):]
        break
ans = sum(tl)
d, m = divmod(N-len(tl), len(ttl))
ans += sum(ttl)*d+sum(ttl[:m])
print(ans)


### FIXED CODE ###

N, X, M = map(int, input().split())
if X == 0:
    print(0)
    exit()
tx = X % M
tl = []
ts = set()
ttl = []
for i in range(N):
    tl.append(tx)
    ts.add(tx)
    tx = pow(tx, 2, M)
    if tx in ts:
        ttl = tl[tl.index(tx):]
        break
ans = sum(tl)
if len(ttl)>0:
    d, m = divmod(N-len(tl), len(ttl))
    ans += sum(ttl)*d+sum(ttl[:m])
print(ans)
import numpy as np
N, M, C = list(map(int, input().split()))
B = np.array(list(map(int, input().split())))
A = []

cnt = 0
for _ in range(N):
    if np.array(list(map(int, input().split()))) @ B + C > 0:
        cnt += 1

print(cnt)

### FIXED CODE ###

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

cnt = 0
for _ in range(N):
    A = list(map(int, input().split()))
    score = C
    for a, b in zip(A, B):
        score += a*b
    if score > 0:
        cnt += 1

print(cnt)
def main():
N = int(input())
A = list(map(int,input().split()))
if 0 in A:
    print(0)
    return
prod = 1
for a in A:
    prod *= a
if prod > 1000000000000000000:
    print(-1)
    return
print(prod)
main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    if 0 in A:
        print(0)
        return
    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod)
    
main()
N = int(input())
X = list(map(int, input().split()))
X_min = min(X)
X_max = max(X)
S = []
for x in range(X_min, X_max):
    s = 0
    for i in range(N):
        s += (X[i]-x)**2
    S.append(s)
print(min(S))

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
X_min = min(X)
X_max = max(X)
S = []
if X_min == X_max:
    S.append(0)
for x in range(X_min, X_max):
    s = 0
    for i in range(N):
        s += (X[i]-x)**2
    S.append(s)
print(min(S))
s, t = map(input().split())

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

u = input()

if s == u:
    print(a - 1, b)
elif t == u:
    print(a, b - 1)


### FIXED CODE ###

s, t = input().split()

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

u = input()

if s == u:
    print(a - 1, b)
elif t == u:
    print(a, b - 1)
s = input()

l = len(s)
cnt = 0
for i in range(math.ceil(l/2)):
    if s[i] != s[l-i-1]:
        cnt += 1
print(cnt)

### FIXED CODE ###

import math
s = input()

l = len(s)
cnt = 0
for i in range(math.ceil(l/2)):
    if s[i] != s[l-i-1]:
        cnt += 1
print(cnt)
n,m=map(int,input().split())
for i in range(m//n+1)[::-1]:
	if m%i==0:
		print(i)
        exit()


### FIXED CODE ###

def f():
  n,m=map(int,input().split())
  for i in range(m//n+1)[::-1]:
    if m%i==0:return i
print(f())
b=input()

if b=='A':
    print('T')
elif b=='C':
    print('G')
elif b==('G')
    print('C')
else:
    print('A')

### FIXED CODE ###

b=input()

if b=='A':
    print('T')
elif b=='C':
    print('G')
elif b=='G':
    print('C')
else:
    print('A')
k=int(input())
s=input()
if len(s)<=k:
  print(s)
else:
  print(s[:s]+"...")

### FIXED CODE ###

k=int(input())
s=input()
if len(s)<=k:
  print(s)
else:
  print(s[:k]+"...")
N, D = [int(i) for i in input().split()]
X = [[int(i) for i in input().split()] for _ in range(N)]
 
ans = 0
for i in range(N):
    for j in range(i+1, N):
        yz = [abs((y - z)**2) for y, z in zip(X[i], X[j])]
        v = math.sqrt(sum(yz))
        if v == int(v):
            ans += 1
            
print(ans)

### FIXED CODE ###

import math
N, D = [int(i) for i in input().split()]
X = [[int(i) for i in input().split()] for _ in range(N)]
 
ans = 0
for i in range(N):
    for j in range(i+1, N):
        yz = [abs((y - z)**2) for y, z in zip(X[i], X[j])]
        v = math.sqrt(sum(yz))
        if v == int(v):
            ans += 1
            
print(ans)
i = list(map(int, input().split()))
j = list(map(int, input().split()))
if i[0]=<sum(j):
  print(Yes)
else:
  print(No)

### FIXED CODE ###

i = list(map(int, input().split()))
j = list(map(int, input().split()))
if i[0]<=sum(j):
  print("Yes")
else:
  print("No")
import itertools
import math
import sys

n = int(input())
v = list(map(int, input().split()))
if len(set(v)) == 1:
    print(n // 2)
else:
    odd_cnt = [0] * 10 ** 5
    even_cnt = [0] * 10 ** 5
    for i in range(len(v)):
        if i % 2 == 0:
            even_cnt[v[i]] += 1
        else:
            odd_cnt[v[i]] += 1
    odd = odd_cnt.index(max(odd_cnt))
    even = even_cnt.index(max(even_cnt))
    ans = 0
    print("odd =", odd)
    print("even =", even)
    for i in range(len(v)):
        if i % 2 == 0:
            if v[i] != even:
                ans += 1
        else:
            if v[i] != odd:
                ans += 1
    print(ans)


### FIXED CODE ###

import itertools
import math
import sys
from collections import Counter

n = int(input())
v = list(map(int, input().split()))
e = Counter(v[0::2]).most_common()
o = Counter(v[1::2]).most_common()
if len(e) == 1 and len(o) == 1:
    if e[0][0] == o[0][0]:
        print(n // 2)
    else:
        print(0)
elif len(e) == 1:
    if e[0][0] != o[0][0]:
        print(n - e[0][1] - o[0][1])
    else:
        print(n - max(e[0][1] + o[0][1], o[1][1]))
elif len(o) == 1:
    if e[0][0] != o[0][0]:
        print(n - e[0][1] - o[0][1])
    else:
        print(n - max(e[0][1] + o[0][1], e[1][1]))
else:
    if e[0][0] != o[0][0]:
        print(n - e[0][1] - o[0][1])
    else:
        print(n - max(e[0][1] + o[1][1], e[1][1] + o[0][1]))
n = int(raw_input())
list_str = []
for count in range(0,n):
    list_str.append(raw_input())

for count in range(0,n-1):
    if count == 0:
        compare1 = set(list_str[count])
    else:
        compare1 = set(output)
    compare2 = set(list_str[count+1])
    output = list(compare1 & compare2)
output = ''.join(output)
print output

### FIXED CODE ###

n = int(raw_input())
list_str = []
for count in range(0,n):
    list_str.append(raw_input())
if n != 1:
	for count in range(0,n):
	    if count == 0:
	        output = set(list_str[count])
	    else:
	        compare1 = set(output)
	    	compare2 = set(list_str[count])
	    	output = list(compare1 & compare2)

	tmp_output = ""
	
	for count1 in range(0,len(output)):
		#print output[count1]
		min = 1000
		for count2 in range(0,n):
			num = list_str[count2].count(output[count1])
			if num < min:
				min = num
			#print min
		tmp_output += min*output[count1]
	output = tmp_output
	#output.sort()
else:
	output = list_str[0]
output = sorted(output)
output = ''.join(output)
print output
a = raw_input()
print "%d"% (a * a * a)

### FIXED CODE ###

print(int(input())**3)
#-------------------------------------------------------------------------------
# Name:        module1
# Purpose:
#
# Author:      sato
#
# Created:     19/10/2013
# Copyright:   (c) sato 2013
# Licence:     <your licence>
#-------------------------------------------------------------------------------

def input_and_sort():
    l = []
    for x in input():
        l.append(x)
    l.sort()
    return l



if __name__ == '__main__':
    l = input_and_sort()
    print l[0]
    print l[1]
    print l[2]

### FIXED CODE ###

list = []
for x in range(10):
    y=input()
    list.append(y)
list = sorted(list)
list.reverse()
for x in range(3):
    print list[x]
a = int(input())
b = int(input())
print(a*b)

### FIXED CODE ###

a, b = map(int, input().split())
print(int(a*b))
A, B = map(int, input().split())
print(math.ceil((B - A) / (B - 1)) + 1)

### FIXED CODE ###

A, B = map(int, input().split())
import math
c = math.ceil((B - A) / (A - 1))
print(c + 1)
n=int(input())
p=[int(input()) for i in range(n)]
print(a/2+p)

### FIXED CODE ###

n=int(input())
p=[int(input()) for i in range(n)]
print(sum(p)-max(p)//2)
n, k = map(int, input().split())
s = str(input())

x = s[k-1]
y = x.lower()
s[k-1] = y

print(s)

### FIXED CODE ###

n, k = map(int, input().split())
s = str(input())

if s[k-1] == 'A':
    print(s[:k-1] + 'a' + s[k:])

elif s[k-1] == 'B':
    print(s[:k-1] + 'b' + s[k:])

else:
    print(s[:k-1] + 'c' + s[k:])
from scipy.special import comb

n, k = map(int, input().split())
for i in range(1, k + 1):
    if i <= n - k + 1:
        a = comb(k-1, i-1, exact=True)
        b = comb(n - k + 1, i, exact=True)
        print(a*b%(10**9+7))

### FIXED CODE ###

from scipy.misc import comb

n, k = map(int, input().split())
mod = 10**9+7

for i in range(1, k + 1):
    a = comb(k-1, i-1, exact=True) % mod
    b = comb(n - k + 1, i, exact=True) % mod
    print((a*b)%mod)
n, k = map(int, input().split())
v = [int(i) for i in input().split()]
ans = 0
for a in range(k + 1):
    pa, va = v[:a], v[a:]
    for b in range(k - a + 1):
        pb = pa + va[-b:] if b > 0 else pa
        pb.sort()
        s = sum(pb)
        for c in range(min(k - a - b, a + b)):
            s -= pb[c]
            ans = max(ans, s)
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
v = [int(i) for i in input().split()]
ans = 0
for a in range(min(n, k) + 1):
    pa, va = v[:a], v[a:]
    for b in range(min(n, k) - a + 1):
        pb = pa + va[-b:] if b > 0 else pa
        pb.sort()
        s = sum(pb)
        ans = max(s, ans)
        for c in range(min(k - a - b, a + b)):
            s -= pb[c]
            ans = max(s, ans)
print(ans)
a,b=input(int,input().split())
if a<10 and b<10:
  print(int(a*b))
else:
  print("-1")

### FIXED CODE ###

a,b=map(int,input().split())
if a<=9 and b<=9:
  print(a*b)
else:
  print(-1)
a,b=map(int,input().splite())
if a%2==0 or b%==0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b=map(int,input().split())
if a%2==1 and b%2==1:
  print("Yes")
else:
  print("No")
X,K=int(input())
if K*500>=X:
  print("Yes")
else : 
  print("No")
 

### FIXED CODE ###

K, X=map(int,input().split())
if K*500>=X:
  print("Yes")
else : 
  print("No")
N = int(input())
list = [int(i) for i in input().split()]
a = 0

for i in range(N):
  if min(list[:i+1]) >= list[i]:
    a += 1
    
print(a)

### FIXED CODE ###

a, b = input().split()

if a == b :
  print("Yes")
else:
  print("No")
s=input()


try:
    s1,s2=s.split("-")
except Exception as e:
    print('No')
    sys.exit()

if(not s1.isdigit() or not s2.isdigit()):
    print('No')
    sys.exit()

if(len(s1)!=a or len(s2)!=b or len(s2)>5):
    print('No')
    sys.exit()

print('Yes')

### FIXED CODE ###

import re,sys
a,b=map(int, input().split())
s=input()


try:
    s1,s2=s.split("-")
except Exception as e:
    print('No')
    sys.exit()

if(not s1.isdigit() or not s2.isdigit()):
    print('No')
    sys.exit()

if(len(s1)!=a or len(s2)!=b or len(s2)>5):
    print('No')
    sys.exit()

print('Yes')
def main () :
        a,b =  [int(i) for i in input().split()]
    if a<b:
        print("a<b")
    elif a>b :
        print("a>b")
    else :
        print("a==b")

if__name__=='__main__':
    main()

### FIXED CODE ###

def main () :
    a, b = [int(i) for i in input().split()]
    if a < b :
        print( "a < b")
    elif a > b :
        print("a > b")
    else :
        print("a == b")

if __name__=='__main__':
    main()
import sys
n = int(input())
ls = list(map(int,input().split()))
for i in range(n-1):
    if (ls[i+1] == ls[i]) or (ls[i+1] - ls[i] >=1):
        continue
    elif ls[i+1] - ls[i] == -1 :
        ls[i] = ls[i] - 1
        if ls[i+2] - ls[i+1] <0:
             print("No")
             sys.exit()
    else:
        print("No")
        sys.exit()
print("Yes")

### FIXED CODE ###

import sys
n = int(input())
ls = list(map(int,input().split()))
mx = -float("inf")
for i in ls:
    if i < mx:
        if i + 1 != mx:
            print("No")
            sys.exit()
        else:
            mx = i + 1
    else:
        mx = i
print("Yes")
n = int(input())

l = []
for i in range(n-1, 1, -1):
    if (n/i).is_integer() == True: 
        l.append(i)
        l.append(n/i)
        break
        
if l[0] < 10 and l[i] < 10:
    print('Yes')
else:
    print("No")

### FIXED CODE ###

n = int(input())
bool = False
for i in range(1, 10, 1):
    for j in range(1, 10, 1):
        if i*j == n:
            bool = True
            break
        else: 
            continue
            
if bool == True:
    print("Yes")
else: 
    print("No")
l = [int(input()) for i in range(3)]
x = int(input())
count = 0
for i in range(l[0]+1):
  for j in range(l[1]+1):
    for k in range(l[2]+1):
      if 500*i+100*j+50*c == x:
        count += 1
print(count)
      

### FIXED CODE ###

l = [int(input()) for i in range(3)]
x = int(input())
count = 0
for i in range(l[0]+1):
  for j in range(l[1]+1):
    for k in range(l[2]+1):
      if 500*i+100*j+50*k == x:
        count += 1
print(count)
from collections import deque
while True:
    W,H = map(int, input().split())
    if W == 0: break
    es = [[] for i in range(W*H)]
    for y in range(H):
        walls_h = map(int, input().split())
        for x in range(W-1):
            if walls_h[x]: continue
            es[y*W + x].append(y*W + x+1)
            es[y*W + x+1].append(y*W + x)
        if y == H-1: break
        walls_v = map(int, input().split())
        for x in range(W):
            if walls_v[x]: continue
            es[y*W + x].append((y+1)*W + x)
            es[(y+1)*W + x].append(y*W + x)
    q = deque()
    q.append(0)
    dist = [0] * (W*H)
    dist[0] = 1
    while q:
        fr = q.popleft()
        for to in es[fr]:
            if dist[to] == 0:
                dist[to] = dist[fr] + 1
                q.append(to)
    print(dist[-1])

### FIXED CODE ###

from collections import deque
while True:
    W,H = map(int, input().split())
    if W == 0: break
    es = [[] for i in range(W*H)]
    for y in range(H):
        walls_h = list(map(int, input().split()))
        for x in range(W-1):
            if walls_h[x]: continue
            es[y*W + x].append(y*W + x+1)
            es[y*W + x+1].append(y*W + x)
        if y == H-1: break
        walls_v = list(map(int, input().split()))
        for x in range(W):
            if walls_v[x]: continue
            es[y*W + x].append((y+1)*W + x)
            es[(y+1)*W + x].append(y*W + x)
    q = deque([0])
    dist = [0] * (W*H)
    dist[0] = 1
    while q:
        fr = q.popleft()
        for to in es[fr]:
            if dist[to] == 0:
                dist[to] = dist[fr] + 1
                q.append(to)
    print(dist[-1])
N = int(input())
A = [int(a) for a in input().split()]

def chk(k):
    if k == 1:
        for i in range(1, N):
            if A[i] <= A[i-1]: return 0
        return 1
    
    X = [(0, 0)]
    def add(x):
        if x <= 0: return 0
        if a > X[-1][0]:
            X.append((a, 0))
        elif a == X[-1][0]:
            if X[-1][1] + 1 < k:
                X[-1] = (X[-1][0], X[-1][1] + 1)
            else:
                add(x-1)
        else:
            while X[-1][0] > a:
                X.pop()
            if a > X[-1][0]:
                X.append((a, 1))
            elif a == X[-1][0]:
                if X[-1][1] + 1 < k:
                    X[-1] = (X[-1][0], X[-1][1] + 1)
                else:
                    add(x-1)
    for a in A:
        c = add(a)
        if c == 0: return 0
    return 1

l, r = 0, 1 << 18
while r - l > 1:
    m = (l + r) // 2
    if chk(m):
        r = m
    else:
        l = m

print(r)

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]

def chk(k):
    if k == 1:
        for i in range(1, N):
            if A[i] <= A[i-1]: return 0
        return 1
    
    X = [(0, 0)]
    def add(x, y):
        if x <= 0: return 0
        if x > X[-1][0]:
            X.append((x, 0 if x == y else 1))
        elif x == X[-1][0]:
            if X[-1][1] + 1 < k:
                X[-1] = (X[-1][0], X[-1][1] + 1)
            else:
                if add(x-1, y) == 0: return 0
        else:
            while X[-1][0] > x:
                X.pop()
            if x > X[-1][0]:
                X.append((x, 1))
            elif x == X[-1][0]:
                if X[-1][1] + 1 < k:
                    X[-1] = (X[-1][0], X[-1][1] + 1)
                else:
                    if add(x-1, y) == 0: return 0
        if X[-1][0] < y: X.append((y, 0))
        return 1
    
    for a in A:
        if add(a, a) == 0: return 0
    return 1

l, r = 0, 1 << 18
while r - l > 1:
    m = (l + r) // 2
    if chk(m):
        r = m
    else:
        l = m

print(r)
i=1
while input()!=0:
    print("Case " ,i,":",input())
    i += 1



### FIXED CODE ###

i=1
while True:
    x = int(input())
    if x==0: break
    print("Case {0}: {1}".format(i,x))
    i += 1
import sympy
n = int(input())
c = 0
for i in range(1,n+1):
    if i % 2 == 1 and len(sympy.divisors(i))==8:
        c+=1
print(c)

### FIXED CODE ###

def make_divisors(n):
    a,b =[],[]
    i = 1
    while i*i<=n:
        if n%i == 0:
            a.append(i)
            if i != n//i:
                b.append(n//i)
        i+= 1
    return a+b[::-1]

n = int(input())
c = 0
for i in range(1,n+1):
    if len(make_divisors(i))== 8 and i%2==1:
        c+=1
print(c)
N=int(input())
H=list(map(int,input().split()))

cnt=0
l=[]

if N==1:
	cnt=0
	l.append(cnt)
else:
	for i in reversed(range(1,N)):
		if H[i]<=H[i-1]:
			cnt+=1
		else:
			l.append(cnt)
			cnt=0

print(max(l))

### FIXED CODE ###

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

cnt=0
l=[]

if N==1:
	cnt=0
	l.append(cnt)
else:
	for i in reversed(range(1,N)):
		if H[i]<=H[i-1]:
			cnt+=1
			if i==1:
				l.append(cnt)
		else:
			l.append(cnt)
			cnt=0

print(max(l))
a,b = input()

### FIXED CODE ###

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

if (a + b) % 2 == 0:
    print((a + b) // 2)
else:
    print("IMPOSSIBLE")
#! /usr/bin/env python3
# -*- coding:utf-8 -*-

def discount(M, A):
    A.sort(reverse=True)
    for _ in range(M):
        if A[0] < A[1]: A.sort(reverse=True)
        A[0] = int(A[0]/2)
    return sum(A)

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    print(discount(M, A))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#! /usr/bin/env python3
# -*- coding:utf-8 -*-

def discount(M, A):
    from heapq import heappush, heappop
    hq = []
    for x in A:
        heappush(hq, (-x, x))
    for _ in range(M):
        _, price = heappop(hq)
        dprice = int(price/2)
        heappush(hq, (-dprice, dprice))
    return sum([x for _, x in hq])

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    print(discount(M, A))

if __name__ == '__main__':
    main()
S = input()
if S == ABC:
  print("ARC")
else:
  print("ABC")

### FIXED CODE ###

S = input()
if S == "ABC":
  print("ARC")
else:
  print("ABC")
n=int(input())
l=list(map(int,input().split()))
b,i=l10**9,1
while(i<n):
  p=sum(l[:i])
  q=sum(l[i:])
  b=min(b,abs(p-q))
  i+=1
print(b)

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
a,b=x[0],sum(x)-x[0]
c=abs(a-b)
for i in range(1,n-1):
  a+=x[i]
  b-=x[i]
  c=min(c,abs(a-b))
print(c)
INF = 10**6 + 1

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

a_l=[]
b_l=[]
c_l=[]

for i in range(M):
    a,b,c=map(int,raw_input().split())
    a_l.append(a-1)
    b_l.append(b-1)
    c_l.append(c-1)
    

d = [[INF for j in range(N)] for i in range(N)]

for i in range(N):
    d[i][i]=0

    

for i in range(M):
    d[a_l[i]][b_l[i]] = min(c_l[i],d[a_l[i]][b_l[i]])
    d[b_l[i]][a_l[i]] = min(c_l[i],d[b_l[i]][a_l[i]])


for i in range(N):
    for j in range(N):
        for k in range(N):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])
        
ans = M

for i in range(M):
    flag=False
    for j in range(N):
        for k in range(N):
            if d[j][k]==d[j][a[i]]+d[b[i]][k]:
                flag=True
    if flag:
        ans-=1
print ans

### FIXED CODE ###

N,M=list(map(int,input().split()))
e_list = [[] for i in range(N)]
e_list2 = []
for i in range(M):
    a,b,d = list(map(int,input().split()))
    a=a-1
    b=b-1
    e_list[a].append([b,d])
    e_list[b].append([a,d])
    e_list2.append([a,b,d])

dist_list = []
import heapq
for i in range(N):
    vi = i
    min_d_list = [10**27 for i in range(N)]
    min_d_list[vi] = 0
    prev_list = [-1 for i in range(N)]
    q = []
    for i in range(N):
        heapq.heappush(q,[min_d_list[i],i])

    while len(q)>0:
        d,v = heapq.heappop(q)
        for e in e_list[v]:
            v1,d1=e
            if min_d_list[v1]>d+d1:
                min_d_list[v1]=d+d1
                prev_list[v1]=v
                heapq.heappush(q,[d+d1,v1])
    dist_list.append(min_d_list)
count=len(e_list2)
for e in e_list2:
    for i in range(N):
        if dist_list[i][e[0]]+e[2]==dist_list[i][e[1]]:
            count-=1
            break

print(count)