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

import sys
from math import sqrt, gcd, ceil, log
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

def main():
	n, k = read(); arr = read()
	arr2 = [i for i in arr]
	for i in range(k-1):
		arr2[k-1] *= arr[i]
	# print(arr)
	for i in range(k, n):
		arr2[i] *= (arr2[i-1]//arr[i-k])
	# print(arr)
	# print(arr2)
	for i in range(k, n):
		print("YNeos"[arr2[i] <= arr2[i-1]::2])






if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
from math import sqrt, gcd, ceil, log
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

def main():
	n, k = read(); arr = read()
	for i in range(k, n):
		print("YNeos"[arr[i] <= arr[i-k]::2])






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

n, q = map(int, input().split())
s = list(input())
l = []
r = []
for _ in range(q):
    line = list(map(int, input().split()))
    l.append(line[0])
    r.append(line[1])
acgt = []
for i in range(1, n):
    if s[i-1] == "A" and s[i] == "C":
        acgt.append(1)
    else:
        acgt.append(0)
for i in range(q):
    print(sum(acgt[l[i]-1:r[i]-1]))

### FIXED CODE ###

n, q = map(int, input().split())
s = list(input())
l = []
r = []
for _ in range(q):
    line = list(map(int, input().split()))
    l.append(line[0])
    r.append(line[1])
ac = []
count = 0
for i in range(1, n):
    if s[i-1] == "A" and s[i] == "C":
        count += 1
    ac.append(count)
for i in range(q):
    right = ac[r[i]-2]
    if l[i] < 2:
        left = 0
    else:
        left = ac[l[i]-2]
    print(right-left)
### BUGGY CODE ###

a, b = map(int,input().split())
def min_multi(x,y):
    for i in range(1,y+1):
        for j in range(1,x+1):
            if x*i == y*j:
                return x*i
print(min_multi(a,b))


### FIXED CODE ###

import fractions
a, b = map(int,input().split())
def jk(j,k):
    return j*k//fractions.gcd(j,k)
print(jk(a, b))
### BUGGY CODE ###

from operator import itemgetter

N = int(input())
h = [[0, i] for i in range(N)]
# 次数と頂点番号

es = [[] for idx in range(N)]
# es[idx]:=[隣接リスト]

for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    h[a][0] += 1
    es[b].append(a)
    h[b][0] += 1

c = list(map(int, input().split()))
c.sort()
# スコアが小さい順にソート

v = [-1] * N
ans = 0

cur = 0
for _ in range(N):
    t = list(sorted(h, key=itemgetter(0)))
    # print(t)
    idx = t[cur][1]
    v[idx] = c[cur]
    ans += c[cur]
    h[idx][0] -= 1
    for nv in es[idx]:
        h[nv][0] -= 1
    cur += 1
ans -= c[-1]
# print(t)
print(ans)
print(*v)


### FIXED CODE ###

N = int(input())
es = [[] for idx in range(N)]
# es[idx]:=[隣接リスト]

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

h = [len(es[i]) for i in range(N)]
# 次数

c = list(map(int, input().split()))
c.sort()
# スコアが小さい順にソート

v = [-1] * N
cur = 0
ans = 0
for _ in range(N - 1):
    for target in range(N):
        # print(target, h, v, ans)
        if h[target] == 1:
            h[target] = 0
            v[target] = c[cur]
            ans += c[cur]
            cur += 1
            for nv in es[target]:
                h[nv] -= 1
            break
for target in range(N):
    if v[target] == -1:
        v[target] = c[cur]
print(ans)
print(*v, sep='\n')
### BUGGY CODE ###

s = input()
t = input()
l_s = len(s)
l_t = len(t)

s2 = s + s
l_s2 = len(s2)

next_idx_1 = [[l_s2] * 26 for i in range(l_s2+1)]

for i in reversed(range(l_s2)):
    for j in range(26):
        next_idx_1[i][j] = next_idx_1[i+1][j]
    next_idx_1[i][ord(s2[i]) - ord("a")] = i

next_idx_2 = [[l_s2] * 26 for i in range(l_s2)]

for i in reversed(range(1, l_s2)):
    for j in range(26):
        next_idx_2[i-1][j] = next_idx_2[i][j]
    next_idx_2[i-1][ord(s2[i]) - ord("a")] = i

cur_idx = 0
for i in range(l_t):
    if i == 0:
        idx = next_idx_1[cur_idx%l_s][ord(t[i]) - ord("a")]

    else:
        idx = next_idx_2[cur_idx%l_s][ord(t[i]) - ord("a")]

    if idx == l_s2:
        print("-1")
        exit()

    cur_idx += idx - (cur_idx % l_s)
    
print(cur_idx+1)

### FIXED CODE ###

s = input()
t = input()
l_s = len(s)
l_t = len(t)

s2 = s + s
l_s2 = len(s2)

next_idx_1 = [[l_s2] * 26 for i in range(l_s2+1)]

for i in reversed(range(l_s2)):
    for j in range(26):
        next_idx_1[i][j] = next_idx_1[i+1][j]
    next_idx_1[i][ord(s2[i]) - ord("a")] = i

next_idx_2 = [[l_s2] * 26 for i in range(l_s2)]

for i in reversed(range(1, l_s2)):
    for j in range(26):
        next_idx_2[i-1][j] = next_idx_2[i][j]
    next_idx_2[i-1][ord(s2[i]) - ord("a")] = i

cur_idx = 0
for i in range(l_t):
    if i == 0:
        idx = next_idx_1[cur_idx%l_s][ord(t[i]) - ord("a")]

    else:
        idx = next_idx_2[cur_idx%l_s][ord(t[i]) - ord("a")]

    if idx == l_s2:
        print("-1")
        exit()

    cur_idx += idx - (cur_idx % l_s)
    
print(cur_idx+1)
### BUGGY CODE ###

from math import factorial
n,m=map(int,input().split())
if n==m:
    print(2*factorial(n)*factorial(m))
elif n==m+1 or m==n+1:
        print(factorial(n)*factorial(m))
else:
    print(0)
    

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
def fact(n):
    mod=10**9+7
    if n==0:
        return 1
    else:
        return (n*fact(n-1))%mod
mod=10**9+7
if n==m:
    print(2*fact(n)*fact(m)%mod)
elif n==m+1 or m==n+1:
        print(fact(n)*fact(m)%mod)
else:
    print(0)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

import bisect

n=int(input())
a = [int(i) for i in input().split()]
a.sort()
check = [0]*n
#print(a)

ans=0

while(a):
    c=a.pop()
    d=c
    keta=0
    while(d!=0):
        d=d//2
        keta +=1
    x = 2**keta - c
#    print(c,x)
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        ans += 1
#        print(a[i],c,"xxx")
        a.remove(x)



print(ans)



### FIXED CODE ###

# coding: utf-8
# Your code here!

import bisect
import collections

n=int(input())
a = [int(i) for i in input().split()]
a.sort()
#print(a)

checked=collections.Counter(a)

ans=0

while(a):
    c=a.pop()
    if checked[c]==0:
        continue
    checked[c]-=1
    d=c
    keta=0
    while(d!=0):
        d=d//2
        keta +=1
    x = 2**keta - c
#    print(c,x)
    i = bisect.bisect_right(a, x)
    if i and a[i-1] == x and checked[x]>0:
        ans += 1
        checked[x]-=1
        
#    print(checked)
#        print(checked)
#        print(a[i],c,"xxx")




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

def mp():return map(int,input().split())
def lmp():return list(map(int,input().split()))

n,m,k = mp()

def combination(n, r, mod):
    np1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (np1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

mod = 998244353
ans = 0
for i in range(k+1):
    ans += combination(n-1, i, mod) * pow(m-1, n-1-i, mod)
    ans %= mod
print((ans*m)%mod)


### FIXED CODE ###

def mp():return map(int,input().split())
def lmp():return list(map(int,input().split()))
n,m,k = mp()
mod = 998244353
conb = [1]
pows = [pow(m-1, n-1-k, mod)]
for i in range(1,k+1):
    conb.append(conb[i-1]*(n-i)*pow(i,mod-2,mod) % mod)
    pows.append(pows[i-1]*(m-1) % mod)
pows.reverse()
# print(conb, pows)
ans = 0
for i in range(k+1):
    ans += m * conb[i] * pows[i]
    ans %= mod
print(ans)

# print(conb)
# print(pows)
# exit()
# now_comb = 1
# now_pow = pow(m-1, n-1, mod)
# ans = now_pow*m
# for i in range(1, k+1):
#     u1 = (now_comb * (n-i) * pow(i, mod-2, mod)) % mod
#     u2 = (now_pow * pow(m-1, mod-2, mod)) % mod
#     now_comb = u1
#     now_pow = u2
#     ans += u1*u2*m
#     ans %= mod
# print(ans%mod)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(M)]
z = []


def func1(x, y):
    global z
    px = -1
    py = -1
    for i, s in enumerate(z):
        if x in s:
            if py > -1:
                lx = len(z[py])
                ly = len(z[i])
                z[py] |= z[i]
                del z[i]
                return (lx + ly)*(lx + ly - 1) // 2 - lx * (lx - 1) // 2 - ly * (ly - 1) // 2
            elif y in s:
                return 0
            else:
                px = i
        elif y in s:
            if px > -1:
                lx = len(z[px])
                ly = len(z[i])
                z[px] |= z[i]
                del z[i]
                return (lx + ly)*(lx + ly - 1) // 2 - lx * (lx - 1) // 2 - ly * (ly - 1) // 2
            else:
                py = i

    if px > -1:
        lx = len(z[px])
        z[px].add(y)
        return lx

    if py > -1:
        lx = len(z[py])
        z[py].add(x)
        return lx

    z.append(set({x, y}))
    return 1


ans = [0] * (M - 1)
p = 0
for i in range(M - 1, 0, -1):
    p += func1(A[i][0], A[i][1])
    ans[i - 1] = p

nall = N * (N - 1) // 2
for a in ans:
    print(nall - a)
print(nall)

### FIXED CODE ###

N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]


class UnionFind:
    def __init__(self,size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]

    def find(self,x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]


def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.number[px] * uf.number[py]
            uf.union(px, py)
        ans.append(p)

    for a in reversed(ans[:-1]):
        print(a)


main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000)

