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

def main():
    a,b,q = map(int,input().split())
    A = []
    B = []
    
    for _ in range(a):
        A.append(int(input()))
    
    for _ in range(b):
        B.append(int(input()))
    
    def search(A,x):
        left =0
        right = len(A)-1
        
        if x<A[0]:
            return (float('inf'),abs(x - A[left]))
        if x >A[-1]:
            return (abs(x - A[right]),float('inf'))
        
        while left != right-1:
            center = (left+right)//2
            
            if A[center] > x:
                right = center
            else:
                left = center
        
        return (abs(x - A[left]),abs(x - A[right]))
    
    
    def dist(A,x,lr):
        if lr == float('inf'):
            return float('inf')
        return abs(x - A[lr])
    
    for _ in range(q):
        x = int(input())
        sl,sr = search(A,x)
        tl,tr = search(B,x)
        print(min(min(sl,sr)+min(tl,tr)+min(min(sl,sr),min(tl,tr)),max(sl,tl),max(sr,tr)))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline


def main():
    a,b,q = map(int,readline().split())
    A = [int(readline()) for i in range(a)]
    B = [int(readline()) for i in range(b)]
    def search(A,x):
        left =0
        right = len(A)-1
        
        if x<A[0]:
            return (float('inf'),abs(x - A[left]))
        if x >A[-1]:
            return (abs(x - A[right]),float('inf'))
        
        while left != right-1:
            center = (left+right)//2
            
            if A[center] > x:
                right = center
            else:
                left = center
        
        return (abs(x - A[left]),abs(x - A[right]))
    
    
    def dist(A,x,lr):
        if lr == float('inf'):
            return float('inf')
        return abs(x - A[lr])
    
    for _ in range(q):
        x = int(readline())
        sl,sr = search(A,x)
        tl,tr = search(B,x)
        print(min(min(sl,sr)+min(tl,tr)+min(min(sl,sr),min(tl,tr)),max(sl,tl),max(sr,tr)))

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

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
mod = 10**9 + 7

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

s = 0
for i in range(n-1):
    for j in range(i+1,n):
        s += a[i]^a[j]
        s %= mod
print(s)

### FIXED CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
mod = 10**9 + 7

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

ans = 0
for i in range(n):
    a[i] = bin(a[i])[2:].zfill(60)

for i in range(60):
    count = 0
    for j in range(n):
        count += 1 if a[j][i] == '1' else 0

    ans += (pow(2, 59-i, mod) * count * (n-count)) % mod

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

from numba import jit
@jit
def keisan(a):
    a.sort(reverse = True)
    ans = 0
    for i in range(n):
        if a.count(a[i]) >= 4:
            ans = a[i]*a[i]
            break
        elif a.count(a[i]) >=2:
            for j in range(i+a.count(a[i]),n):
                if a.count(a[j]) >=2:
                    ans = a[i]*a[j]
                    break
            break
    print(ans)

n = int(input())
in_ = [int(i) for i in input().split()]
keisan(in_)

### FIXED CODE ###

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

a.sort(reverse = True)
ans = 0
b = a.copy()
b = list(set(b))
b.sort(reverse = True)
c = [0]*len(b)
j = 0
c[j] = 1
for i in range(1,n):
    if a[i-1] == a[i]:
        c[j] +=1
    else:
        j+=1
        c[j] +=1
for i in range(len(b)):
    if c[i] >= 4:    
        
        ans = b[i]*b[i]
        break
    elif c[i] >= 2:
        for j in range(i+1,len(b)):
            if c[j] >= 2:
                ans = b[i]*b[j]
                break
        break
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
x = 0
a = 0
for i in range (0,N-K+1):
  x = sum(p[i:i+K])
  if x == max(a,x):
    a = x
    ans = i
    
E = 0
for j in range (0,K):
  E = E + (1 + p[ans+j]) / 2
print(E)


### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
E = sum(p[0:K])
a = E
for i in range (0,N-K):
  E = E - p[i] + p[i+K]
  if E == max(a,E):
    a = E
    
print((a+K)/2)
### BUGGY CODE ###

