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



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

ans = 0
mod = 10**9 + 7


b = bin(max(A))

l = len(b) - 2


for j in range(l):
    tmp = 0
    for i in range(N):
        if (A[i] >> j) % 2 == 1:
            tmp += 1

    ans += (2**j) * tmp * (N-tmp)
    ans %= mod
print(ans)


### FIXED CODE ###



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

ans = 0
mod = 10**9 + 7


b = bin(max(A))

l = len(b) - 2


for j in range(l):
    tmp = 0
    for i in range(N):
        if (A[i] >> j) % 2 == 1:
            tmp += 1

    ans += (2**j) * tmp * (N-tmp)
    ans %= mod
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

S = input()

MOD =[1,0,0,0,0,0,0,0,0,0,0,0,0]
NMOD =[0,0,0,0,0,0,0,0,0,0,0,0,0]

R10 = range(10)
R13 = range(13)

for i,D in enumerate(S):
    C = -1
    if D != '?':
        C = int(D)
    #end if
    for N in R10:
        if C >= 0 and C != N:
            continue
        for M in R13:
            NM = (M * 10 + N) % 13
            NMOD[NM] += MOD[M]
        #end for
    #end for
    for M in R13:
        MOD[M] = NMOD[M]%1000000007
        NMOD[M] = 0
    #end for
#end for

print(MOD[5])


### FIXED CODE ###

# -*- coding: utf-8 -*-

R10 = range(10)
R13 = range(13)

S = input()
R = [[(M-N)*4 % 13 for N in R10] for M in R13]
AM = 10**9+7

MOD =[1]+[0]*12

for D in S:
    if D == '?':
        MOD = [sum([MOD[N] for N in M])%AM for M in R]
    else:
        C = int(D)
        MOD = [MOD[M[C]] for M in R]
    #end if
#end for

print(MOD[5])
### BUGGY CODE ###

# coding: utf-8
# Your code here!

def pin(type=int):
    return eval("map(type,input().split())")
#1行ごとに読み込んでいる
#変数一個だけのときはカンマを入れるだけ、input()相当。ちょろい。
#下記のようにsum関数などintを相手にした関数を書く時に便利なのでデフォルトをint型にする
N,M = pin()
p=[0 for i in range(0,M)]
S=[0 for i in range(0,M)]
for i in range(0,M):
    p[i],S[i] =pin(str)

#print(p,S)
#ACした問題番号と各々の問題（後々AC下かを考えない）ペナ数を問題番号別にまとめた配列
AC=[0 for i in range(0,N)]
Penalties = [0 for i in range(0,N)]
#問題番号iと回答番号jについて,
for i in range(0,N):
    for j in range(0,M):
    
        #jがiの回答である時に,WAだったらPenaltiesに1個加算
        if int(p[j])-1==i:
            if (S[j]) == 'WA':
                Penalties[int(p[j])-1] += 1
            else:#それが初めてのACならば、AC数に1を足してcontinueで次の問題i+1へ移る
                AC[int(p[j])-1] = 1
                break
            #print(AC,Penalties)
#print(AC,Penalties)
acnum=0
pennum=0
for i in range(0,N):
    acnum += AC[i]
    if AC[i]==1:
        pennum += Penalties[i]

print(acnum,pennum)

### FIXED CODE ###

# coding: utf-8
# Your code here!

def pin(type=int):
    return map(type,input().split())
#1行ごとに読み込んでいる
#変数一個だけのときはカンマを入れるだけ、input()相当。ちょろい。
#sum関数などintを相手にした関数を書く時に便利なのでデフォルトをint型にする

N,M = pin() 
p=[0 for j in range(0,M)]
S=[0 for j in range(0,M)]
for j in range(0,M):
    p[j],S[j] =pin(str) #p_i,S_iにそれぞれ対応
    #print("sah")
