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

N,a,b=map(int,input().split())
m = 10**9+7

M = pow(2, N,m)

m = 10**9+7
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
  

res = 1
for i in range(N-a+1,N+1):
    res = res*i%m
for i in range(1,a+1):
    res = res*mod_inv(i,m)%m

rs = 1
for i in range(N-b+1,N+1):
    rs = rs*i%m
for i in range(1,b+1):
    rs = rs*mod_inv(i,m)%m

print((M-1-res-rs)%m)


### FIXED CODE ###

N,a,b=map(int,input().split())
m = 10**9+7

M = pow(2, N, m)

def nCr(n,r):
    if r*2>n:
        return nCr(n,n-r)
    else:
        a = b = 1
        for i in range(r):
            a = a * (n - i) % m
            b = b * (r - i) % m
        return (a * pow(b,m-2,m)) % m
 
ans = M - 1 - nCr(N,a) - nCr(N,b)
print(ans%m)
### BUGGY CODE ###

import sys
from collections import Counter
from bisect import bisect_left

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

class BitSum:
    def __init__(self, n):
        self.n = n
        self.table = [0] * (n + 1)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    aa = list(Counter(aa).values())
    aa.sort()
    bit = BitSum(len(aa))
    for i, a in enumerate(aa):
        bit.update(i, a)
    # print(aa)
    r0 = bit.sum(len(aa) - 1) + 1
    for k in range(1, n + 1):
        l = 0
        r = r0
        while l + 1 < r:
            m = (l + r) // 2
            i = bisect_left(aa, m)
            s = bit.sum(i - 1) + m * (len(aa) - i)
            if s >= m * k:
                l = m
            else:
                r = m
        print(l)

main()


### FIXED CODE ###

import sys
from collections import Counter
from bisect import bisect_left

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

class BitSum:
    def __init__(self, n):
        self.n = n
        self.table = [0] * (n + 1)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    aa = list(Counter(aa).values())
    aa.sort()
    bit = BitSum(len(aa))
    for i, a in enumerate(aa):
        bit.update(i, a)
    # print(aa)
    for k in range(1, n + 1):
        l = 0
        r = n // k + 2
        while l + 1 < r:
            m = (l + r) // 2
            i = bisect_left(aa, m)
            s = bit.sum(i - 1) + m * (len(aa) - i)
            if s >= m * k:
                l = m
            else:
                r = m
        print(l)

main()
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = sorted(list(map(int,input().split())),reverse=True)
c = Counter(a)
s = list (set(a))
dp = [True] * (10**6+1)

for x in s:
    e = x*2
    # エラトステネスの篩
    while e <= 10 ** 6:
        dp[e] = False
        e += x

ret = 0
for x in a:
    # 重複なし かつ 素数
    if c[x] == 1 and dp[x] == True:
        ret += 1
print(ret)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
dp = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    e = x * 2
    while e <= 10 ** 6:
        dp[e] = False
        e += x
ret = 0
for x in a:
    if c[x] == 1 and dp[x] == True:
        ret += 1
print(ret)
### BUGGY CODE ###

#!/usr/bin/env python3
N, M = [int(str) for str in input().strip().split()]
H = [int(str) for str in input().strip().split()]
AB = [[int(str) - 1 for str in input().strip().split()] for _ in range(M)]


def solve():
    G = [[False] * N for _ in range(N)]
    for a, b in AB:
        G[a][b] = True
        G[b][a] = True

    ans = 0
    visited = [False] * N
    for start in range(N):
        if visited[start]:
            continue
        nexts = [i for i in range(N) if G[start][i]]
        if all([H[start] > H[next] for next in nexts]):
            ans += 1
            for next in nexts:
                visited[next] = True

    print(ans)


solve()


### FIXED CODE ###

#!/usr/bin/env python3
N, M = [int(str) for str in input().strip().split()]
H = [int(str) for str in input().strip().split()]
AB = [[int(str) - 1 for str in input().strip().split()] for _ in range(M)]


def solve():
    G = [0] * N
    for a, b in AB:
        G[a] = max(G[a], H[b])
        G[b] = max(G[b], H[a])

    ans = 0
    for i in range(N):
        if H[i] > G[i]:
            ans += 1

    print(ans)


