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

class Solver(object):
    def __init__(self):
        self.n = int(input())
        self.a_s = list(map(int, input().split(" ")))
        self._sadness = {}

    def do_solve(self, b, length):
        b = 0
        current = self.sadness(b)
        left = self.sadness(b-1)
        right = self.sadness(b+1)
        while True:
            # print("{}: {} {} {}".format(b, left, current, right))
            if (left >= current) and (right >= current):
                return b
            elif left < right:  # go left
                b -= 1
            else:  # go right
                b += 1
            current = self.sadness(b)
            left = self.sadness(b-1)
            right = self.sadness(b+1)

    def solve(self):
        b = self.a_s[0] - 1
        for i in range(1, self.n+1):
            b = self.do_solve(b, i)
        print(self.sadness(b))
        
    def sadness(self, b):
        if b not in self._sadness:
            self._sadness[b] = sum(abs(self.a_s[i] - (b+i+1)) for i in range(self.n))
        return self._sadness[b]


if __name__ == "__main__":
    s = Solver()
    s.solve()

### FIXED CODE ###

class Solver(object):
    def __init__(self):
        self.n = int(input())
        self.a_s = list(map(int, input().split(" ")))
        self._sadness = {}

    def solve(self):
        array = self.a_s.copy()
        for i in range(self.n):
            array[i] -= i + 1
        array.sort()
        b = array[len(array) // 2]
        print(self.sadness(b))
        
    def sadness(self, b):
        if b not in self._sadness:
            self._sadness[b] = sum(abs(self.a_s[i] - (b+i+1)) for i in range(self.n))
        return self._sadness[b]


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

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

max_A = max(A)
table = [False]*(max_A+1)
for i in A:
    if table[i] == False:
        table[i] = True
    else:
        table[i] = -1

mem = []        
for i in A:
    if table[i] == -1:
        table[i] = True
        mem.append(i)

for i in range(1, max_A+1):
    if table[i] == True:
        n = 2
        while i*n < max_A+1:
            table[i*n] = False
            n += 1

for i in range(max_A+1): 
    if i in mem and table[i] == True:
        table[i] = False
        
print(table.count(True))

### FIXED CODE ###

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

max_A = max(A)
table = [False]*(max_A+1)
for i in A:
    if table[i] == False:
        table[i] = True
    else:
        table[i] = -1

mem = []        
for i in A:
    if table[i] == -1:
        table[i] = True
        mem.append(i)

for i in range(1, max_A+1):
    if table[i] == True:
        n = 2
        while i*n < max_A+1:
            table[i*n] = False
            n += 1

for i in mem: 
    if table[i] == True:
        table[i] = False
        
print(table.count(True))
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return
#B
def B():

    return

#C
def C():
    n = I()
    s = S()
    d = defaultdict(lambda : 0)
    m = 1<<n
    for i in range(m):
        r = []
        b = []
        for j in range(n):
            if i&(1<<j):
                r.append(s[j])
            else:
                b.append(s[j])
        r,b = b[::-1],r[::-1]
        d[(tuple(r),tuple(b))] += 1
        
    ans = 0
    for i in range(m):
        r = []
        b = []
        for j in range(n):
            if i&(1<<j):
                r.append(s[j+n])
            else:
                b.append(s[j+n])
        ans += d[(tuple(r),tuple(b))]
    print(ans)
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return
#B
def B():

    return

#C
def C():
    n = I()
    s = S()
    d = defaultdict(lambda : 0)
    alp = list("abcdefghijklmnopqrstuvwxyz")
    f = {}
    for i in range(26):
        f[alp[i]] = i+1
    for i in range(2*n):
        s[i] = f[s[i]]
    for i in range(n>>1):
        s[i],s[n-i-1] = s[n-i-1],s[i]
    k = 27
    m = 1<<n
    p = [1<<j for j in range(n)]
    for i in range(m):
        r = 0
        b = 0
        for j in range(n):
            if i&p[j]:
                r *= k
                r += s[j]
            else:
                b *= k
                b += s[j]
        d[(r,b)] += 1
    ans = 0
    for i in range(m):
        r = 0
        b = 0
        for j in range(n):
            if i&p[j]:
                r *= k
                r += s[j+n]
            else:
                b *= k
                b += s[j+n]
        ans += d[(r,b)]
    print(ans)
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()
### BUGGY CODE ###

import copy

n = int(input())
x = [int(num) for num in input().split()]

for i in range(n):
    x_ = copy.copy(x)
    del x_[i]

    x_ = sorted(x_)
    b = x_[(n//2 - 1)]
    print(b)

### FIXED CODE ###

n = int(input())
x = [int(num) for num in input().split()]
xx = sorted(x)

mid_l = xx[n//2 -1]
mid_r = xx[n//2]

for _ in x:
    if _ <= mid_l:
        print(mid_r)
    else:
        print(mid_l)
### BUGGY CODE ###

s = input()
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
d = 0

for c in s[::-1]:
    if d == 0:
        d += 1
        if c == "?":
            for i in range(10):
                table[1][i] = 1
        else:
            table[1][int(c)] = 1
        continue
    if c == "?":
        for n in range(10):
            for i in range(13):
                table[d + 1][(i + n * 10 ** d) % 13] += table[d][i]

    else:
        for i in range(13):
            table[d + 1][(i + int(c) * 10 ** d) % 13] += table[d][i]
    d += 1

    for j in range(13):
        table[d + 1][j] %= mod
print(table[d][5] % mod)

### FIXED CODE ###

s = input()
s = s[::-1]
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
table[0][0] = 1
dd = 1
for c in range(len(s)):
    if s[c] == "?":
        for n in range(10):
            for i in range(13):
                table[c + 1][(i + n * dd) % 13] += table[c][i]
                table[c + 1][(i + n * dd) % 13] %= mod
    else:
        num = int(s[c])
        for i in range(13):
            table[c + 1][(i + num * dd) % 13] += table[c][i]
            table[c + 1][(i + num * dd) % 13] %= mod
    dd = (dd * 10) % 13
print(table[c + 1][5])
### BUGGY CODE ###

R,C,K=map(int,input().split())
vl=[[0 for _c in range(C)] for _r in range(R)]
for _ in range(K):
  r,c,v=map(int,input().split())
  vl[r-1][c-1]=v
dp=[[[0 for _ in range(4)]for _ in range(C+1)]for _ in range(R+1)]
for i in range(1,R+1):
  for j in range(1,C+1):
    for k in range(4):
      dp[i][j][k]=max(dp[i][j-1][k],dp[i-1][j][3])
    for k in range(3,0,-1):
      dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]+vl[i-1][j-1])
print(dp[R][C][3])

### FIXED CODE ###

import numpy as np
from numba import njit
R,C,K=map(int,input().split())
vl=np.zeros((R,C), np.int64)
for _ in range(K):
  r,c,v=map(int,input().split())
  vl[r-1][c-1]=v
@njit
def main():
  dp=np.zeros((R+1,C+1,4), np.int64)
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4):
        dp[i][j][k]=max(dp[i][j-1][k],dp[i-1][j][3])
      for k in range(3,0,-1):
        dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]+vl[i-1][j-1])
  return dp[R][C][3]