# O(3M)...?
#print(p)
#print(p,S)
#ACした問題番号と各々の問題（後々AC下かを考えない）ペナ数を問題番号別にまとめた配列
AC=[0 for i in range(0,N)]
Penalties = [0 for i in range(0,N)]

#問題番号iと回答番号jについて,
"""
for i in range(0,N):
    for j in range(0,M):
    
        #jがiの回答である時に,WAだったらPenaltiesに1個加算
        if int(p[j])-1==i:
            if (S[j]) == 'WA':
                Penalties[int(p[j])-1] += 1
            else:#それが初めてのACならば、AC数に1を足してcontinueで次の問題i+1へ移る
                AC[int(p[j])-1] = 1
                break
            #print(AC,Penalties)
"""
#double-loop だと　TLEしてしまう O(n^2)はだめみたい

#singleloopしかないねぇ
#回答番号jに着目する
for j in range (0,M):
    if S[j] == "AC":
        if AC[int(p[j])-1]==1:
            continue
        else:
            AC[int(p[j])-1]=1
    else:#wa or something
        if AC[int(p[j])-1]==1:
            continue
        else:
            Penalties[int(p[j])-1]+=1
  # print(AC,Penalties)

for i in range(0,N):
    if AC[i] == 0:
        Penalties[i]=0
#print("///////")    
#print(AC,Penalties)    



#ACリスト内の1の数を数えるのは iter.countだね
print(AC.count(1),sum(Penalties))
### BUGGY CODE ###

# coding: utf-8

def main():
	N = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]

	xor_a = [a[i] ^ a[(i+1) % N] for i in range(len(a))]
	xor_b = [b[i] ^ b[(i+1) % N] for i in range(len(b))]

	bm = BMSearch(xor_a + xor_a, xor_b)

	start = 0
	ans = []
	x = []
	while True:
		k = bm.search(start)
		if k == -1 or k == len(a):
			break
		ans.append(k)
		start = k + 1
		x.append(a[0 + k] ^ b[0])

	for i in range(len(ans)):
		print(str(ans[i]) + " " + str(x[i]))

class BMSearch:
	def __init__(self, target, pattern):
		self.target = target
		self.pattern = pattern
		self.__table = self.__create_BM_table()

	def search(self, start=0):

		if len(self.pattern) > len(self.target):
			return -1

		i = len(self.pattern) - 1 + start
		p = len(self.pattern) - 1
		while i < len(self.target):
			if self.pattern[p] == self.target[i]:
				i -= 1
				p -= 1

				if p == -1:
					return i + 1
			else:
				t = self.__table[self.target[i]] if (self.target[i] in self.__table) else len(self.pattern)
				i += max(t, len(self.pattern) - p)
				p = len(self.pattern) - 1

		return -1

	def __create_BM_table(self):
		table = {}

		for i in range(len(self.pattern)):
			table[self.pattern[i]] = len(self.pattern) - i - 1

		return table

if __name__ == "__main__":
	main()

### FIXED CODE ###

# coding: utf-8

def main():

	# N = 0
	# a = []
	# b = []
	# with open("C:/Users/admin/Downloads/random_05") as f:
	# 	N = int(f.readline())
	# 	a = [int(x) for x in f.readline().split()]
	# 	b = [int(x) for x in f.readline().split()]

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

	xor_a = [a[i] ^ a[(i+1) % N] for i in range(len(a))]
	xor_b = [b[i] ^ b[(i+1) % N] for i in range(len(b))]

	kmp = KmpSearch(xor_a + xor_a, xor_b)

	ans = kmp.full_search()
	for k in ans:
		if k == len(a):
			break
		print(str(k) + " " + str(a[0 + k] ^ b[0]))