solve()
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    S = input()
    amari = []
    for i in range(len(S)):
        a = int(S[-(i + 1) :]) % 2019
        amari.append(a)
    print(len(amari) - len(set(amari)) +amari.count(0) )


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    S = input()[::-1] # 入力文字列を逆順で格納
    counts = [0] * 2019
    counts[0] = 1
    num, d = 0, 1

    for char in S:
        num = num + int(char) * d
        num = num % 2019
        d = d * 10
        d = d % 2019
        counts[num] += 1 #余りの数の番号のリストに+1していくことでカウント

    ans = 0
    for cnt in counts:
        ans += cnt * (cnt - 1) // 2
    print(ans)

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def main():
    N = int(input())
    re = [[] for _ in range(N)]
    for i in range(N-1):
        p = int(input())
        re[p-1].append(i+1)

    def dep(x):
        if re[x] == []:
            return 0
        else:
            cl = []
            for ch in re[x]:
                cl.append(dep(ch))
                cl.sort(reverse = True)
            l = len(cl)
            return max(cl[i]+i+1 for i in range(l))
    
    print(dep(0))
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def main():
    N = int(input())
    re = [[] for _ in range(N)]
    for i in range(N-1):
        p = int(input())
        re[p-1].append(i+1)

    def dep(x):
        if re[x] == []:
            return 0
        else:
            cl = []
            for ch in re[x]:
                cl.append(dep(ch))
            cl.sort(reverse = True)
            l = len(cl)
            return max(cl[i]+i+1 for i in range(l))
    
    print(dep(0))
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [int(i) for i in bin(A[i])[2:]]
    B[i] = [0]*(60-len(B[i]))+B[i]

TB=[[0]*n for i in range(60)]
for i in range(60):
    TB[i] = [B[j][i] for j in range(n)]
        
# import numpy as np
#print(TB)
ans=0
for i in range(60):
    now=TB[i]
    q=sum(now)
    ans+= ((pow(2,59-i,mod)* (q*(q-1)))%mod *pow(2,mod-2,mod))%mod
    ans%=mod
ans*=2
ans%=mod


last=0
for i in A:
    last+=i%mod
    last%=mod
last*=(n-1)
last%=mod
print((last-ans)%mod)
    
     


### FIXED CODE ###

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

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [((A[i]>>(59-j))) & 1 for j in range(60)]
    B[i] = [0]*(60-len(B[i]))+B[i]

TB=[[0]*n for i in range(60)]
for i in range(60):
    TB[i] = [B[j][i] for j in range(n)]
        
# import numpy as np
#print(TB)
ans=0
for i in range(60):
    now=TB[i]
    q=sum(now)
    
    ans+= ((pow(2,59-i,mod)* (q*(n-q)))%mod)%mod
    ans%=mod


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

from collections import defaultdict 
import sys
import heapq

sys.setrecursionlimit(10**8)

#N:頂点数   M:辺数
N,M,s,t = map(int,input().split())


#root[n] -> nからいけるlist
root_yen = defaultdict(set)
root_snu = defaultdict(set)


#cost[a][b] = a -> b のコスト
cost_yen = [[0 for i in range(N+1)] for j in range(N+1)]
cost_snu = [[0 for i in range(N+1)] for j in range(N+1)]


#weight[a] = start -> a のコスト 未探索->-1
weight_yen = [-1 for i in range(N+1)]
weight_snu = [-1 for i in range(N+1)]
weight_yen[s] = 0
weight_snu[t] = 0


#q = 次に探索する(確定する)もの q[0]=[w,n]
q_yen = [[0,s]]
q_snu = [[0,t]]
heapq.heapify(q_yen)
heapq.heapify(q_snu)


for i in range(M):
	u,v,a,b = list(map(int,input().split())) #
	
	root_yen[u].add(v)
	root_yen[v].add(u)
	
	root_snu[u].add(v)
	root_snu[v].add(u)
	
	cost_yen[u][v] = a
	cost_yen[v][u] = a
	cost_snu[u][v] = b
	cost_snu[v][u] = b
	
	