def gcd(a, b):
	# while b:
	# 	a, b = b, a % b
	# return a

	if b:
		return gcd(b, a % b)
	else:
		return a

def gcd_list(li):
	if len(li) > 2:
		x = gcd(li[-1], li[-2])
		li = li[:-2] + [x]
		return gcd_list(li)
	else:
		return gcd(li[0], li[1])

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

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

li = [abs(i - X) for i in x]

# li = [i for i in li if i]
li = sorted(li)
if len(li) == 1:
	print(li[0])
else:
	print(gcd_list(li))

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)

def gcd(a, b):
	# while b:
	# 	a, b = b, a % b
	# return a

	if b:
		return gcd(b, a % b)
	else:
		return a

def gcd_list(li):
	if len(li) > 2:
		x = gcd(li[-1], li[-2])
		li = li[:-2] + [x]
		return gcd_list(li)
	else:
		return gcd(li[0], li[1])

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

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

li = [abs(i - X) for i in x]

# li = [i for i in li if i]
# li = sorted(li)
if len(li) == 1:
	print(li[0])
else:
	ans = li[0]
	for i in range(1,N):
		ans = gcd(ans, li[i])
	print(ans)
### BUGGY CODE ###

import numpy as np
n,m,q=map(int,input().split())
a=np.zeros((n,n))
for i in range(m):
    L,R=map(int,input().split())
    a[:L,R-1:]+=1
