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

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
def main():
	N, M = map(int, input().split(" "))
	#N = int(input())
	#S = input()

	A = input().split(" ")
	A = list(A)
	#A = A[:-1]
	A = [int(s) for s in A]

	BC = []
	for i in range(M):
		b, c = map(int, input().split(" "))
		BC.append((b, c))

	for i in BC:
		A.sort()
		b, c = i

		if A[0] >= c:
			continue
			
		tmp = bisect_left(A, c)
		if tmp <= b:
			A[:tmp] = [c] * tmp
		elif tmp > b:
			A[:b] = [c] * b


	ans = 0
	for i in A:
		ans += i
	print(ans)


if __name__ == "__main__":
	main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)

# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

def main():
	N, M = map(int, input().split(" "))
	#N = int(input())
	#S = input()

	A = input().split(" ")
	A = list(A)
	#A = A[:-1]
	A = [(int(s) * (-1), 1) for s in A]
	heapq.heapify(A)

	for i in range(M):
		b, c = map(int, input().split(" "))
		heapq.heappush(A, (c * (-1), b))
	
	ans = []
	for i in range(N):
		t, con = heapq.heappop(A)
		for _ in range(con):
			if len(ans) == N:
				print(sum(ans))
				sys.exit()
			ans.append(t * (-1))
	print(sum(ans))


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

N = int(input())

tNow = 1
aNow = 1

for i in range(N) :
    t, a = map(int, input().split())
    n = 1
    while n * t < tNow or n * a < aNow :
        n += 1
    tNow = n * t
    aNow = n * a

print(tNow + aNow)

### FIXED CODE ###

N = int(input())

tNow = 1
aNow = 1