def search_yen (n,w_0): #nから更新 w_0:確定コスト
	global cost_yen
	global weight_yen
	global q_yen
		
	for i in list(root_yen[n]):
		w = w_0 + cost_yen[n][i]
		if weight_yen[i] == -1 or weight_yen[i] > w: #未探索orより小さい
			heapq.heappush(q_yen, [w,i])
			weight_yen[i] = w
			
def search_snu (n,w_0): #nから更新 w_0:確定コスト
	global cost_snu
	global weight_snu
	global q_snu
		
	for i in list(root_snu[n]):
		w = w_0 + cost_snu[n][i]
		if weight_snu[i] == -1 or weight_snu[i] > w: #未探索orより小さい
			heapq.heappush(q_snu, [w,i])
			weight_snu[i] = w			
			

while q_yen:
	w,n = heapq.heappop(q_yen)
	search_yen(n,w)
	
while q_snu:
	w,n = heapq.heappop(q_snu)
	search_snu(n,w)
	

finalans = float('inf')
ans_li = []

for i in range(0,N):
	ans = weight_yen[N-i] + weight_snu[N-i]
	finalans = min(finalans, ans)
	ans_li.append(finalans)
	
ans_li.reverse()
syozikin = 10**15


for i in ans_li:
	print(syozikin - i)

### FIXED CODE ###

from collections import defaultdict 
import sys
import heapq

sys.setrecursionlimit(10**8)

#N:頂点数   M:辺数
N,M,s,t = map(int,input().split())


#root[n] -> nからいけるlist
roots = defaultdict(set)

#weight[a] = start -> a のコスト 未探索->-1
weight_yen = [-1 for i in range(N+1)]
weight_snu = [-1 for i in range(N+1)]
weight_yen[s] = 0
weight_snu[t] = 0


for i in range(M):
	u,v,a,b = list(map(int,input().split())) #

	roots[u].add((v,a,b))
	roots[v].add((u,a,b))
		
	
def search_yen (n,w_0): #nから更新 w_0:確定コスト
	global weight_yen
		
	for root in list(roots[n]):
		i = root[0]
		w = w_0 + root[1]
		if weight_yen[i] == -1 or weight_yen[i] > w: #未探索orより小さい
			heapq.heappush(q, [w,i])
			weight_yen[i] = w
			
def search_snu (n,w_0): #nから更新 w_0:確定コスト
	global weight_snu
		
	for root in list(roots[n]):
		i = root[0]
		w = w_0 + root[2]
		if weight_snu[i] == -1 or weight_snu[i] > w: #未探索orより小さい
			heapq.heappush(q, [w,i])
			weight_snu[i] = w

#q = 次に探索する(確定する)もの q[0]=[w,n]
q = [[0,s]]
heapq.heapify(q)
			
while q:
	w,n = heapq.heappop(q)
	search_yen(n,w)
	
heapq.heappush(q, [0,t])
	
while q:
	w,n = heapq.heappop(q)
	search_snu(n,w)
	

finalans = float('inf')
ans_li = []

for i in range(0,N):
	ans = weight_yen[N-i] + weight_snu[N-i]
	finalans = min(finalans, ans)
	ans_li.append(finalans)
	
for i in range(N):
	print(10**15 - ans_li[N-i-1])
### BUGGY CODE ###

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


def main():
    N = int(input())
    S = input()

    R = []
    G = []
    B = []

    for i, s in enumerate(S):
        if s == 'R':
            R.append(i)
            continue
        elif s == 'G':
            G.append(i)
            continue
        elif s == 'B':
            B.append(i)
    

    total = 0

    for r in R:
        for g in G:
            for b in B:
                li = sorted([r, g, b])
                if li[1] - li[0] != li[2] - li[1]:
                    total += 1
    
    print(total)



if __name__ == '__main__':
    main()

### FIXED CODE ###

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