for i in range(q):
    L,R=map(int,input().split())
    print(int(a[L-1][R-1]))

### FIXED CODE ###

import numpy as np
n,m,q=map(int,input().split())
a=np.zeros((n+2,n+2))
for i in range(m):
    L,R=map(int,input().split())
    a[1][R]+=1
    a[L+1][R]-=1
a=np.cumsum(a, axis=1)
a=np.cumsum(a, axis=0)
for i in range(q):
    L,R=map(int,input().split())
    print(int(a[L][R]))
### BUGGY CODE ###

from sys import stdin
from collections import deque
import numpy as np

N, M = [int(x) for x in stdin.readline().rstrip().split()]
AB = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N)]
AB.sort(key=lambda x: (x[0], -x[1]))
work = [deque([]) for _ in range(M + 1)]

for ab in AB:
    if ab[0] <= M:
        work[ab[0]].append(ab[1])

ans = 0
day = 1
max_work = np.array([])
while day <= M:
    w = 0
    tmp = 0
    max_work = max_work.tolist()
    if len(work[day]) > 0:
        max_work.append(work[day][0])
    else:
        max_work.append(-1)
    max_work = np.asarray(max_work)
    a = np.argmax(max_work) + 1
    if max_work[a - 1] > 0:
        ans += max_work[a - 1]
        work[a].popleft()
        if len(work[a]) > 0:
            max_work[a - 1] = work[a][0]
        else:
            max_work[a - 1] = -1
    day += 1