print(main())
### BUGGY CODE ###

N = int(input())
i,j = 1,1
while i<3501 and j<3501:
    if N/i >= 4:
        i += i
        continue
    if N/j >= 4:
        j += j
        continue
    i = i//2
    j = j//2
    for x in range(i,3501):
        for y in range(j,3501):
            if (4*x*y - N*y - N*x) == 0:
                continue
            z = N*x*y/(4*x*y - N*y - N*x)
            if z == int(z) and z >= 1:
                print(x,y,int(z))
                exit()

### FIXED CODE ###

N = int(input())
i = 1
while i<=7000:
    if N/i >= 4:
        i += 100
        continue
    if i >100:
        i -= 100
    for x in range(i,3501):
        for y in range(i,3501):
            a = (4*x*y - N*y - N*x)
            if a == 0:
                continue
            z = N*x*y/a
            if z == int(z) and z >= 1:
                print(x,y,int(z))
                exit()
### BUGGY CODE ###

import sys

readline = sys.stdin.readline

N, M = map(int, readline().split())
S = list(map(int, readline().split()))
T = list(map(int, readline().split()))

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

for x in range(1, N + 1):
    for y in range(1, M + 1):
        dp[x][y] = dp[x][y - 1] + dp[x - 1][y] - dp[x - 1][y - 1]
        if S[x - 1] == T[y - 1]:
            dp[x][y] += dp[x - 1][y - 1] + 1