from math import*
n,k=map(int,input().split())
*a,=map(int,input().split())
*f,=map(int,input().split())
ref=sorted([(x*y,y) for x,y in zip(sorted(a),sorted(f)[::-1])])[::-1]
l=-1
r=10**12
while r-l>1:
	m=(l+r)//2
	rest=k
	flg=1
	for z,y in ref:
		if m>=z:
			break
		if rest>=ceil((z-m)/y):
			rest-=ceil((z-m)/y)
		else:
			flg=0
			break
	if flg:
		r=m
	else:
		l=m
print(r)

### FIXED CODE ###

def main():
	n, k = map(int, input().split())
	*a, = map(int, input().split())
	*f, = map(int, input().split())
	a.sort()
	f.sort(reverse=1)
	prod = [(y, x * y) for x, y in zip(a, f)]
	l = -1
	r = 10 ** 12
	while r - l > 1:
		m = (l + r) // 2
		s = sum(max(0, 0 - (m - p) // y) for y, p in prod)
		if s <= k:
			r = m
		else:
			l = m
	print(r)


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

i = int(input())
S = [input() for _ in range(i)]
d = {}
max = 1
for s in list(set(S)):
  if S.count(s) >= max:
    max = S.count(s) 
    d[s] = S.count(s)
keys = sorted([k for k, v in d.items() if v == max])
for key in keys:
  print(key)

### FIXED CODE ###

import collections
i = int(input())
S = collections.Counter([input() for _ in range(i)])
max_v = max(S.values())
[print(s) for s in sorted([s for s in S if S[s] == max_v])]
### BUGGY CODE ###

N, M = map(int, input().split())
AB = []

for i in range(N):
  ab = list(map(int, input().split()))
  if ab[0] <= M:
    AB.append(ab)

AB.sort(reverse = True, key = lambda x:x[1])
ans = 0
for i in range(1, M + 1):
  for j in range(len(AB)):
    if AB[j][0] <= i:
      ans += AB.pop(j)[1]
      break

print(ans)

### FIXED CODE ###

from heapq import heappush, heappop

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

for i in range(N):
  ab = list(map(int, input().split()))
  #Ai > M の仕事はいらない
  if ab[0] <= M:
    jobs[ab[0] - 1].append(ab[1])

#最終日はAi=1の仕事のみ選べる。その前の日はAi<=2, ...
#終わりから考えればよさそう
hq = []
ans = 0
for i in range(M):
  for b in jobs[i]:
    heappush(hq, -1 * b)
  if len(hq) > 0:
    m = -1 * heappop(hq)
    ans += m

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

import sys

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

if numbers == [] or 1 not in numbers:
    print(-1)
    sys.exit(0)

index = 0
value = 1
breaks = 0
while True:
    while numbers[index] != value:
        if index >= len(numbers):
            print(-1)
            sys.exit(0)
        numbers.pop(index)
        breaks += 1
    index += 1
    value += 1
    if index >= len(numbers):
        print(breaks)
        sys.exit(0)

### FIXED CODE ###

import sys

n = int(input())
numbers = list(map(int, sys.stdin.readline().split()))

if 1 not in numbers:
    print(-1)
    sys.exit(0)

breaks = 0
current = 1
for i in range(n):
    if numbers[i] == current:
        current += 1
    else:
        breaks += 1
print(breaks)
### BUGGY CODE ###

import sys

n, m = map(int, sys.stdin.readline().split())
A = [int(sys.stdin.readline()) for _ in range(m)]

dp = [0 for i in range(n+1)]
dp[0] =1
#print(dp)

for i in range(1, n+1):
    if i in A:
        continue
    if i-2>=0:
        dp[i] = dp[i-1] + dp[i-2]
    else:
        dp[i] = dp[i-1]


print(dp[-1]%1000000007)


### FIXED CODE ###

import sys

n, m = map(int, sys.stdin.readline().split())
A = [int(sys.stdin.readline()) for _ in range(m)]
bloken = [0 for i in range(n+1)]
for a in A:
    bloken[a]=1
    

dp = [0 for i in range(n+1)]
dp[0] =1
#print(dp)

for i in range(1, n+1):
    if bloken[i]==1:
        continue
    if i-2>=0:
        dp[i] = dp[i-1] + dp[i-2]
    else:
        dp[i] = dp[i-1]


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

N = int(input())
import numpy as np
L = np.array(input().split(),np.int16)
L.sort()
L = L[::-1]
#L.sort(reverse=True)
counter = 0

for index1,c in enumerate(L):
    index2 = index1+1
    if index2>N-1:
      break
    b = L[index2]
    while b>=c/2:
        
        index3 = index2+1
        if index3>N-1:
            break
        a = L[index3]
        
        while a+b>c:
            counter += 1
            index3+=1
            if index3>N-1:
                break
            a = L[index3]

        index2+=1
        if index2>N-1:
            break
        b = L[index2]


print(counter)

### FIXED CODE ###

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

L.sort(reverse=True)
counter = 0
import bisect

for index1,c in enumerate(L):
    for index2,b in enumerate(L[index1+1:],start=index1+1):
        left = 0 ; right = N
        oppai = c-b
        while left+1<right:
            mid = (left+right)//2
            if L[mid]>oppai:
                left = mid
            else :
                right=mid
        
        index3 = left
        
        if index3>index2:

            counter += index3-index2
print(counter)
### BUGGY CODE ###

N,K,Q=map(int,input().split())
c=[K-Q]*N

for i in range(Q):
  A=int(input())-1
  for r in range(N):
    if r==A:
      c[r]+=1
    
for k in range(N):
  if c[k]>0:
    c[k]='Yes'
  else:
    c[k]='No'
    
for j in range(N):
  print(c[j])
    
    

### FIXED CODE ###

N,K,Q=map(int,input().split())
c=[K-Q]*N

for i in range(Q):
  A=int(input())-1
  c[A]+=1
    
for k in range(N):
  if c[k]>0:
    c[k]='Yes'
  else:
    c[k]='No'
    
for j in range(N):
  print(c[j])
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
import copy

H, W, K = map(int, input().split())
if K > W:
    exit(print(0))

# 現在の盤面を生成する
c = [[] for _ in range(W)]
for i in range(H):
    S = input()
    for j in range(W):
        c[j].append(int(S[j]))

for j in range(W):
    c[j] = c[j][::-1]
# print(c)

# 連鎖消滅後の得点を計算する
def cal_score(c,score,loop):
    # 消滅
    nextc = []
    for j in range(W):
        num0 = c[j].count(0)
        tmp = [*filter(lambda x: x>0,c[j])]
        nextc.append(tmp+[0]*num0)

    # print(nextc)

    # 連鎖
    res = 0# 追加得点
    for i in range(H):
        j = 0
        while j < W:
            seq = 1
            while j<W-1 and nextc[j][i] == nextc[j+1][i] > 0:
                seq += 1
                j += 1
            if seq >= K:
                res += seq * nextc[j][i]
                for k in range(j-seq+1,j+1):
                    nextc[k][i] = 0
            j += 1
    # print(nextc,res)
    if res == 0:
        return score
    else:
        return cal_score(nextc,score+res*pow(2,loop),loop+1)
    

ans = 0
for p in range(H):
    for q in range(W):
        # p = 0
        # q = 2
        cc = copy.deepcopy(c)
        cc[q][p] = 0
        # print(p,q)
        z = cal_score(cc,0,0)
        # print(z)
        ans = max(ans, z)
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import copy

H, W, K = map(int, input().split())
if K > W:
    exit(print(0))

# 現在の盤面を生成する
c = [[] for _ in range(W)]
for i in range(H):
    S = input()
    for j in range(W):
        c[j].append(int(S[j]))

for j in range(W):
    c[j] = c[j][::-1]

# 連鎖消滅後の得点を計算する
def cal_score(c,score,loop):
    # 消滅
    nextc = []
    for j in range(W):
        num0 = c[j].count(0)
        tmp = [*filter(lambda x: x>0,c[j])]
        nextc.append(tmp+[0]*num0)

    # 連鎖
    res = 0# 追加得点
    for i in range(H):
        j = 0
        while j < W:
            seq = 1
            while j<W-1 and nextc[j][i] == nextc[j+1][i] > 0:
                seq += 1
                j += 1
            if seq >= K:
                res += seq * nextc[j][i]
                for k in range(j-seq+1,j+1):
                    nextc[k][i] = 0
            j += 1
    if res == 0:
        return score
    else:
        return cal_score(nextc,score+res*pow(2,loop),loop+1)
    

ans = 0
for p in range(H):
    for q in range(W):
        cc = copy.deepcopy(c)
        cc[q][p] = 0
        z = cal_score(cc,0,0)
        ans = max(ans, z)
print(ans)
### BUGGY CODE ###

MOD = 10**9 + 7
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [0] * (N+1)
dp[0] = 1
for i in range(1, N+1):
    if i in A:
        dp[i] = 0
        continue
    dp[i] = dp[i - 1]
    if i > 1:
        dp[i] = dp[i - 1] + dp[i - 2]
# print(dp)
print(dp[N] % MOD)

### FIXED CODE ###

MOD = 10 ** 9 + 7
n, m = map(int, input().split())
broken = [False] * (n + 1)
for i in range(m):
    a = int(input())
    broken[a] = True
dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    dp[i] %= MOD
    if broken[i]:
        dp[i] = 0
    if i + 1 <= n:
        dp[i+1] += dp[i]
    if i + 2 <= n:
        dp[i+2] += dp[i]
print(dp[n] % MOD)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Jul  5 21:49:24 2020

@author: NEC-PCuser
"""

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

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

A.sort()

minus_list = []
plus_list = []
for i in range(len(A)):
    if (A[i] <= 0):
        minus_list.append(A[i])
    else:
        plus_list.append(A[i])

ans = 1
mod = 10 ** 9 + 7   
if N == K:
    for i in A:
        ans = (ans * i) % mod
elif 0 == len(plus_list) and  K % 2 == 1:
    minus_list.sort(reverse=True)
    for i in range(K):
        ans = (ans * minus_list[i]) % mod
else:
    minus_list.sort()
    plus_list.sort(reverse=True)
    if K % 2 == 1:
        ans = plus_list.pop(0)
    for i in range(K // 2):
        if (len(plus_list) < 2):
            ans = (minus_list[0] * ans) % mod
            ans = (minus_list[1] * ans) % mod
            minus_list = minus_list[2:]
        elif (len(minus_list) < 2):
            ans = (plus_list[0] * ans) % mod
            ans = (plus_list[1] * ans) % mod
            plus_list = plus_list[2:]
        elif (plus_list[0] * plus_list[1] > minus_list[0] * minus_list[1]):
            ans = (plus_list[0] * ans) % mod
            ans = (plus_list[1] * ans) % mod
            plus_list = plus_list[2:]
        else:
            ans = (minus_list[0] * ans) % mod
            ans = (minus_list[1] * ans) % mod
            minus_list = minus_list[2:]
print(ans)
        

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Jul  5 21:49:24 2020

@author: NEC-PCuser
"""

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

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

A.sort()

minus_list = []
plus_list = []
for i in range(len(A)):
    if (A[i] <= 0):
        minus_list.append(A[i])
    else:
        plus_list.append(A[i])

ans = 1
mod = 10 ** 9 + 7   
if N == K:
    for i in A:
        ans = (ans * i) % mod
elif 0 == len(plus_list) and  K % 2 == 1:
    minus_list.sort(reverse=True)
    for i in range(K):
        ans = (ans * minus_list[i]) % mod
else:
    minus_list.sort(reverse=True)
    plus_list.sort()
    if K % 2 == 1:
        ans = plus_list.pop()
    for i in range(K // 2):
        if (len(plus_list) < 2):
            ans = (minus_list.pop() * ans) % mod
            ans = (minus_list.pop() * ans) % mod
        elif (len(minus_list) < 2):
            ans = (plus_list.pop() * ans) % mod
            ans = (plus_list.pop() * ans) % mod
        elif (plus_list[len(plus_list) - 1] * plus_list[len(plus_list) - 2] > minus_list[len(minus_list) - 1] * minus_list[len(minus_list) - 2]):
            ans = (plus_list.pop()* ans) % mod
            ans = (plus_list.pop() * ans) % mod
        else:
            ans = (minus_list.pop() * ans) % mod
            ans = (minus_list.pop()* ans) % mod
print(ans)
### BUGGY CODE ###

import numpy as np
a = list(input())
b = np.array([1 for i in range(len(a))])
#print(a)
keep1 = np.array([0 for i in range(len(a))])
keep2 = np.array([0 for i in range(len(a))])
hako = np.array([0 for i in range(len(a))])
for j in range(1000000000):
    hako = np.array([0 for i in range(len(a))])
    #print(b,keep1, keep2-b,(keep2 - b).any())
    if j % 2 == 0 and not (keep2 - b).any():
        print(' '.join(map(str,b)))
        break
    for i in range(len(a)):
        if a[i] == 'L' and b[i] >= 1:
            hako[i - 1] += b[i]

        elif a[i] == 'R' and b[i] >= 1:
            hako[i + 1] += b[i]
    
    keep2 = np.copy(keep1)
    keep1 = np.copy(b)
    b = np.copy(hako)

### FIXED CODE ###


a = list(input().split('LR'))
for i in range(len(a) - 1):
    a[i] += 'L'
    a[i + 1] = 'R' + a[i + 1]

#print(a)

b = []
c = 0
d = []
for j in range(len(a)):
    b = [0 for i in range(len(a[j]))]
    c = a[j].find('L')
    #print(c)
    if c % 2 == 0:
        b[c - 1] = len(a[j]) // 2
        b[c] = len(a[j]) - len(a[j]) // 2
    else:
        b[c] = len(a[j]) // 2
        b[c - 1] = len(a[j]) - len(a[j]) // 2

    d.extend(b)

print(' '.join(map(str,d)))
### BUGGY CODE ###

#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[[inf for _ in range(4)] for _ in range(w)] for _ in range(h)]
seen[x1][y1] = [0,0,0,0]

dire = [[1,0],[-1,0],[0,1],[0,-1]]
def add(x,y,di,s):
  dx,dy = dire[di]
  if 0 <= x+dx < h and 0 <= y+dy < w:
    if raw[x+dx][y+dy] == '.' and seen[x+dx][y+dy][di] > s:
      now.append([s,x+dx,y+dy,di])
      seen[x+dx][y+dy][di] = s
def turn(x,y,di,s):
  dx,dy = dire[di]
  if seen[x][y][di] > s:
    nex.append([s,x,y,di])
    seen[x][y][di] = s

nex = [[0,x1,y1,d] for d in range(4)]
while nex:
  now = nex[:]
  nex = []
  for i in range(k):
    last = now[:]
    now = []
    for sxydi in last:
      s,x,y,di = sxydi
      if seen[x][y][di] < s:
        continue
      if x == x2 and y == y2:
        print(s)
        exit()
      add(x,y,di,s+1-int(bool(i)))
      for d in range(4):
        if di != d:
          turn(x,y,d,s)
  for xx in now:
    nex.append(xx)
print(-1)

### FIXED CODE ###

#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0,x1,y1]]

while now:
  s,x,y = pop(now)
  if x == x2 and y == y2:
    print(s)
    exit()
  for i in range(1,k+1):
    if x-i == -1 or raw[x-i][y] == '@' or seen[x-i][y] < s+1:
      break
    if seen[x-i][y] != s+1:
      seen[x-i][y] = s+1
      push(now,[s+1,x-i,y])
  for i in range(1,k+1):
    if y-i == -1 or raw[x][y-i] == '@' or seen[x][y-i] < s+1:
      break
    if seen[x][y-i] != s+1:
      seen[x][y-i] = s+1
      push(now,[s+1,x,y-i])
  for i in range(1,k+1):
    if x+i == h or raw[x+i][y] == '@' or seen[x+i][y] < s+1:
      break
    if seen[x+i][y] != s+1:
      seen[x+i][y] = s+1
      push(now,[s+1,x+i,y])
  for i in range(1,k+1):
    if y+i == w or raw[x][y+i] == '@' or seen[x][y+i] < s+1:
      break
    if seen[x][y+i] != s+1:
      seen[x][y+i] = s+1
      push(now,[s+1,x,y+i])
print(-1)
### BUGGY CODE ###

import collections
import numpy as np

h, w = list(map(int, input().split()))
smat = [input() for _ in range(h)]

def bfs(x0, y0):
    visited = np.zeros((h, w))
    deq = collections.deque()
    deq.append((x0, y0, -1))

    mx = 0
    while len(deq) > 0:
        x, y, d = deq.popleft()
        nd = d + 1
        visited[x][y] = 1
        mx = max(mx, nd)

        for dx, dy in [(-1, 0), (0, -1), (+1, 0), (0, +1)]:
            nx = x + dx
            ny = y + dy
            if not (0 <= nx < h) or not (0 <= ny < w):
                # bound check
                continue
            if smat[nx][ny] == '#':
                # cell attr check
                continue
            if visited[nx][ny] == 1:
                # already visited
                continue
            v = (nx, ny, nd)
            deq.append(v)
    
    return mx

mxall = 0
for x0 in range(h):
    for y0 in range(w):
        if smat[x0][y0] == '.':
            mx = bfs(x0, y0)
            mxall = max(mxall, mx)
print(mxall)


### FIXED CODE ###

import collections

h, w = list(map(int, input().split()))
smat = [input() for _ in range(h)]

def bfs(x0, y0):
    visited = [[0 for _ in range(w)] for _ in range(h)]
    deq = collections.deque()
    deq.append((x0, y0, -1))

    mx = 0
    while len(deq) > 0:
        x, y, d = deq.popleft()
        nd = d + 1
        visited[x][y] = 1
        mx = max(mx, nd)

        for dx, dy in [(-1, 0), (0, -1), (+1, 0), (0, +1)]:
            nx = x + dx
            ny = y + dy
            if not (0 <= nx < h) or not (0 <= ny < w):
                # bound check
                continue
            if smat[nx][ny] == '#':
                # cell attr check
                continue
            if visited[nx][ny] == 1:
                # already visited
                continue
            v = (nx, ny, nd)
            deq.append(v)
    
    return mx

if all(all(col == '.' for col in row) for row in smat):
    print((w - 1) + (h - 1))
else:
    mxall = 0
    for x0 in range(h):
        for y0 in range(w):
            if smat[x0][y0] == '.':
                mx = bfs(x0, y0)
                mxall = max(mxall, mx)
    print(mxall)
### BUGGY CODE ###

import numpy as np


N,M=map(int,input().split())
A=np.array(list(map(int,input().split())))
# A=np.array(list(map(int,input().split())),dtype=np.int64)
A=np.sort(A)

for i in range(M):
    B,C=map(int,input().split())
    for j in range (B):
        count=np.count_nonzero(A<C)
        if count>0:
            m=min(B,count)
            A[:m]=C
        else:
            continue
    
    A=np.sort(A)

print(np.sum(A))

### FIXED CODE ###

import numpy as np


N,M=map(int,input().split())
# A=np.array(list(map(int,input().split())))
A=np.array(list(map(int,input().split())),dtype=np.int32)
A=np.sort(A)

EXC=[]

for i in range(M):
    exc=list(map(int,input().split()))
    EXC.append(exc)
excArry=np.array(EXC,dtype=np.int32)

col_num=1
Arr=excArry[np.argsort(excArry[:,col_num])[::-1]]
# print(A)
# print(Arr)

point=0


for j in range (M):
    change_Num=Arr[j][1]
    count=np.count_nonzero(A<change_Num)
    if count > 0:
        m=min(count,Arr[j][0])
        A[point:point+m]=change_Num
        point+=m
        # A=np.sort(A)
    else:
        break

print(np.sum(A))
    
#     for j in range (B):
#         count=np.count_nonzero(A<C)
#         if count>0:
#             m=min(B,count)
#             A[:m]=C
#         else:
#             continue
    
#     A=np.sort(A)

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

#https://atcoder.jp/contests/abc110/tasks/abc110_c

s = list(str(input()))
t = list(str(input()))
u = []
v = []
flag = 'Yes'
cnt = 0
for i in range(len(s)):
    for j in range(i, len(s)):
        if s[i] == s[j]:
            cnt += 1
    u.append(cnt)
    cnt = 0

cnt = 0
for i in range(len(t)):
    for j in range(i, len(t)):
        if t[i] == t[j]:
            cnt += 1
    v.append(cnt)
    cnt = 0
    if u[len(v) - 1] != v[len(v) - 1]:
        flag = 'No'
        break


print(flag)

### FIXED CODE ###

import sys
s = str(input())
t = str(input())
l = len(s)
tmp = [[], []]
for i in range(l):
    if (not s[i] in tmp[0]) and (not t[i] in tmp[1]):
        tmp[0].append(s[i])
        tmp[1].append(t[i])
    else:
        if s[i] in tmp[0]:
            tmp2 = 0
            for j in range(len(tmp[0])):
                if s[i] == tmp[0][j]:
                    tmp2 = j
            if t[i] != tmp[1][tmp2]:
                print('No')
                sys.exit()
        else:
            print('No')
            sys.exit()
print('Yes')