print(ans)

### FIXED CODE ###

from sys import stdin
from collections import deque
import heapq


N, M = [int(x) for x in stdin.readline().rstrip().split()]
AB = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N)]
AB.sort(key=lambda x: (x[0], -x[1]))
work = [deque([]) for _ in range(M + 1)]

for ab in AB:
    if ab[0] <= M:
        work[ab[0]].append(ab[1])

ans = 0
day = 1
available_work = []
while day <= M:
    for w in work[day]:
        heapq.heappush(available_work, -w)
    if len(available_work) > 0:
        ans += heapq.heappop(available_work)
    day += 1

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

import numpy as np

N, X, Y = map(int, input().split())
X -= 1
Y -= 1

ans = np.zeros(N-1, np.int64)

c = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        d1 = abs(j - i)
        d2 = abs(X - i) + 1 + abs(j - Y)
        d3 = abs(Y - i) + 1 + abs(j - X)
        ans[min(d1, d2, d3) - 1] += 1

[print(ans[i]) for i in range(N - 1)]


### FIXED CODE ###

import numpy as np

N, X, Y = map(int, input().split())
X -= 1
Y -= 1

ans = [0] * (N-1)

for i in range(N - 1):
    for j in range(i + 1, N):
        d1 = abs(j - i)
        d2 = abs(X - i) + 1 + abs(j - Y)
        ans[min(d1, d2) - 1] += 1

[print(ans[i]) for i in range(N - 1)]
### BUGGY CODE ###

K,S = map(int,input().split())
ans = 0
if 3*K < S:
  pass
else:
  for x in range(K+1):
    for y in range(K+1):
      for z in range(K+1):
        if x+y+z == S:
          ans += 1
print(ans)

### FIXED CODE ###

K,S = map(int,input().split())
ans = 0
if 3*K < S:
  pass
else:
  for x in range(K+1):
    for y in range(K+1):
      z = S-x-y
      if 0 <= z <= K:
        ans += 1

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

import collections
def resolve_c():
    n = input()
    s_l = [input() for i in range(int(n))]
    c = collections.Counter(s_l)
    results = []
    for k, v in c.most_common():
        if v == c.most_common()[0][1]:
            results.append(k)
        else:
            break
    results = sorted(results)
    for r in results:
        print(r)
resolve_c()

### FIXED CODE ###

import collections
def resolve_c():
    n = input()
    s_l = [input() for i in range(int(n))]
    c = collections.Counter(s_l)
    values, counts = zip(*c.most_common())
    results = sorted(list(values[:collections.Counter(counts)[max(counts)]]))
    fin = [print(r) for r in results]
resolve_c()
### BUGGY CODE ###

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

if X < 0:
    X = -X