class KmpSearch:
	def __init__(self, target, pattern):
		self.target = target
		self.pattern = pattern
		self.__table = self.__create_kmp_table()

	def full_search(self):
		if len(self.pattern) > len(self.target):
			return -1

		res = []
		i = 0
		p = 0
		while i < len(self.target):
			if self.pattern[p] == self.target[i]:
				i += 1
				p += 1

				if p == len(self.pattern):
					res.append(i-p)
					i -= 1
					p = self.__table[p-1]
			elif p == 0:
				i += 1
			else:
				p = self.__table[p]

		return res

	def __create_kmp_table(self):
		table = [0 for x in range(len(self.pattern))]

		j = 0
		for i in range(1, len(self.pattern)):
			table[i] = j
			if self.pattern[j] == self.pattern[i]:
				j += 1
			else:
				j = 0

		return table

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

int_n = int(input())
ar_int_a = list(map(int, input().split()))
ar_int_b = list()
for i in ar_int_a:
    ar_int_b.append(i)
    ar_int_b = ar_int_b[::-1]

print(" ".join(map(str, ar_int_b)))


### FIXED CODE ###

int_n = int(input())
ar_int_a = list(map(int, input().split()))
ar_int_b = [-1] * int_n


idx = (int_n // 2)
ar_int_b[idx] = ar_int_a[0]

if int_n % 2 == 0:
    # 偶数
    for i in range(1, int_n):
        if i % 2 == 0:
            idx = idx + i
        else:
            idx = idx + (-1 * i)
        ar_int_b[idx] = ar_int_a[i]
else:
    # 奇数
    for i in range(1, int_n):
        if i % 2 == 0:
            idx = idx + (-1 * i)
        else:
            idx = idx + i
        ar_int_b[idx] = ar_int_a[i]


print(" ".join(map(str, ar_int_b)))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
s = 1
if 0 in A:
    print(0)
    exit(0)
for i in A:
    s *= i
if s > 10**(18):
    print(-1)
else:
    print(s)

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int,input().split()))
s = 1
if 0 in A:
    print(0)
    exit(0)
for i in A:
    s *= i
    if s > 10**(18):
        print(-1)
        exit(0)
print(s)
### BUGGY CODE ###

n=int(input())
h=list(map(int,input().split()))
temp=0
if n==1:
  print("Yes")
else:
  for i in range(0,n-1):
    for j in range(i+1,n):
      if h[i]-1>h[j]:
        temp=1
        break
  if temp==0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))
base=0
for h in H:
    if base>h:
        print("No")
        break
    base=max(base,h-1)
else:
    print("Yes")
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
cy -= 1
cx -= 1
dy -= 1
dx -= 1

S = [list(input().strip()) for _ in range(H)]

worps = [[float('inf')]*W for _ in range(H)]
used = [[False]*W for _ in range(H)]
q = deque([[cy, cx]])

worp = 0
while q:
    v = {}
    while q:
        y, x = q.popleft()
        used[y][x] = True
        worps[y][x] = min(worps[y][x], worp)

        for h in range(-2+y, 3+y):
            for w in range(-2+x, 3+x):
                if 0 <= h and h < H and 0 <= w and w < W and S[h][w] == "." and not used[h][w]:
                    v[(h, w)] = True

        for h, w in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            ny, nx = y+h, x+w
            if 0 <= ny and ny < H and 0 <= nx and nx < W:
                if not used[ny][nx] and S[ny][nx] == ".":
                    q.append([ny, nx])

    worp += 1
    for h, w in v.keys():
        if not used[h][w]:
            q.append([h, w])
            used[h][w] = True

ans = worps[dy][dx]
if ans != float('inf'):
    print(ans)
else:
    print(-1)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
cy -= 1
cx -= 1
dy -= 1
dx -= 1
d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
S = [input() for _ in range(H)]

worps = [[float('inf')]*W for _ in range(H)]
q = deque([[cy, cx]])

worps[cy][cx] = 0
while q:
    y, x = q.popleft()
    worp = worps[y][x]

    for h, w in d:
        ny, nx = y+h, x+w
        if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == "." and worp < worps[ny][nx]:
            worps[ny][nx] = worp
            q.appendleft([ny, nx])

    worp += 1
    for h in range(-2+y, 3+y):
        for w in range(-2+x, 3+x):
            if 0 <= h < H and 0 <= w < W and S[h][w] == "." and worp < worps[h][w]:
                worps[h][w] = worp
                q.append([h, w])