ans = (dp[N][M] + 1) % (10 ** 9 + 7)
print(ans)


### FIXED CODE ###

import sys

readline = sys.stdin.readline

N, M = map(int, readline().split())
S = list(map(int, readline().split()))
T = list(map(int, readline().split()))

P = 10 ** 9 + 7

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

for x in range(1, N + 1):
    for y in range(1, M + 1):
        dp[x][y] = dp[x][y - 1] + dp[x - 1][y] - dp[x - 1][y - 1]
        if S[x - 1] == T[y - 1]:
            dp[x][y] += dp[x - 1][y - 1] + 1

        dp[x][y] = dp[x][y] % P

ans = dp[N][M] + 1
print(ans % P)
### BUGGY CODE ###

N, M = [int(str) for str in input().strip().split()]
A = [int(str) for str in input().strip().split()]

sums = [0]
for i in range(N):
    sums.append(sums[-1] + A[i])
    if sums[i] > M:
        sums[i] -= M

ans = 0
for l in range(N):
    for r in range(l + 1, N + 1):
        if (sums[r] - sums[l]) % M == 0:
            ans += 1

print(ans)

### FIXED CODE ###

N, M = [int(str) for str in input().strip().split()]
A = [int(str) for str in input().strip().split()]

ssum = 0
B = {}
for i in range(N):
    ssum += A[i]
    key = ssum % M
    B[key] = B.get(key, 0) + 1

print(B.get(0, 0) + sum([i * (i - 1) for i in B.values()]) // 2)
### BUGGY CODE ###

N, W = map(int, input().split(" "))
weights = []
values = []

for _ in range(N):
    w, v = map(int, input().split(" "))
    weights.append(w)
    values.append(v)

dp = [[None for _ in range(W+1)] for _ in range(N+1)]
for _ in range(W+1):
    dp[0][_] = 0

for i in range(N):
    item_weight = weights[i]
    for j in range(W+1):
        if j >= item_weight:
            dp[i+1][j] = max([dp[i][j-weights[i]] + values[i], dp[i][j]])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split(" "))
weights = []
values = []

for _ in range(N):
    w, v = map(int, input().split(" "))
    weights.append(w)
    values.append(v)

dp = [[None for _ in range(W+1)] for _ in range(N+1)]
for _ in range(W+1):
    dp[0][_] = 0

for i in range(N):
    item_weight = weights[i]
    for j in range(W+1):
        if j >= item_weight:
            dp[i+1][j] = max([dp[i][j-weights[i]] + values[i], dp[i][j]])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[N][W])
### BUGGY CODE ###

from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return dp[-1][-1]
print(knapsack(n,w,li))

### FIXED CODE ###

from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return max(dp[-1])
print(knapsack(n,w,li))
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
lr = [list(map(int,input().split())) for i in range(q)]
ac_list = [i+1 for i,(j,k) in enumerate(zip(s[0:len(s)-1],s[1:])) if j+k=='AC']
for i in lr:
    count = 0
    for j in ac_list:
        if j>=i[0] and j<=i[1]-1:
            count += 1
    print(count)


### FIXED CODE ###

n,q = map(int,input().split())
s = input()
t = [0]*(n+1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2]=="AC" else 0)
for i in range(q):
    l,r = map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

modulo = 1000000007

import sys
sys.setrecursionlimit(100000009)


muchii = []


def recursie(x, y):
    alb = 1
    negru = 1
    for elem in muchii[x]:
        if elem == y:
            continue
        result_1, result_2 = recursie(elem, x)
        alb = (alb * (result_1 + result_2)) % modulo
        negru = (negru * result_1) % modulo
    return alb, negru
    

if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    for i in range(n):
        muchii.append([])
        
    for i in range(n-1):
        numbers = list(map(int, input().split(" ")))
        
        x = numbers[0]
        y = numbers[1]
        
        muchii[x-1].append(y-1)
        muchii[y-1].append(x-1)
        
    result_1, result_2 = recursie(0, None)
    
    result = (result_1 + result_2) % modulo
    
    print(result)


### FIXED CODE ###

modulo = 1000000007

import sys
sys.setrecursionlimit(100000009)


muchii = []