cnt = 0
for i in range(K):
    X -= D
    cnt += 1
    if X <= 0:
        break
    else:
        continue
    
remain = K-cnt
    
if remain == 0:
    print(abs(X))
else:
    if remain % 2 == 0:
        print(abs(X))
    else:
        print(abs(X+D))

### FIXED CODE ###

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

if X < 0:
    X = -X

cnt = 0
Q = X//D
R = X%D

if K < Q:
    print(X-K*D)
else:
    if (K - Q)%2 == 0:
        print(abs(R))
    else:
        print(abs(R-D))
### BUGGY CODE ###

from collections import deque

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

parent = [[] for _ in range(N)]
child = [[] for _ in range(N)]

for _ in range(N - 1 + M):
    pr, ch = map(int, input().split())
    pr -= 1
    ch -= 1
    parent[ch].append(pr)
    child[pr].append(ch)

root = parent.index([])
depth = [-1] * N
ans = [-1] * N

st = deque([(root, root)])
while st:
    now, pr = st.popleft()
    if depth[now] >= depth[pr] + 1:
        continue
    depth[now] = depth[pr] + 1
    ans[now] = pr + 1
    for ch in child[now]:
        if depth[ch] >= depth[now] + 1:
            continue
        st.append((ch, now))

ans[root] = 0
print(*ans, sep='\n')

### FIXED CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 7)

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

parent = [[] for _ in range(N)]
child = [[] for _ in range(N)]

for _ in range(N - 1 + M):
    pr, ch = map(int, input().split())
    pr -= 1
    ch -= 1
    parent[ch].append(pr)
    child[pr].append(ch)

root = parent.index([])
ans = [-1] * N

# 葉からの検索を行う
@lru_cache(maxsize=None)
def search(now):
    if now == root:
        ans[now] = 0
        return 0
    ret = -1
    for pr in parent[now]:
        depth = search(pr)
        if depth > ret:
            ans[now] = pr + 1
            ret = depth
    return ret + 1

for i in range(N):
    search(i)

print(*ans, sep='\n')
### BUGGY CODE ###

# coding: utf-8
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    N = ir()
    P = lr()
    dp = [[min(i, N-1-i)] * N for i in range(N)]
    people = [[True] * N for i in range(N)]
    for j in range(N):
        x = min(j, N-1-j)
        for i in range(N):
            dp[i][j] = min(dp[i][j], x)

    answer = 0
    for p in P:
        p -= 1
        i = p // N
        j = p % N
        answer += dp[i][j]
        people[i][j] = False
        que = deque([(i, j, dp[i][j])])
        popleft = que.popleft; append = que.append
        while que:
            y, x, cur = popleft()
            cur += people[y][x]
            if x > 0:
                if dp[y][x-1] > cur:
                    dp[y][x-1] = cur
                    append((y, x-1, cur))
            if x < N-1:
                if dp[y][x+1] > cur:
                    dp[y][x+1] = cur
                    append((y, x+1, cur))
            if y > 0:
                if dp[y-1][x] > cur:
                    dp[y-1][x] = cur
                    append((y-1, x, cur))
            if y < N-1:
                if dp[y+1][x] > cur:
                    dp[y+1][x] = cur
                    append((y+1, x, cur))

    print(answer)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