ans = worps[dy][dx]
if ans != float('inf'):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

input=[input().split() for i in range(2)]
length=int(input[0][0])
list=[]
for i in range(length):
    list.append(int(input[1][i]))
ret=0
for i in range(length):
    flg=True
    num=list[i]
    for j in range(length):
        if i!=j and num%list[j]==0:
            flg=False
            break
    if flg:
        ret=ret+1
print(ret)

### FIXED CODE ###

import numpy as np
from collections import Counter

length=int(input())
list=list(map(int,input().split()))
list.sort()

max=list[-1]
dp=[0]*(max+1)
dp=np.array(dp,int)

for num in list:
    dp[num]=1

for num in list:
    if dp[num]==1:
        dp[2*num::num]=0

count=Counter(list)

for num,cnt in count.items():
    if cnt>1:
        dp[num]=0

print(dp.sum())
### BUGGY CODE ###

n, a = map(int, input().split())
X = tuple(map(int, input().split()))
X = sorted(X)

from collections import deque
ans = 0
for i in range(n):
    st = deque([[i, 1, X[i]]])
    while st:
        idx, count, s = st.pop()
        if count*a == s:
            ans += 1
        elif count*a < s:
            continue
        
        for ni in range(idx+1, n):
            st.append([ni, count+1, s+X[ni]])
print(ans)
        

### FIXED CODE ###