def recursie(x, y):
    alb = 1
    negru = 1
    for elem in muchii[x]:
        if elem == y:
            continue
        result_1, result_2 = recursie(elem, x)
        alb = (alb * (result_1 + result_2)) % modulo
        negru = (negru * result_1) % modulo
    return alb, negru
    

if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    for i in range(n):
        muchii.append([])
        
    for i in range(n-1):
        numbers = list(map(int, input().split(" ")))
        
        x = numbers[0]
        y = numbers[1]
        
        muchii[x-1].append(y-1)
        muchii[y-1].append(x-1)
        
    result_1, result_2 = recursie(0, None)
    
    result = (result_1 + result_2) % modulo
    
    print(result)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
a,b = map(int, input().split())
c = str(input())

for i in range(0,b):
    d,e = map(int, input().split())
    moji = c[d-1:e]
    
    count = 0
    for t in range(0,len(moji)-1):
        if moji[t]+moji[t+1] == "AC":
            count = count + 1
    print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import accumulate
a,b = map(int, input().split())
c = str(input())
d = [list(map(int, input().split())) for i in range(0,b)]

flg = []
for i in range(a-1):
    moji = c[i:i+2]
    if moji == "AC":
        flg.append(1)
    else:
        flg.append(0)

flg2 = [0] + flg
flg2 = list(accumulate(flg2))

for a in d:
    print(flg2[a[1]-1] - flg2[a[0]-1])
### BUGGY CODE ###

S = input()
Q = int(input())
reverse = False
for i in range(Q):
    query = input().split()
    if query[0] == '1':
        reverse = not reverse
    else:
        if query[1] == '1':
            if not reverse:
                S = query[2] + S
            else:
                S = S + query[2]
        else:
            if reverse:
                S = query[2] + S
            else:
                S = S + query[2]
if reverse: S = S[::-1]
print(S)

### FIXED CODE ###

from collections import deque

S = deque(list(input()))
Q = int(input())
reverse = True
for i in range(Q):
    query = input().split()
    if query[0] == '1':
        reverse = not reverse
    else:
        right = query[1] == '1'
        if right == reverse:
            S.appendleft(query[2])
        else:
            S.append(query[2])
if not reverse:
    print(''.join(list(reversed(S))))
else:
    print(''.join(list(S)))
### BUGGY CODE ###

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

h = [int(x) for x in input().split()]
sorted_h = sorted(h, reverse=True)

for i in range(k):
    if len(sorted_h) > 0:
        sorted_h.pop(0)
    else:
        break
print(sum(sorted_h))


### FIXED CODE ###

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

h = [int(x) for x in input().split()]

if len(h) <= k:
    print(0)