# coding: utf-8
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    N = ir()
    P = lr()
    P = [((p-1)//N, (p-1)%N) for p in P]
    dp = [[min(i, N-1-i, j, N-1-j) for j in range(N)] for i in range(N)]
    people = [[True] * N for i in range(N)]

    answer = 0
    for i, j in P:
        answer += dp[i][j]
        people[i][j] = False
        que = deque([(i, j, dp[i][j])])
        popleft = que.popleft; append = que.append
        while que:
            y, x, cur = popleft()
            cur += people[y][x]
            if x > 0:
                if dp[y][x-1] > cur:
                    dp[y][x-1] = cur
                    append((y, x-1, cur))
            if x < N-1:
                if dp[y][x+1] > cur:
                    dp[y][x+1] = cur
                    append((y, x+1, cur))
            if y > 0:
                if dp[y-1][x] > cur:
                    dp[y-1][x] = cur
                    append((y-1, x, cur))
            if y < N-1:
                if dp[y+1][x] > cur:
                    dp[y+1][x] = cur
                    append((y+1, x, cur))

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

import bisect
N = int(input())
L = list(map(int, input().split()))

L.sort()

ans = 0

for k in range(N-2):
    for j in range(k+1, N-1):
        ans += bisect.bisect_left(L[j+1:], L[k]+L[j])


print(ans)


### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int, input().split()))
 
L.sort()
 
ans = 0
 
for k in range(N-2):
    for j in range(k+1, N-1):
        ans += bisect.bisect_left(L[j+1:], L[k]+L[j])
 
 
print(ans)
### BUGGY CODE ###

# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush

def run():
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    max_m = 2500
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))

    cd = [int(i) for i in sys.stdin.read().split()]
    C = [0]+ cd[::2]
    D = [0]+ cd[1::2]

    queue = []
    # (time, node, rest-coin)
    if S > max_m: S = max_m
    heappush(queue, (0, 1, S))

    state = [[1<<61] * (max_m+1) for _ in range(N+1)]

    while queue:
        time, node, coin = heappop(queue)
        if state[node][coin] < time: continue
        if coin + C[node] <= max_m and time + D[node] < state[node][coin+C[node]]:
            state[node][coin+C[node]] = time + D[node]
            heappush(queue, (time+D[node], node, coin+C[node]))
        for n_node, n_time, n_coin in to[node]:
            if coin < n_coin:continue
            if state[n_node][coin-n_coin] < n_time + time:continue
            state[n_node][coin - n_coin] = n_time + time
            heappush(queue, (time + n_time, n_node, coin - n_coin))
    for s in state[2:]:
        print(min(s))

if __name__ == "__main__":
    run()

### FIXED CODE ###

import sys
readline = sys.stdin.readline
read = sys.stdin.read
 
n,m,s = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    u,v,a,b = [int(i) for i in readline().split()]
    u -= 1
    v -= 1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
 
 
cd = [int(i) for i in read().split()]
c = cd[::2]
d = cd[1::2]
 
 
from heapq import *
INF = 1<<61
M = 2500
if s >= M: s = M-1
dist = [[INF]*M for _ in range(n)] #startからの最短距離
dist[0][s] = 0
q = [(0,s,0)] #(そこまでの距離、銀の枚数、点)
 
while q:
    dv,num,v = heappop(q)
    if dist[v][num] < dv: continue
    if num+c[v] < M and dv+d[v] < dist[v][num+c[v]]:
        dist[v][num+c[v]] = dv + d[v]
        heappush(q, (dv + d[v], num+c[v] ,v))
    for to,a,b in g[v]:
        if num >= a and dv + b < dist[to][num-a]:
            dist[to][num-a] = dv + b
            heappush(q, (dv + b, num-a ,to))
    #print(q)
 
for i in range(1,n):
    print(min(dist[i]))
### BUGGY CODE ###

n, m = list(map(int, input().split()))
lisA = [int(i) for i in input().split()]
#print(n, m)
#print(lisA)

lisA.sort(reverse=True)
half0 = lisA[0]
count = 0
for i in range(m):
	if (count > n - 1):
		count = 0
	if (lisA[count] < half0):
		lisA.sort(reverse=True)
		half0 = lisA[0]
		count = 0
	lisA[count] //= 2
	count += 1
print(sum(lisA))

### FIXED CODE ###

n, m = list(map(int, input().split()))
lisA = [int(i) for i in input().split()]
#print(n, m)
#print(lisA)

lisA.sort(reverse=True)
half0 = lisA[0] // 2
count = 0
for i in range(m):
	if (count > n - 1):
		count = 0
	if (lisA[count] < half0):
		lisA.sort(reverse=True)
		half0 = lisA[0] // 2
		count = 0
	lisA[count] //= 2
	count += 1
print(sum(lisA))