def main():
    N = int(input())
    S = input()

    R = 0
    G = 0
    B = 0

    for s in S:
        if s == 'R':
            R += 1
            continue
        elif s == 'G':
            G += 1
            continue
        elif s == 'B':
            B += 1
    

    total = 0

    for i in range(N-2):
        for j in range(i+1, N-1):
            if 2*j-i >= N:
                break
            if S[i] != S[j] and S[j] != S[2*j-i] and S[2*j-i] != S[i]:
                total += 1

    print(R*G*B - total)


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

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]
C = [c for b, c in BC for _ in range(b)]

A.extend(C)
A.sort(reverse=True)

print(sum(A[:N]))


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]
BC = sorted(BC, key=lambda x: x[1])
A.sort()
i = 0
for b, c in BC[::-1]:
    for _ in range(b):
        if i == N:
            break
        if c > A[i]:
            A[i] = c
            i += 1
        else:
            break

print(sum(A))
### BUGGY CODE ###

n = int(input())
sum = 0
n1 = n
for i in range(n-1,0,-1):
  sum+=i%n1
  n1-=1
print(sum)

### FIXED CODE ###

n = int(input())
print((n*(n-1))//2)
### BUGGY CODE ###

N,K = map(int,input().split(' '))
H = list(map(int,input().split(' ')))
dp = [float('inf')]*N
dp[0] = 0

for i in range(1,N):
  dp[i] = min([dp[j] + abs(H[i] - H[j]) for j in range(max(0,i-K),i)])
  
print(dp[-1])


### FIXED CODE ###

import numpy as np
N,K = map(int,input().split())
H = np.array(list(map(int,input().split())))
dp = np.zeros(N,dtype=int)

for i in range(1,N):
  x = max(0,i-K)
  dp[i] = np.min(dp[x:i] + abs(H[x:i] - H[i]))

print(dp[-1])
### BUGGY CODE ###

import itertools

def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    
    base = [i for i in range(1, 1001)]
    l = list(itertools.accumulate(base))
    r = []
    for i in range(0, len(l)):
        r.append(l[i] / (i+1))

    memo = 0
    maxi = 0
    for i in range(N-M+1):
        if maxi < sum(A[i:M+i]):
            maxi = sum(A[i:M+i])
            memo = i

    ans = 0
    for i in A[memo:M+memo]:
        ans += r[i-1]

    return ans

print(solve())


### FIXED CODE ###

import itertools

def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    # スコアの累積和
    l = list(itertools.accumulate(A))

    score = sum(A[:M])
    for i in range(1, N-M):
        score = max(score, l[i+M] - l[i])
        
    ans = (M + score) / 2

    return ans

print(solve())
### BUGGY CODE ###

ans = 1
x1, x2 = map(int, input().split())
for i in range(2,min(x1,x2)+1):
  if x1 % i == 0 and x2 % i == 0:
    ans += 1
    while x1%i == x2%i == 0:
      x1 //= i
      x2 //= i
print(ans)

### FIXED CODE ###

import sys 
input = sys.stdin.readline
a, b = map(int, input().split())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

A = set(prime_factorize(a))
B = set(prime_factorize(b))
ans = A&B
print(len(ans)+1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10 * 9 + 7

flag = True

if 0 in A:
    if A.count(0) != 1:
        flag = False

for a in set(A):
    if a == 0:
        continue
    if A.count(a) != 2:
        flag = False
        break

if flag:
    print(2 ** (N//2) % MOD)
else:
    print(0)

### FIXED CODE ###

# 人数分布は一意
import numpy as np
MOD = 10**9 + 7
N = int(input())
A = np.array([int(x) for x in input().split()])

left = np.arange(N)
right = N-1-left
cnt_1 = np.bincount(np.abs(left-right))
cnt_2 = np.bincount(A)

if cnt_1.shape != cnt_2.shape or (cnt_1 != cnt_2).any():
    answer = 0
else:
    answer = pow(2, N//2, MOD)

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

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
dp = [10**10] * (10**5)
dp[0] = 0
# ぴったり倒せるときだけ更新して、答えを出力するときに最小値を出力する
for i in range(len(dp)):
    for a, b in AB:
        dp[i] = min(dp[i], dp[i-a]+b)

print(min(dp[H:]))


### FIXED CODE ###

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
dp = [10**10] * (10**4+5)
dp[0] = 0
# ぴったり倒せるときだけ更新して、答えを出力するときに最小値を出力する
for i in range(len(dp)):
    for a, b in AB:
        dp[i] = min(dp[i], dp[i-a]+b)

print(min(dp[H:]))
### BUGGY CODE ###

N = int(input())
S = list(map(str,input()))

R = []
G = []
B = []
for i in range(N):
    if S[i] == "R":
        R.append(i)
    elif S[i] == "G":
        G.append(i)
    else:
        B.append(i)
ans = 0
for i in range(N):
    for j in range(1,N//2+2):
        if i+2*j < N:
            if S[i] != S[i+j] and S[i] != S[i+2*j] and S[i+j] != S[i+2*j]:
                ans +=1

print(len(R)*len(G)*len(B)-ans)

### FIXED CODE ###

N = int(input())
S = list(map(str,input()))

r = 0
g = 0
b = 0
for i in range(N):
    if S[i] == "R":
        r+=1
    elif S[i] == "G":
        g+=1
    else:
        b+=1
ans = 0
for i in range(N):
    for j in range(1,N//2+2):
        if i+2*j < N:
            if S[i] != S[i+j] and S[i] != S[i+2*j] and S[i+j] != S[i+2*j]:
                ans +=1

print(r*g*b-ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1


N = int(input())
A = [int(input()) for _ in range(N)]

max_a = max(A)

for i in range(N):
    if A[i] == max_a:
        tmp = A[i]
        A[i] = NIL
        print(max(A))
        A[i] = tmp
        continue

    print(max_a)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1


N = int(input())
A = [int(input()) for _ in range(N)]

max_a = max(A)
max_idx = [i for i, x in enumerate(A) if x == max_a]

if len(max_idx) > 1:
    for i in range(N):
        print(max_a)
    exit()
else:
    for i in max_idx:
        A[i] = NIL
    second_max = max(A)

    for i in range(N):
        if i in max_idx:
            print(second_max)
        else:
            print(max_a)
### BUGGY CODE ###

N, M = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
mod = 10 ** 9 + 7
a_set = set(a_list)
b_set = set(b_list)

if len(a_set) < N or len(b_set) < M:
    print(0)
    exit()


a_list.sort(reverse=True)
b_list.sort(reverse=True)
a_list.append(-1)
b_list.append(-1)
ans = 1
a_i = 0
b_i = 0
for i in range(N*M, 0, -1):
    if i == a_list[a_i] and i == b_list[b_i]:
        a_i += 1
        b_i += 1
    elif i == a_list[a_i]:
        a_i += 1
        ans *= b_i % mod
    elif i == b_list[b_i]:
        b_i += 1
        ans *= a_i % mod
    else:
        ans *= (a_i*b_i - (N * M - i)) % mod
print(ans % mod)



### FIXED CODE ###

N, M = map(int, input().split())
a_list = tuple(map(int, input().split()))
b_list = tuple(map(int, input().split()))
mod = 10 ** 9 + 7

a_list = sorted(a_list, reverse=True)
b_list = sorted(b_list, reverse=True)
a_list.append(-1)
b_list.append(-1)
ans = 1
a_i = 0
b_i = 0
for i in range(N*M, 0, -1):
    if i == a_list[a_i] and i == b_list[b_i]:
        a_i += 1
        b_i += 1
    elif i == a_list[a_i]:
        a_i += 1
        ans *= b_i
        ans %= mod
    elif i == b_list[b_i]:
        b_i += 1
        ans *= a_i
        ans %= mod
    else:
        ans *= (a_i*b_i - (N * M - i))
        ans %= mod
print(ans % mod)
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
	a.append(int(input()))
b=['']*n
b[0]='hoge'
c=0
x=0
while True:
	c+=1
	x=a[x]-1
	if b[x]=='hoge':
		c=-1
		break
	else:
		if x==1:
			break
print(c)



### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
	a.append(int(input()))
b=['']*n
b[0]='hoge'
c=0
x=0
while True:
	c+=1
	x=a[x]-1
	if b[x]=='hoge':
		c=-1
		break
	else:
		b[x]='hoge'
		if x==1:
			break
print(c)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
AA = sorted([ a - i - 1 for i,a in enumerate(A) ])
C = []
for i,a in enumerate(AA):
    if i == 0:
        C.append(a)
    else:
        C.append(C[-1] + a)
ans = ""
#print(C)
for b in AA:
    sample = 0
    num = 0
    for i,a in enumerate(AA):
        if b <= a:
            num = i -1 
            break
        else:
            num = i
    if num == -1:
        sample = C[-1]  - b * (N - 2 * (num + 1))
    else:
        sample = C[-1] - 2 * C[num] - b * (N - 2 * (num + 1))
    if ans == "":
        ans = sample
    if ans > sample:
        ans = sample
if ans == "":
    ans = 0
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
AA = sorted([ a - i - 1 for i,a in enumerate(A) ])
C = []
for i,a in enumerate(AA):
    if i == 0:
        C.append(a)
    else:
        C.append(C[-1] + a)
ans = ""
#print(C)
for i,b in enumerate(AA):
    sample = 0
    num = i-1
    if num == -1:
        sample = C[-1]  - b * (N - 2 * (num + 1))
    else:
        sample = C[-1] - 2 * C[num] - b * (N - 2 * (num + 1))
    if ans == "":
        ans = sample
    if ans > sample:
        ans = sample
if ans == "":
    ans = 0
print(ans)
### BUGGY CODE ###

n=int(input());c=[0]*3;l=[1.0/i for i in range(1,n+1)]
for i in map(int,input().split()):c[i-1]+=1
x,y,z=c;dp=[[[-1]*(z+2) for i in range(n-x+2)]for i in range(n+2)]
for k in range(z+1):
  for j in range(n-x-k+1):
    for i in range(n-k-j+1):
      if i+j+k:dp[i][j][k]=(n+dp[i-1][j][k]*i+dp[i+1][j-1][k]*j+dp[i][j+1][k-1]*k)*l[i+j+k-1]
print(dp[x][y][z]+1)

### FIXED CODE ###

n,a=int(input()),map(int,input().split());c=[0]*3
for i in a:c[i-1]+=1
x,y,z=c;dp=[[[None]*(z+2) for i in range(n-x+2)]for i in range(n+2)];dp[0][0][0]=0
for k in range(z+1):
  for j in range(n-x-k+1):
    for i in range(n-k-j+1):
      if i+j+k:dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)/(i+j+k)
print(dp[x][y][z])
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(input())-1 for i in range(m)]
mod = 1000000007

dp = [0 for i in range(n+1)]
dp[0] = 1
for i in range(n):
  if not i in a:
    dp[i+1] = (dp[i] + dp[i-1])%mod
print(dp[len(dp)-1])
  

### FIXED CODE ###

n, m = map(int, input().split())
a = [int(input())-1 for i in range(m)]
mod = 1000000007

dp = [0 for i in range(n+1)]
for i in a:
  dp[i+1] = -1

dp[0] = 1
for i in range(n):
  if dp[i+1] >= 0:
    dp[i+1] = (dp[i] + dp[i-1])%mod
  else:
    dp[i+1] = 0
print(dp[len(dp)-1])
### BUGGY CODE ###

n,m=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
List=A
for i in range(m):
    a,b=[int(i) for i in input().split()]
    for j in range(a):
        List.append(b)
List.sort()
#print(List)
print(sum(List[-n:]))


### FIXED CODE ###

N,M = [int(x) for x in input().split()]

A = [int(x) for x in input().split()]
A.sort()
max = 0
BC = []
for i in range(M):
    b,c = [int(x) for x in input().split()]
    max += b
    BC.append([c,b])

BC.sort(reverse = True)
str =[]
for c,b in BC:
    str+=[c]*b
    # print(str)
    if(len(str) > N):
        break

now = 0
for i in range(len(A)):
    if(now >= max or str[now] < A[i]):
        break
    if(A[i] < str[now]):
        A[i] = str[now]
        now+=1

# print(A)
print(sum(A))