else:
    sorted_h = sorted(h, reverse=True)
    print(sum(sorted_h[k:]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
max_f = 0
for d in range(41,-2,-1):
    if (d != -1 and not (K & 1 << d)):
        continue
    f=0
    for e in range(41,-1,-1):
        mask = 1<<e
        num=0
        for a in A:
            if a&mask:
                num+=1
        n_num = N - num
        if e>d:
            if K&mask:
                f += mask*n_num
            else:
                f += mask*num
        elif e==d:
            f += mask*num
        else:
            f += mask*max(n_num,num)
    max_f = max(f,max_f)
print(max_f)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
"""
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
max_A = max(A)
bit = bin(K)
if max_A > K:
    bit = bin(max_A)"""
max_f = 0
#for d in range(1,len(bit))[::-1]:
for d in range(41,-2,-1):
    #d=d-2
    if (d != -1 and not (K & 1 << d)):
        continue
    f=0
    #for e in range(2,len(bit))[::-1]:
    for e in range(41,-1,-1):
        #e=e-2
        mask = 1<<e
        num=0
        for a in A:
            if a&mask:
                num+=1
        n_num = N - num
        if e>d:
            if K&mask:
                f += mask*n_num
            else:
                f += mask*num
        elif e==d:
            f += mask*num
        else:
            f += mask*max(n_num,num)
    max_f = max(f,max_f)
print(max_f)
### BUGGY CODE ###

S = int(input())
n = len(str(S))
dp = [0]*2019
dp[0] = 1
for i in range(1,n+1):
    X =S%10**i % 2019
    dp[X] += 1
answer = 0
for i in range(2019):
    answer += dp[i]*(dp[i]-1)/2
print(int(answer))

### FIXED CODE ###

S = input()[::-1]
n = len(S)
dp = [0]*2019
dp[0] = 1
X = 0
Y = 1
for s in S:
    Z=(int(s)*Y)%2019
    X = (X+Z)%2019
    dp[X] += 1
    Y = (10*Y)%2019
answer = 0
for i in range(2019):
    answer += dp[i]*(dp[i]-1)/2
print(int(answer))
### BUGGY CODE ###


class BIT:
    # 1-indexed
    def __init__(self, n):
        self.size = n + 1
        self.bit = [0] * self.size

    def add(self, i, x):
        # Add x to a[i]
        while i < self.size:
            self.bit[i] += x
            i += i & -i

    def sumup(self, i):
        # Sum a[1]~a[i]
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

    def query(self, i, j):
        # Sum a[i]~a[j]
        return self.sumup(j) - self.sumup(i - 1)


N, Q = map(int, input().split())
C = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(Q)]

ans = [0] * Q
bit = BIT(N + 1)
last = [0] * (N + 1)
k = 0
for i, (l, r) in sorted(enumerate(X), key=lambda x: x[1][1]):
    for j in range(k + 1, r + 1):
        if last[C[j - 1]] > 0:
            bit.add(last[C[j - 1]], -1)

        bit.add(j, 1)
        last[C[j - 1]] = j

    k = r
    ans[i] = bit.query(l, r)

print(*ans, sep="\n")


### FIXED CODE ###

class BIT:
    # 1-indexed
    def __init__(self, n):
        self.size = n + 1
        self.bit = [0] * self.size

    def add(self, i, x):
        """Add x to a[i]."""
        while i < self.size:
            self.bit[i] += x
            i += i & -i

    def sumup(self, i):
        """Sum a[1]~a[i]."""
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

    def query(self, i, j):
        """Sum a[i]~a[j]."""
        return self.sumup(j) - self.sumup(i - 1)


N, Q = map(int, input().split())
C = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(Q)]

ans = [0] * Q
last_appeared = [0] * (N + 1)
bit = BIT(N + 1)
rm = 0
for i, (l, r) in sorted(enumerate(X), key=lambda x: x[1][1]):
    for j in range(rm + 1, r + 1):
        if last_appeared[C[j - 1]] > 0:
            bit.add(last_appeared[C[j - 1]], -1)
        last_appeared[C[j - 1]] = j
        bit.add(j, 1)

    rm = r
    ans[i] = bit.query(l, r)

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

# -*- coding: UTF-8 -*-
# ABC073_C

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

for i in range(0, N, 1):
    x = input()
    if (x not in list):
        list.append(x)
    else:
        list.remove(x)
print(len(list))


### FIXED CODE ###

# -*- coding: UTF-8 -*-
# ABC073_C

N = int(input())
ans = set()

for i in range(N):
    x = int(input())
    if (x in ans):
        ans.remove(x)
    else:
        ans.add(x)
print(len(ans))
### BUGGY CODE ###

import bisect

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

for _ in range(M):
    a = A2.pop()
    a2=a>>1
    bisect.insort_right(A2,a2)
    #print(A2)

print(sum(A2))

### FIXED CODE ###

from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import sys
import logging
import heapq
logging.basicConfig(level=logging.DEBUG)

input = sys.stdin.readline

setrecursionlimit(1000000)

def main():
    N,M=[int(x) for x in input().split()]
    A=[-int(x) for x in input().split()]

    heapq.heapify(A)
    for _ in range(M):
        a = -heapq.heappop(A) // 2 # 最小値取得
        heapq.heappush(A, -a)
    
    print(-sum(A))

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc.sort(key=lambda x:x[1], reverse=True)
result = 0
for [b,c] in bc:
    if len(a) == 0 or c < a[0]:
        break
    result = result + sum(list(map(lambda x: x if c < x else c, a[0:b])))
    a = a[b:]
print(sum(a)+result)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc.sort(reverse=True, key=lambda x:x[1])
l=[]
for [b,c] in bc:
    l.extend([c]*b)
    if n < len(l):
        break
for i in range(n):
    if len(l) <= i or l[i] <= a[i]:
        break
    a[i] = l[i]
print(sum(a))