n, a = map(int, input().split())
X = tuple(map(int, input().split()))
dp = [[[0] * (2550) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
    # i枚目までで
    for j in range(n):
        # j枚のカードを選んで
        for s in range(n*a+1):
            # 合計がsになるパターン
            if dp[i][j][s] == 0:
                continue
            # i枚目のカードが選ばれない場合
            dp[i+1][j][s] += dp[i][j][s]
            # i枚目のカードが選ばれる場合
            dp[i+1][j+1][s+X[i]] += dp[i][j][s]
ans = 0
for k in range(1, n+1):
    ans += dp[n][k][k*a]
print(ans)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

div = [0] * (N+1)

for i in range(1, N+1):
    for j in range(i, N+1, i):
        div[j] += 1

ans = 0
for i in range(1, N+1):
    ans += i * div[i]
print(ans)    


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

ans = 0
for i in range(1, N+1):
    ans += N//i * (2*i + (N//i-1)*i) // 2
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

x = [0, a[0]]
s = [0, a[0]]
for i in range(1, n):
    x.append(x[-1] ^ a[i])
    s.append(s[-1] + a[i])

cnt = 0
for i in range(1, n + 1):
    for j in range(i, n + 1):
        xor = x[j] ^ x[i-1]
        sm = s[j] - s[i-1]
        if xor == sm:
            cnt += 1
        else:
            break

print(cnt)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

r = 0
s = 0

ans = 0
for l in range(n):
    while r < n and not (s & a[r]):
        s ^= a[r]
        r += 1
    ans += r - l
    s ^= a[l]

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

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def update(node,value):
  if node-1<0 or len(l)<=node-1:
    return 0
  vl[node-1]+=value

  if len(l[node-1])==0:
    return 0

  for x in l[node-1]:
    update(x,value)

n,q=LI()

l=[[] for _ in range(n)]
vl=[0 for _ in range(n)]

for _ in range(n-1):
  a,b=LI()
  l[a-1].append(b)

l2=[0]*(n+1)
for _ in range(q):
  a,b=LI()
  l2[a]+=b

for i,x in enumerate(l2):
  if i==0:
    continue
  update(i,x)

print(' '.join([str(x) for x in vl]))



### FIXED CODE ###

import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

nmax=2*10**5+10
graph=[[] for _ in range(nmax)]
level=[-1]*nmax

def dfs(n,s,l):
  if len(graph[s])==0:
    return
  for e in graph[s]:
    if level[e]==-1:
      level[e]=level[s]+1
    if level[e]>level[s]:
      l[e]+=l[s]
      dfs(n,e,l)

def main():
  n,q=LI()
  for _ in range(n-1):
    a,b=LI()
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
  l=[0]*n
  for _ in range(q):
    a,b=LI()
    l[a-1]+=b

  level[0]=0
  dfs(n,0,l)

  return ' '.join([str(x) for x in l])

# main()
print(main())
### BUGGY CODE ###

N =input()
A = list(map(int, input().split()))
MA =max(A)
N=int(N)
s=0
A2 = [-1] 
B =[-1]#重複
LS =[-1]
for i in range(0,N):
  k=1
  P =A[i]
  if P in A2:
    B.append(P)
    pass
  else:
    while P*k<=MA:
      LS.append(P*k)
      k+=1
    A2.append(P)
for j in range(0,N):
  if A[j] in B:
    pass
  else:
    if LS.count(A[j]) ==1:
      s=s+1

print(s)
    


### FIXED CODE ###

N = input()
A = list(map(int, input().split()))
N = int(N)
MA = max(A)
s=0
LS = [0 for i in range(0,MA)]
for i in range(0,N):
  k=1
  while A[i]*k<=MA:
    LS[A[i]*k-1] +=1
    k +=1
for j in range(0,N):
  if LS[A[j]-1]==1:
    s+=1
print(s)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc144/tasks/abc144_c C - Walk on Multiplication Table
N=int(input())
S_List = [i for i in range(1,int(N/2)+1) if N % i ==0]
S_List.append(N)
R_S_List = S_List[::-1]

Answer=(10**6)*2
for i in range(len(S_List)):
    Current_Answer = S_List[i] + R_S_List[i] - 2
    if Current_Answer < Answer:
        Answer = Current_Answer

print(Answer)


### FIXED CODE ###

# https://atcoder.jp/contests/abc144/tasks/abc144_c C - Walk on Multiplication Table
N=int(input())
S_List=[i for i in range(1,int(N**0.5)+1,1) if N % i ==0]

Answer = 10**12
for i in range(len(S_List)):
    Current_Answer = int(S_List[i] + (N/S_List[i]) -2)
    if Current_Answer < Answer:
        Answer = Current_Answer

print(Answer)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
import collections
a = collections.Counter(A)
b = []
for i in range(len(a)):
    if a.most_common()[i][1] >= 2:
        b.append(a.most_common()[i])
    else:
        break
b.sort()
if len(b) >= 1 and b[-1][1] >= 4:
    print(b[-1][0] ** 2)
elif len(b) >= 2:
    print(b[-1][0] * b[-2][0])
else:
    print(0)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
import collections
a = collections.Counter(A)
b = []
for i, j in a.items():
    if j >= 2:
        b.append([i,j])
b.sort(reverse=True)
if len(b) >= 1 and b[0][1] >= 4:
    print(b[0][0] ** 2)
elif len(b) >= 2:
    print(b[0][0] * b[1][0])
else:
    print(0)
### BUGGY CODE ###

# coding: utf-8

n,l = list(map(int,input().split()))
D = []
C = [0]

for i in range(n):
    d,c = list(map(int,input().split()))
    D.append(d)
    C.append(C[i]+c)

#時計周りに歩く場合を考える
L = []
for i in range(n):
    L.append(C[i+1]-D[i])

#反時計周りに歩く場合を考える
R = []
for i in range(n):
    R.append(C[n]-C[n-i-1]-(l-D[-i-1]))

#時計周りに歩いた後、反時計周りに歩く場合を考える
LR = []
for i in range(n-1):
    LR.append(C[i+1]-D[i]*2+max(R[:n-i-1]))

#時計周りに歩いた後、反時計周りに歩く場合を考える
RL = []
for i in range(n-1):
    RL.append(C[n]-C[n-i-1]-(l-D[-i-1])*2+max(L[:n-i-1]))
    
#即退店する場合を考える
O = [0]

print(max(L+R+LR+RL+O))

### FIXED CODE ###

# coding: utf-8

n,l = list(map(int,input().split()))
D = []
C = [0]

for i in range(n):
    d,c = list(map(int,input().split()))
    D.append(d)
    C.append(C[i]+c)

#時計周りに歩く場合を考える
L = [0]
for i in range(n):
    L.append(max(L[i],C[i+1]-D[i]))

#反時計周りに歩く場合を考える
R = [0]
for i in range(n):
    R.append(max(R[i],C[n]-C[n-i-1]-(l-D[-i-1])))

#時計周りに歩いた後、反時計周りに歩く場合を考える
LR = 0
for i in range(n-1):
    LR = max(LR, C[i+1]-D[i]*2+R[n-i-1])

# #時計周りに歩いた後、反時計周りに歩く場合を考える
RL = 0
for i in range(n-1):
    RL = max(RL, C[n]-C[n-i-1]-(l-D[-i-1])*2+L[n-i-1])

print(max(L+R+list([LR,RL])))
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
a = [[i+1, l[i]] for i in range(n)]
a.sort(key=lambda x: x[1])
ans = ""
for i in range(n):
  ans = ans + str(a[i][0]) + " "

print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
ans = [0]*n
for i in range(n):
  ans[l[i]-1]=str(i+1)

print(" ".join(ans))
### BUGGY CODE ###

import functools
_ = input()
l = list(map(int, input().split(" ")))

ans = functools.reduce(lambda x, y : x* y, l, 1)

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###


import sys
_ = input()
l = list(map(int, input().split(" ")))

if 0 in l:
    print(0)
    sys.exit()

ans = 1
for i in l:
    ans *= i
    if ans > 10 **18:
        print(-1)
        sys.exit()

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

from bisect import bisect_left

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

A = map(int, input("").split(" "))
A = list(A)
A.sort()

for i in range(M):
    B, C = map(int, input("").split(" "))

    c = -1
    for j in range(B):
        if C > A[j]:
            c = j
        else:
            break

    if c >= 0:
        A = A[c+1:]

        b = bisect_left(A, C)
        A = A[:b] + [C]*(c+1) + A[b:]

c = 0
for a in A:
    c += a

print(c)


### FIXED CODE ###

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

A = map(int, input("").split(" "))
A = list(A)
A.sort()

potentials = []
for i in range(M):
    B, C = map(int, input("").split(" "))

    potentials.append((B, C))

potentials.sort(key=lambda x: x[1], reverse=True)

c = 0
for p in potentials:
    for b in range(p[0]):
        if p[1] > A[c]:
            A[c] = p[1]
            c += 1
            if c >= len(A):
                break
        else:
            break
    if c >= len(A):
        break

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

n = int(input())
g=[]
for i in range(n):
    
    g.append(list(map(int,input().split())))

def dp(p,vw):
    if p==n:
        return 1
    k=0
    
            
    for j in range(n):
        if g[p][j]==1 and vw[j]==0:
            #print(p,j)

            vw[j]=1
            k+=dp(p+1,vw)
            #print(vw)

            vw[j]=0
                    
    return k

viw=[0]*n
print(dp(0,viw))
            
    
    

### FIXED CODE ###

n = int(input())
g=[]
for i in range(n):
    
    g.append(list(map(int,input().split())))
mod=10**9+7
dp=[0]*(2**n)
dp[0]=1
for i in range(1,2**n):
    e=bin(i)[2:]
    y=e.count('1')
    for j in range(len(e)):
        if e[-j-1]=='1':
            if g[y-1][j]:
                    dp[i]+=dp[i-(2**j)]
                    dp[i]%=mod


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

def bogosort(l):
  import random
  while 1:
    random.shuffle(l)
    for i in range(1,len(l)):
      if l[i]<l[i-1]:
        break
    else:
      return l
i=lambda:list(map(int,input().split()))
n,m,x,y=i()
if bogosort(i()+[x])[-1]<bogosort(i()+[y])[0]:
    print('No War')
else:
    print('War')

### FIXED CODE ###

x,y=input().split()[2:];print('No '*(max(map(int,input().split()+[x]))<min(map(int,input().split()+[y])))+'War')
### BUGGY CODE ###

n = int(input())
get = []
count = 0
for i in range(n):
    prize = input()
    if prize in get:
        continue
    get.append(prize)
    count += 1
print(count)

### FIXED CODE ###

n = int(input())
get = []
for i in range(n):
    prize = input()
    get.append(prize)
get = list(set(get))
print(len(get))
### BUGGY CODE ###

import math
def main():
	H,N = map(int,input().split())
	A,B = [],[]
	for _ in range(N):
		a,b = map(int,input().split())
		A.append(a)
		B.append(b)
	
	dp = [[0 for _ in range(H+1)] for _ in range(N)]
	
	for i in range(1,H+1):
		dp[0][i] = math.ceil(i/A[0])*B[0]

	for i in range(1,N):
		for j in range(1,H+1):
			if j<=A[i]:
				dp[i][j] = min(dp[i-1][j],B[i])
			else:
				dp[i][j] = min([dp[i-1][j],dp[i-1][j-A[i]]+B[i],
										   dp[i][j-A[i]]+B[i]])

	print(dp[N-1][H])
if __name__ == '__main__':
	main()

### FIXED CODE ###

import math
import sys
input = sys.stdin.readline
def main():
	H,N = map(int,input().split())
	A,B = [],[]
	ap = A.append
	bp = B.append
	for _ in range(N):
		a,b = map(int,input().split())
		ap(a)
		bp(b)
	
	dp = [[0 for _ in range(H+1)] for _ in range(N)]
	
	for i in range(1,H+1):
		dp[0][i] = math.ceil(i/A[0])*B[0]

	for i in range(1,N):
		for j in range(1,H+1):
			if j<=A[i]:
				dp[i][j] = min(dp[i-1][j],B[i])
			else:
				dp[i][j] = min(dp[i-1][j],dp[i][j-A[i]]+B[i])

	print(dp[N-1][H])
if __name__ == '__main__':
	main()
### BUGGY CODE ###

import collections
n, k = map(int, raw_input().split())
num = map(int, raw_input().split())
n = int()
num = collections.Counter(num)
while True:
    if len(num) <= k:
        print n
        break
    t, v = sorted(num.items(), key=lambda x:x[1])[0]
    del num[t]
    n += v

### FIXED CODE ###

import collections
n, k = map(int, raw_input().split())
num = map(int, raw_input().split())
n = int()
num = collections.Counter(num)
for t, v in sorted(num.items(), key=lambda x:x[1])[0:-k]:
    n += v
print n
### BUGGY CODE ###

n = int(input())
lst = []
num = [1]*n
ans = 0
for i in range(n):
    s = sorted(input())
    s = "".join(s)
    if s not in lst:
        lst.append(s)
    else:
        pos = lst.index(s)
        num[pos] += 1
for j in num:
    ans += (j * (j-1)) / 2
print(int(ans))

### FIXED CODE ###

from collections import defaultdict
N = int(input())
dict = defaultdict(int)
ans = 0
for i in range(N):
    s = ''.join(sorted(input()))
    ans += dict[s]
    dict[s] += 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
s = 0
MOD = 10**9 + 7
rea = [num%MOD for num in a]
while len(rea) != 1:
    firstnum = rea.pop()
    for i in rea:
        b = firstnum * i
        s += b
s %= MOD
print(s)

### FIXED CODE ###

n = int(input())
mod = 10**9 + 7
a = [int(x)%mod for x in input().split()]
allsum = sum(a)
s = 0
for i in range(n):
    allsum = allsum -a[i]
    s += a[i]*allsum
print(s%mod)