for i in range(N) :
    t, a = map(int, input().split())

    n = max(-(-tNow // t), -(-aNow // a))

    tNow = n * t
    aNow = n * a

print(tNow + aNow)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0

n_iter_r = int(N/R)+1
n_iter_g = int(N/G)+1

for r in range(n_iter_r):
    for g in range(n_iter_g):
        if (N - R*r - G*g)%B==0:
            if (N - R*r - G*g)//B >= 0:
                ans += 1

print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
n_iter_r = N//R + 1
n_iter_g = N//G + 1

for r in range(n_iter_r):
    for g in range(n_iter_g):
        nokori = N - R*r - G*g
        if nokori < 0:
            break
        else:
            if nokori%B==0:
                ans += 1

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

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

for i in T:
    if T.count(i)>D.count(i):
        print('NO')
        exit()

print('YES')


### FIXED CODE ###

import collections

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

DS=collections.Counter(D)
TS=collections.Counter(T)

for i,k in TS.items():

    if k > DS[i]:
        print('NO')
        exit()

print('YES')
### BUGGY CODE ###

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

grid = []

count_w = [[0] * W for _ in range(H)]
count_h = [[0] * W for _ in range(H)]

for _ in range(H):
  grid.append([x for x in input()])
  

for i in range(H):
  for j in range(W):
    if grid[i][j] == '#':
      count_w[i][j] = 0
      continue
    if j == 0 or grid[i][j - 1] == '#':  # カウントスタート
      count = 0
      k = j
      while k < W and grid[i][k] == '.':
        k += 1
        count += 1
      count_w[i][j] = count      
    else:
      count_w[i][j] = count_w[i][j - 1]  # 左隣と同じ
    
for h in range(H):
  for w in range(W):
    if grid[h][w] == '#':
      count_w[h][w] = 0
      continue
    if w == 0 or grid[h][w - 1] == '#':  # カウントスタート
      count = 0
      k = w
      while k < W and grid[h][k] == '.':
        k += 1
        count += 1
      count_w[h][w] = count      
    else:
      count_w[h][w] = count_w[h][w - 1]  # 左隣と同じ  

for w in range(W):
  for h in range(H):
    if grid[h][w] == '#':
      count_h[h][w] = 0
      continue
    if h == 0 or grid[h - 1][w] == '#':  # カウントスタート
      count = 0
      k = h
      while k < H and grid[k][w] == '.':
        k += 1
        count += 1
      count_h[h][w] = count      
    else:
      count_h[h][w] = count_h[h - 1][w]  # 上と同じ        

print(max(
  count_h[h][w] + count_w[h][w] - 1
  for w in range(W)
  for h in range(H)      
))


### FIXED CODE ###

import sys

input = sys.stdin.readline

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

grid = []

count_w = [[0] * W for _ in range(H)]
count_h = [[0] * W for _ in range(H)]

for _ in range(H):
  grid.append([x for x in input()])
  

for h in range(H):
  r = 0
  count = 0
  for l in range(W):
    while r < W and grid[h][r] == '.':
      r += 1
      count += 1
    count_w[h][l] = count
    if r == l:
      r += 1
      count = 0
      
for w in range(W):
  r = 0
  count = 0
  for l in range(H):
    while r < H and grid[r][w] == '.':
      r += 1
      count += 1
    count_h[l][w] = count
    if r == l:
      r += 1
      count = 0

answer = 0

for h in range(H):
  for w in range(W):
    answer = max(answer, count_h[h][w] + count_w[h][w] - 1)

print(answer)
### BUGGY CODE ###

S=str(input())
S_list=list(S)

Q=int(input())

q=[]
for i in range(Q):
    q.append(input().split())
    if q[i][0]=="1":
        S_list.reverse()
    elif q[i][0]=="2":
        if q[i][1]=="1":
            S_list.reverse()
            S_list.append(q[i][2])
            S_list.reverse()
        elif q[i][1]=="2":
            S_list.append(q[i][2])

S=''.join(S_list)
print(S)

### FIXED CODE ###

S=str(input())
S_list=list(S)

Q=int(input())

q=[]
right=[]
left=[]

rev=1

for i in range(Q):
    q.append(input().split())
    if q[i][0]=="1":
        rev=rev*(-1)
    elif q[i][0]=="2":
        if q[i][1]=="1":
            if rev==1:
                right.append(q[i][2])
            else:
                left.append(q[i][2])
        elif q[i][1]=="2":
            if rev==1:
                left.append(q[i][2])
            else:
                right.append(q[i][2])
right.reverse()
if rev==1:
    S_list=right+S_list+left
else:
    S_list=right+S_list+left
    S_list.reverse()

S=''.join(S_list)
print(S)
### BUGGY CODE ###

N, X, Y = [int(i) for i in input().split()]




p = []

for i in range(1, N):
    for j in range(1, N+1):
        if j<=X:
            p.append(j-i)
        elif j<=Y:
            if i <= X:
                p.append(min(j-i, X-i+1+Y-j))
            else:
                p.append(min(j-i, i-X+1+Y-j))
        else:
            if i <= X:
                p.append(j-i-(Y-X)+1)
            elif i <=Y:
                p.append(min(j-i, i-X+1+j-Y))
            else:
                p.append(j-i)
for k in range(1,N):
    print(sum(x==k for x in p))    

### FIXED CODE ###

N, X, Y = [int(i) for i in input().split()]

p = []

for i in range(1, N):
    for j in range(i+1, N+1):
        if j<=X:
            p.append(j-i)
        elif j<=Y:
            if i <= X:
                p.append(min(j-i, X-i+1+Y-j))
            else:
                p.append(min(j-i, i-X+1+Y-j))
        else:
            if i <= X:
                p.append(j-i-(Y-X)+1)
            elif i <=Y:
                p.append(min(j-i, i-X+1+j-Y))
            else:
                p.append(j-i)
    
import collections
c = collections.Counter(p)
for k in range(1,N):
    print(c[k])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    # Python3で出すことに注意！
    # floyd_warshall

    # https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.floyd_warshall.html
    # ↑を見ながら細部を埋める
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import floyd_warshall

    # (i, j)成分はiからjへの直接経路のコスト
    N=int(input())
    graph = [[0]*N for i in range(N)]
    for i in range(N-1):
        a,b,c=map(int,input().split())
        graph[a-1][b-1]=c


    graph = csr_matrix(graph)

    dist_matrix = floyd_warshall(csgraph=graph, directed=False, return_predecessors=False)
    # (i, j)成分はiからjへの最短コスト
    Q,K=map(int,input().split())
    for i in range(Q):
        x,y=map(int,input().split())
        print(int(dist_matrix[x-1][K-1]+dist_matrix[K-1][y-1]))


resolve()

### FIXED CODE ###

import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        Edge[a-1].append((b-1, c))
        Edge[b-1].append((a-1, c))
    Q, K = map(int, input().split())
    q = deque()
    Dist = [-1] * N
    q.append((K-1, K-1, 0))
    while q:
        nowN, preN, nD = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = nD
            for e, add in Edge[nowN]:
                if e != preN: q.append((e, nowN, nD + add))
    Ans = [None] * Q
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = str(Dist[x-1] + Dist[y-1])
    print("\n".join(Ans))

    return 0

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

from collections import deque
x,y,a,b,c=map(int,input().split())
p=sorted(list(map(int,input().split())),reverse=True)
q=sorted(list(map(int,input().split())),reverse=True)
r=deque(sorted(list(map(int,input().split())),reverse=True))
p=deque(p[:x])
q=deque(q[:y])
ans=sum(p)+sum(q)

while p[-1]<r[0] or q[-1]<r[0]:
  if p[-1]<q[-1]:
    ans+=r[0]-p[-1]
    r.popleft()
    p.pop()
  else:
    ans+=r[0]-q[-1]
    r.popleft()
    q.pop()
  if p==deque([]) or q==deque([]) or r==deque([]):
    break
if r==deque([]):
  pass
elif p==deque([]):
  while q[-1]<r[0]:
    ans+=r[0]-q[-1]
    r.popleft
    q.pop
    if q==deque([]) or r==deque([]):
      break
elif q==deque([]):
  while p[-1]<r[0]:
    ans+=r[0]-p[-1]
    r.popleft
    p.pop
    if p==deque([]) or r==deque([]):
      break
  
print(ans)

### FIXED CODE ###

from collections import deque
x,y,a,b,c=map(int,input().split())
p=sorted(list(map(int,input().split())),reverse=True)
q=sorted(list(map(int,input().split())),reverse=True)
r=deque(sorted(list(map(int,input().split())),reverse=True))
p=deque(p[:x])
q=deque(q[:y])
ans=sum(p)+sum(q)

while p[-1]<r[0] or q[-1]<r[0]:
  if p[-1]<q[-1]:
    ans+=r[0]-p[-1]
    r.popleft()
    p.pop()
  else:
    ans+=r[0]-q[-1]
    r.popleft()
    q.pop()
  if p==deque([]) or q==deque([]) or r==deque([]):
    break
if r==deque([]):
  pass
elif p==deque([]):
  while q[-1]<r[0]:
    ans+=r[0]-q[-1]
    r.popleft()
    q.pop()
    if q==deque([]) or r==deque([]):
      break
elif q==deque([]):
  while p[-1]<r[0]:
    ans+=r[0]-p[-1]
    r.popleft()
    p.pop()
    if p==deque([]) or r==deque([]):
      break
  
print(ans)
### BUGGY CODE ###

s = list(map(int, input().split(" ")))

a = s[0]
b = s[1]
m = s[2]

a_l = list(map(int, input().split(" ")))
b_l = list(map(int, input().split(" ")))

ans = a_l[0] + b_l[0]

for i in a_l:
    for t in b_l:
        if (i + t) < ans:
            ans = i + t

for i in range(m):
    x = list(map(int, input().split(" ")))
    if ans > (a_l[x[0] - 1] + b_l[x[1] -1] - x[2]):
        ans = a_l[x[0] -1] + b_l[x[1] -1] - x[2]
print(ans)

### FIXED CODE ###

s = list(map(int, input().split(" ")))

a = s[0]
b = s[1]
m = s[2]

a_l = list(map(int, input().split(" ")))
b_l = list(map(int, input().split(" ")))

ans = min(a_l) + min(b_l)

for i in range(m):
    x = list(map(int, input().split(" ")))
    if ans > (a_l[x[0] - 1] + b_l[x[1] -1] - x[2]):
        ans = a_l[x[0] -1] + b_l[x[1] -1] - x[2]


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

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

I = 0
J = 0
K = 0
for a in A:
    if a == 1:
        I += 1
    elif a == 2:
        J += 1
    else:
        K += 1

dp = [[[0] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)] 

# def output(lst):
#     for tmp in lst:
#         print (tmp)

for k in range(K + 1):
    for j in range(K + J + 1):
        for i in range(N + 1):
            if i == j == k == 0:
                continue
            tmp = N / (i + j + k)
            if i > 0:
                tmp += i / (i + j + k) * dp[k][j][i - 1]
            if j > 0 and i < N:
                tmp += j / (i + j + k) * dp[k][j - 1][i + 1]
            if k > 0 and j < K + J:
                tmp += k / (i + j + k) * dp[k - 1][j + 1][i]
            dp[k][j][i] = tmp

print (dp[K][J][I])

# output(dp)

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = tuple(map(int, input().split()))

    I = A.count(1)
    J = A.count(2)
    K = A.count(3)
    # for a in A:
    #     if a == 1:
    #         I += 1
    #     elif a == 2:
    #         J += 1
    #     else:
    #         K += 1

    dp = [[[0] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)] 

    # def output(lst):
    #     for tmp in lst:
    #         print (tmp)

    for k in range(K + 1):
        for j in range(K + J + 1 - k):
            for i in range(N + 1 - k  - j):
                if i == j == k == 0:
                    continue
                tmp = N
                if i > 0:
                    tmp += i * dp[k][j][i - 1]
                if j > 0:
                    tmp += j * dp[k][j - 1][i + 1]
                if k > 0:
                    tmp += k * dp[k - 1][j + 1][i]
                dp[k][j][i] = tmp / (i + j + k)

    print (dp[K][J][I])

    # output(dp)

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

N = int(input())

A = []
B = []
C = []
for i in range(N):
    s = input()
    if '.' in s:
        a,b = map(int,s.split('.'))
        if(int(b)==0):
            C.append(a)
        else:
            A.append(a*pow(10,len(s)-s.find('.')-1)+b)
            B.append(pow(10,len(s)-s.find('.')-1))
    else:
        C.append(int(s))

ans = len(C) * (len(C)-1) // 2
for i in range(len(A)):
    for j in range(len(C)):
        if A[i]*C[j]%B[i]==0:
            ans += 1
for i in range(len(A)-1):
    for j in range(i+1,len(A)):
        if (A[i]*A[j])%(B[i]*B[j])==0:
            ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
A = []

for i in range(N):
    s = input()
    if '.' in s:
        a,b = map(int,s.split('.'))
        if(int(b)==0):
            c = a
            d = 1
        else:
            c = a*pow(10,len(s)-s.find('.')-1)+b
            d = pow(10,len(s)-s.find('.')-1)
    else:
        c = int(s)
        d = 1
    e = 0
    f = 0
    while(c != 0 and c%2==0):
        e += 1
        c //= 2
    while(c != 0 and c%5==0):
        f += 1
        c //= 5
    while(d%2==0):
        e -= 1
        d //=2
    while(d%5==0):
        f -= 1
        d //=5
    A.append([e,f])

tm = max(max([a[0] for a in A]), -1 * min([a[0] for a in A])) + 1
fm = max(max([a[1] for a in A]), -1 * min([a[1] for a in A])) + 1

B = [[0] * (tm * 2 ) for _ in range(fm * 2)]

for a in A:
    B[a[1]+fm][a[0]+tm] += 1

for i in range(fm*2):
    for j in range(tm*2):
        if(i>0):
            B[i][j] += B[i-1][j]
        if(j>0):
            B[i][j] += B[i][j-1]
        if(i>0 and j>0):
            B[i][j] -= B[i-1][j-1]

ans = 0
for a in A:
    i = -1 * a[1] + fm
    j = -1 * a[0] + tm
    ans += B[fm*2-1][tm*2-1] - B[fm*2-1][j-1] - B[i-1][tm*2-1] + B[i-1][j-1]
    if a[1]>=0 and a[0]>=0:
        ans -= 1

print(ans//2)
### BUGGY CODE ###

from math import sqrt

n = int(input())
 
def calc(n):
    if n < 6:
        return 0
    if n == 6:
        return 1
    if 6 < n < 11:
        return 0
    if n == 11:
        return 3
    if 11 < n < 17:
        return 0
    if n == 17:
        return 3
    if n == 18:
        return 3
    ans = 0
    for x in range(1, int(sqrt(n))):
        for y in range(1, int(sqrt(n))):
            for z in range(1, int(sqrt(n))):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == n:
                    ans += 1
 
    return ans
 
for i in range(1, n+1):
    print(calc(i))


### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(n+1)]
def calc(n):
    for x in range(1, int(n**0.5)+1):
        for y in range(1, int(n**0.5)+1):
            for z in range(1, int(n**0.5)+1):
                v = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if v < n+1:
                    ans[v] += 1

calc(n)
for i in range(n):
    print(ans[i+1])
### BUGGY CODE ###

S = input()
N = len(str(S))
cubes = [int(i) for i in list(S)]

first_comb = [0]
second_comb = [0]
while len(first_comb) > 0 or len(second_comb) > 0:
  length = len(cubes)
  first_comb = []
  second_comb = []
  for i in range(length - 1):
    if (cubes[i] == 0 and cubes[i + 1] == 1) or (cubes[i] == 1 and cubes[i + 1] == 0):
      if i + 2 <= length - 1 and i - 1 >= 0:
        if (cubes[i + 2] == 0 and cubes[i - 1] == 1) or (cubes[i + 2] == 1 and cubes[i - 1] == 0):
          first_comb.append([i, i + 1])
        else: 
          second_comb.append([i, i + 1])
      else: 
        second_comb.append([i, i + 1])

  if len(first_comb) > 0:
    cubes.pop(first_comb[0][0])
    cubes.pop(first_comb[0][1] - 1)
  elif len(second_comb) > 0:
    cubes.pop(second_comb[0][0])
    cubes.pop(second_comb[0][1] - 1)

print(N - len(cubes))



### FIXED CODE ###

S = input()
N = len(str(S))
cubes = [int(i) for i in list(S)]

one_count = len([i for i in cubes if i == 1])

if one_count > N - one_count:
  print(2 * (N - one_count))
else: 
  print(2 * one_count)
### BUGGY CODE ###

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        # dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    return dp[-1]


def solve_slow(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    # print("\n".join(map(str, dp)))
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


### FIXED CODE ###

# DP
def main():
    N, W = map(int, input().split())

    dp = [-1] * (W + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v
    print(max(dp))


main()
### BUGGY CODE ###

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N,K = list(map(int,input().split()))
A = sorted(tuple(map(int,input().split())))
B = tuple(A[i+1]-A[i]  for i in range(len(A)-1))
lim = math.ceil(len(B)/2)

L = 10**9+7
ans = 0
multi = combinations_count(N,K)
for j in range(lim):
    front = j + 1
    back = N - front
    tmp_b = 0
    tmp_f = 0
    if front >= K:
        tmp_f = combinations_count(front,K) % L
    if back >= K:
        tmp_b = combinations_count(back,K) % L
    if j == (len(B)-1)/2:
        ans += (multi - tmp_b - tmp_f)*(B[j]) % L
    else:
        ans += (multi - tmp_b - tmp_f)*(B[j]+B[len(B)-1-j]) % L
print(ans%L)

### FIXED CODE ###

import math

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5+5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N,K = list(map(int,input().split()))
A = sorted(tuple(map(int,input().split())))
B = tuple(A[i+1]-A[i]  for i in range(len(A)-1))
lim = math.ceil(len(B)/2)

L = 10**9+7
ans = 0
multi = cmb(N,K,mod)
for j in range(lim):
    front = j + 1
    back = N - front
    tmp_b = 0
    tmp_f = 0
    if front >= K:
        tmp_f = cmb(front,K,mod)
    if back >= K:
        tmp_b = cmb(back,K,mod)
    if j == (len(B)-1)/2:
        ans += (multi - tmp_b - tmp_f)*(B[j]) % L
    else:
        ans += (multi - tmp_b - tmp_f)*(B[j]+B[len(B)-1-j]) % L
print(ans%L)
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
nums = list(set(a_list))
nums.sort(reverse=True)
a = 0
b = 0
for num in nums:
	count = a_list.count(num)
	if count > 1:
		if a == 0:
			a = num
			if count > 3:				
				b = num
				break
		else:
			b = num
			break
r = a * b
print(r)

### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
counts = {}
for a in a_list:
	if a in counts:
		counts[a] += 1
	else:
		counts[a] = 1
counts = sorted(counts.items(), reverse=True, key=lambda x: x[0])
a = 0
b = 0
for key, value in counts:
	if value > 1:
		if a == 0:
			a = key
			if value > 3:
				b = key
				break
		else:
			b = key
			break
r = a*b
print(r)
### BUGGY CODE ###

import math

N = int(input())
An = [int(i) for i in input().split()]

sum = 0
for i in range(N - 1):
    Ai = An[i]
    for j in range(i + 1, N):
        Aj = An[j]
        sum += Ai * Aj

mod = int(math.pow(10, 9) + 7)

print(sum % mod)


### FIXED CODE ###

import math

N = int(input())
An = [int(i) for i in input().split()]


mod = int(math.pow(10, 9) + 7)

sum_an = sum(An)
sum_result = 0

for i in range(N - 1):
    Ai = An[i]
    sum_an -= Ai
    sum_result += (Ai * sum_an) % mod


print(sum_result % mod)
### BUGGY CODE ###

a = [] 
while True:
    n = int(input())
    if n == 0:
        break 
    a.append(n)
    count = 0
    for i in a:
        count += 1
    print("Case " + str(count) + ":" + str(n))

### FIXED CODE ###

i = 0
while True:
    n = int(input())
    if n == 0: 
        break
    else:
        i += 1
    print("Case " + str(i) + ": " + str(n))
### BUGGY CODE ###

import numpy as np

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

nA = np.array(A)
nA = np.sort(nA)

for i in range(M):
    a = nA[-1]//2
    nA = np.delete(nA, -1)
    idx = np.searchsorted(nA, a)
    nA = np.insert(nA, idx, a)

print(np.sum(nA))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(lambda a: int(a)*(-1), input().split()))

heapq.heapify(A)

for i in range(M):
    a = -heapq.heappop(A)//2
    heapq.heappush(A, -a)
    
print(-sum(A))