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

import sys

N=int(sys.stdin.readline())
A=list(map(int,sys.stdin.readline().split()))
B=list(map(int,sys.stdin.readline().split()))

ANS=""
for i in range(1,30):
    k=2**i
    XA=sorted([A[t]%k for t in range(N)],reverse=True)
    XB=sorted([B[t]%k for t in range(N)])
    XB.append(k*2)

    b0=0
    b1=0
    b2=0
    count=0

    for xa in XA:
        for j in range(b0,N+1):
            if k//2<=xa+XB[j]:
                b0=j
                break
        
        for j in range(b1,N+1):
            if xa+XB[j]>=k:
                b1=j
                break

        for j in range(b2,N+1):
            if k*3//2<=xa+XB[j]:
                b2=j
                break

        count+=(b1-b0+N-b2)%2

    ANS+=str(count%2)

print(int(ANS[::-1],2))

### FIXED CODE ###

import sys

N=int(sys.stdin.readline())
A=list(map(int,sys.stdin.readline().split()))
B=list(map(int,sys.stdin.readline().split()))

ANS=""
for i in range(1,30):
    k=2**i
    XA=sorted([a%k for a in A],reverse=True)
    XB=sorted([b%k for b in B])
    XB.append(k*2)

    b0=0
    b1=0
    b2=0
    count=0

    for xa in XA:
        for j in range(b0,N+1):
            if k//2<=xa+XB[j]:
                b0=j
                break

        if b1<b0:
            b1=b0

        
        for j in range(b1,N+1):
            if xa+XB[j]>=k:
                b1=j
                break

        if b2<b1:
            b2=b1

        for j in range(b2,N+1):
            if k*3//2<=xa+XB[j]:
                b2=j
                break

        count+=(b1-b0+N-b2)

    ANS+=str(count%2)

print(int(ANS[::-1],2))
### BUGGY CODE ###

N,Q=map(int,input().split())
S=list(input())
count_list=[]

flag=0
for num,i in enumerate(S):
    if i=='A':
        flag=1
    elif i=='C' and flag==1:
        count_list.append(num)
        flag=0
    else:
        flag=0

for i in range(Q):
    l,r=map(int,input().split())
    l,r=l-1,r-1 #リストのインデックスとの整合
    n=sum(l+1<=x<= r for x in count_list)
    print(max(n,0))

### 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 ###

import numpy as np

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

ans=1

for i in a:
    ans*=i


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


### FIXED CODE ###

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

ans=1

if 0 in a:
    print(0)
    exit()

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


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

from itertools import accumulate, product
def solve():
    N,W = map(int,input().split())
    value = [list() for _ in range(4)]
    w1 = None
    for i in range(N):
        w,v = map(int,input().split())
        if i == 0:
            w1 = w
        value[w-w1].append(v)
    
    acc = []
    for i in range(4):
        value[i].sort(reverse=True)
        acc.append(list(accumulate(value[i])))
    
    max_len = max(list(map(lambda x:len(x),acc)))
    comb = list(product(list(range(max_len+1)),repeat=4))
    ans = 0
    for c in comb:
        if isOver(c, acc):
            continue
        sum_w = c[0] * w1 + c[1] * (w1+1) + c[2] * (w1+2) + c[3] * (w1+3)
        if sum_w > W:
            continue
        res = 0
        for i in range(4):
            if c[i] == 0:
                continue
            res += acc[i][c[i]-1]
        
        ans = max(ans,res)
    
    print(ans)

def isOver(c, acc):
    res = False
    for i in range(4):
        if len(acc[i]) < c[i]:
            res = True
    
    return res
if __name__ == '__main__':
    solve()

### FIXED CODE ###

from itertools import accumulate, product
def solve():
    N,W = map(int,input().split())
    value = [list() for _ in range(4)]
    w1 = None
    for i in range(N):
        w,v = map(int,input().split())
        if i == 0:
            w1 = w
        value[w-w1].append(v)
    
    acc = []
    for i in range(4):
        value[i].sort(reverse=True)
        acc.append(list(accumulate(value[i])))
    
    comb = []
    for i_0 in range(len(acc[0]) + 1):
        for i_1 in range(len(acc[1]) + 1):
            for i_2 in range(len(acc[2]) + 1):
                for i_3 in range(len(acc[3]) + 1):
                    comb.append((i_0,i_1,i_2,i_3))
    ans = 0
    for c in comb:
        if isOver(c, acc):
            continue
        sum_w = c[0] * w1 + c[1] * (w1+1) + c[2] * (w1+2) + c[3] * (w1+3)
        if sum_w > W:
            continue
        res = 0
        for i in range(4):
            if c[i] == 0:
                continue
            res += acc[i][c[i]-1]
        
        ans = max(ans,res)
    
    print(ans)

def isOver(c, acc):
    res = False
    for i in range(4):
        if len(acc[i]) < c[i]:
            res = True
    
    return res
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

# ABC097 C - K-th Substring
s = input()
k = int(input())

n = len(s)
d = set()
l = []

for i in range(n):
    for j in range(n-i):
        d.add(s[j:j+i+1])
l = list(d)
l.sort()

print(l[k-1])

### FIXED CODE ###

# ABC097 C - K-th Substring
s = input()
k = int(input())

n = len(s)
d = set()
l = []

for i in range(k):
    for j in range(n-i):
        d.add(s[j:j+i+1])
l = list(d)
l.sort()

print(l[k-1])
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
S = S[0:len(S)-1]
ac = [1 if S[_:_+2] == 'AC' else 0 for _ in range(N-1)] + [0]
for q in range(Q):
    r,l = map(int,input().split())
    print(sum(ac[r-1:l-1]))

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
ansers = [0] * (N+1)
for i in range(N):
    ansers[i+1] = ansers[i] + (1 if S[i:i+2] == 'AC' else 0)
for q in range(Q):
    l,r = map(int,input().split())
    print(ansers[r-1] - ansers[l-1])
### BUGGY CODE ###

h,w,k=map(int,input().split())

y1,x1,y2,x2=map(int,input().split())

maze=[list(input()) for _ in range(h)]

from collections import deque
stack=deque([(y1-1,x1-1)])

before=[[0]*w for _ in range(h)]
dic={}
dic[0]=0
dic[(0,1)]=(0,-1)
dic[(0,-1)]=(0,1)
dic[(1,0)]=(-1,0)
dic[(-1,0)]=(1,0)

maze[y1-1][x1-1]=0
#pri(maze)
while len(stack)>0:
    #print(stack)
    (y,x)=stack.popleft()
    if (y,x)==(y2-1,x2-1):
        print(maze[y][x])
        exit()

    #縦横左右
    for (my,mx) in ((1,0),(0,1),(-1,0),(0,-1)):
        #print(my,mx)
        flag=0
        if (my,mx)!=dic[before[y][x]]:
            for kk in range(1,k+1):
                ny=y+my*kk
                nx=x+mx*kk
                if 0<=ny<h and 0<=nx<w:
                    if maze[ny][nx]!="@":
                        if maze[ny][nx]==".":
                            maze[ny][nx]=maze[y][x]+1
                            stack.append((ny,nx))
                            before[ny][nx]=((my,mx))
                    else:
                        break
                else:
                    break
    #pri(maze)
print(-1)


### FIXED CODE ###

def main():
    import sys
    from collections import deque
    input=sys.stdin.readline

    h,w,k=map(int,input().split())
    sy,sx,gy,gx=map(int,input().split())

    #maze=[]
    #for _ in range(h):
    #    maze.append(tuple(input()))

    maze=[tuple(input()) for _ in range(h)]

    sy-=1
    sx-=1
    gy-=1
    gx-=1

    #maze[sy][sx]="S"

    dis=[[-1]*w for _ in range(h)]



    dis[sy][sx]=0



    d = deque([(sx,sy)])
    while len(d)>0:
        (x,y)=d.popleft()
        if x==gx and y==gy:
            print(dis[gy][gx])
            #maze[gy][gx]="G"

            #pri(dis)
            #pri(maze)

            exit()

        for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
            #print(mx,my,d)
            for j in range(1,k+1):
                nx=x+mx*j
                ny=y+my*j
                #print(y,x,">>",ny,nx)
                if 0<=nx<w and 0<=ny<h:
                    if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                        if dis[ny][nx]==-1:
                            d.append((nx,ny))
                        dis[ny][nx]=dis[y][x]+1
                        
                        #pri(dis)
                    else:
                        break
                else:
                    break

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

import sys
input = sys.stdin.readline
N,W= map(int,input().split())
ans=[0 for e in range(W+1)] 
for i in range(N):
 w,v=map(int,input().split())
 for j in range(w,W+1)[::-1]:
  ans[j]=max(ans[j-w]+v,ans[j])
print(max(ans))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,W= map(int,input().split())
ans=[[0 for e in range(W+1)] for f in range(N+1)]
for i in range(N):
 w,v=map(int,input().split())
 for k in range(0,w):
  ans[i+1][k]=ans[i][k]
 for j in range(w,W+1):
  ans[i+1][j]=max(ans[i][j-w]+v,ans[i][j])
print(max(ans[N]))
### BUGGY CODE ###

S = input()
Q = int(input())
for _ in range(Q):
    A = list(map(str, input().split()))
    if A[0] == "1":
        S = S[::-1]
    else:
        if A[1] == "1":
            S = A[2] + S
        else:
            S = S + A[2]
print(S)

### FIXED CODE ###

from collections import deque
def main():
    S = deque(map(str, input()))
    Q = int(input())
    flag = False
    for _ in range(Q):
        A = tuple(map(str, input().split()))
        if A[0] == "1":
            flag = not(flag)
        else:
            if (A[1] == "1" and not(flag)) or (A[1] == "2" and flag):
                S.appendleft(A[2])
            else:
                S.append(A[2])
    if flag:
        print("".join(S)[::-1])
    else:
        print("".join(S))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

primes = [0, 0] + [1] * 9999999
for i in range(2, 3163):
    if primes[i]:
        for j in range(i*i, 10000001, i):
            primes[j] = 0

while True:
    n = int(input())
    if n == 0:
        break
    for i in range(5, n+1)[::-1]:
        if primes[i-8] & primes[i-6] & primes[i-2] & primes[i]:
            print(i)
            break

### FIXED CODE ###

import bisect


primes = [0, 0] + [1] * 9999999
for i in range(2, 3163):
    if primes[i]:
        for j in range(i*i, 10000001, i):
            primes[j] = 0

values = [i for i, v in enumerate(primes) if v]
while True:
    n = int(input())
    if n == 0:
        break
    index = bisect.bisect(values, n)
    for i in range(2, index)[::-1]:
        if all(primes[values[i]-j] for j in [0, 2, 6, 8]):
            print(values[i])
            break
### BUGGY CODE ###

N=int(input())
a=list(map(int, input().split()))
l = [i for i in range(1,N+1)]
c=0
for j in range(N):
  if l[0]==a[j]:
    del l[0]
  elif l[0]!=a[j]:
    c+=1
if len(l)==N:
  print(-1)
  exit()
print(c)

### FIXED CODE ###

N=int(input())
a=list(map(int, input().split()))
S=1
c=0
for j in range(N):
  if S==a[j]:
    S+=1
  elif S!=a[j]:
    c+=1
if c==N:
  print(-1)
  exit()
print(c)
### BUGGY CODE ###

def kaijo(x):
    v=1
    for i in range(1,x+1):
        v*=i
    return v


n,m=map(int,input().split())
mod=10**9+7
if abs(n-m)>=2:
    ans=0
else:
    if n==m:
        ans=2*kaijo(n)*kaijo(m)
    else:
        ans=kaijo(n)*kaijo(m)
print(ans%mod)


### FIXED CODE ###

def kaijo(x):
    v=1
    for i in range(1,x+1):
        v*=i
    return v


n,m=map(int,input().split())
mod=10**9+7
if abs(n-m)>=2:
    ans=0
else:
    ans=1
    for i in range(1,n+1):
        ans*=i
        ans%=mod
    for i in range(1,m+1):
        ans*=i
        ans%=mod
    if n==m:
        ans*=2
        ans%=mod

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

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

S = list(set(A))
count = [1 for s in S if A.count(s) % 2 == 1]

print(sum(count))

### FIXED CODE ###

import itertools

n = int(input())
A = [int(input()) for _ in range(n)]
A.sort()

count = 0
itrs = itertools.groupby(A)
for k, v in itrs:
    if len(list(v)) % 2 == 1:
        count += 1

print(count)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
  n, m = map(int, input().split())
  uf = UnionFind(n)

  for i in range(m):
    a, b = map(int, input().split())
    a -= 1; b-= 1;
    uf.union(a, b)
  
  max_len = 0
  for g in list(uf.all_group_members().values()):
    len_g = len(g)
    if len_g > max_len:
      max_len = len_g
      
  print(max_len)
  
main()

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

def main():
  n, m = map(int, input().split())
  uf = UnionFind(n)

  for i in range(m):
    a, b = map(int, input().split())
    a -= 1; b-= 1;
    uf.union(a, b)
  
  ans = 0
  for i in range(n):
    ans = max(ans, uf.size(i))
      
  print(ans)
  
main()
### BUGGY CODE ###

n, k = [ int(_) for _ in input().split() ]
h = [ int(_) for _ in input().split() ]

h.sort()

for i in range(len(h)):
  if max(h) < k:
    ans = 0
    break
  elif h[i] >= k:
    ans = len(h[i:])
    break
  
    
print(ans)

### FIXED CODE ###

n, k = [ int(_) for _ in input().split() ]
h = [ int(_) for _ in input().split() ]

h.sort(reverse=True)
flag = True
if h[n-1]>k:
	ans = n
	flag = False
elif h[0] < k:
	ans = 0
	flag = False
#k==max(h)とk==min(h)と合致する場合の分岐がなく、ans=0になっていた
elif h[n-1]==k:
	ans = n
elif h[0]==k:
	ans = h.count(h[0])
if flag == True:
	for i in range(0,n):
		if h[i] < k:
			ans = len(h[0:i])
			break

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

n=int(input())
a=list(map(int,input().split()))
q=int(input())
for i in range(q):
  s,t=list(map(int,input().split()))
  a=[t if j==s else j for j in a]
  print(sum(a))

### FIXED CODE ###

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

cnt=[0]*(10**5+1)

for i in a:
  cnt[i]+=1

xxx=sum(a)

q=int(input())

for i in range(q):
  l,r=map(int,input().split())
  pin=cnt[l]
  cnt[r]+=pin
  cnt[l]=0

  xxx+=(r-l)*pin

  print(xxx)
### BUGGY CODE ###

N = int(input())
A = [int(_) for _ in input().split()]
m = min(A)
if m == 1:
    print(m)
else:
    while m > 0:
        m = min(A)
        for i in range(0,len(A)):
            if A[i] != m:
                A[i] = A[i]%m
        z = A.count(0)
        for j in range(z):
            A.remove(0)
        if A.count(1) >= 1:
            m = 1
            break
        else:
            if [_%min(A) for _ in A].count(0) == len(A):
                m = min(A)
                break
    print(m)

### FIXED CODE ###

N = int(input())
A = [int(_) for _ in input().split()]
m = min(A)
while m > 0:
    for i in range(0,len(A)):
        if A[i] != m:
            A[i] = A[i]%m
    z = A.count(0)
    A = sorted(A)[z:]
    m = A[0]
    if m == 1:
        break
    else:
        if [_%m for _ in A] == [0]*len(A):
            break
print(m)
### BUGGY CODE ###


def read_input():
    n = int(input())
    alist = [-1]

    for i in range(n):
        alist.append(int(input()))


    return n, alist

def submit():
    n, alist = read_input()

    through = []
    curr_button = 1
    steps = 0
    while curr_button not in through:
        through.append(curr_button)
        curr_button = alist[curr_button]
        steps += 1

        if curr_button == 2:
            break

    if curr_button == 2:
        print(steps)
    else:
        print(-1)



if __name__ == '__main__':
    submit()

### FIXED CODE ###

from collections import defaultdict

def read_input():
    n = int(input())
    alist = [-1]

    for i in range(n):
        alist.append(int(input()))


    return n, alist

def submit():
    n, alist = read_input()

    through = defaultdict(int)
    curr_button = 1
    steps = 0
    while through[curr_button] == 0:
        through[curr_button] = 1
        curr_button = alist[curr_button]
        steps += 1

        if curr_button == 2:
            break

    if curr_button == 2:
        print(steps)
    else:
        print(-1)



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

def main():
    from collections import deque

    h, w = map(int, input().split())
    start = tuple(map(lambda x: int(x) - 1, input().split()))
    goal = tuple(map(lambda x: int(x) - 1, input().split()))

    maze = tuple([tuple(input()) for _ in range(h)])
    vis = [[False] * w for _ in range(h)]

    mw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    mj = list(set((i, j) for i in range(-2, 3) for j in range(-2, 3)) - set(mw) - {(0, 0)})

    q = deque()
    q.append((start[0], start[1], 0))
    while q:
        y, x, c = q.popleft()
        vis[y][x] = True
        if (y, x) == goal:
            print(c)
            break
        for a, b in mw:
            if 0 <= y + a < h and 0 <= x + b < w:
                if maze[y + a][x + b] == '.' and not vis[y + a][x + b]:
                    q.appendleft((y + a, x + b, c))
        for a, b in mj:
            if 0 <= y + a < h and 0 <= x + b < w:
                if maze[y + a][x + b] == '.' and not vis[y + a][x + b]:
                    q.append((y + a, x + b, c + 1))
    else:
        print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import deque

    h, w = map(int, input().split())
    ch, cw = map(lambda x: int(x) - 1, input().split())
    dh, dw = map(lambda x: int(x) - 1, input().split())

    m = [list(input()) for _ in range(h)]
    vis = [[False for _ in range(w + 2)] for _ in range(h + 2)]

    def walk(i, j):
        q = deque()
        q.append((i, j))
        edge = []
        while q:
            y, x = q.popleft()
            if vis[y][x]:
                continue
            vis[y][x] = True
            for s, t in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if not 0 <= y + s <= h - 1 or not 0 <= x + t <= w - 1:
                    continue
                if m[y + s][x + t] == '#':
                    edge.append((y, x))
                    continue
                q.appendleft((y + s, x + t))
        return edge

    def jump(i, j, c):
        q = walk(i, j)
        if vis[dh][dw]:
            return c
        nx = []
        c += 1
        while q:
            y, x = q.pop()
            for s in range(-2, 3):
                for t in range(-2, 3):
                    if not 0 <= y + s <= h - 1 or not 0 <= x + t <= w - 1:
                        continue
                    if vis[y + s][x + t]:
                        continue
                    if m[y + s][x + t] == '#':
                        continue
                    nx += walk(y + s, x + t)
                    if vis[dh][dw]:
                        return c
            if len(q) == 0:
                c += 1
                q = nx
                nx = []

    ans = jump(ch, cw, 0)
    print(ans if ans is not None else -1)


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

n, a = map(int, input().split())
x = list(map(int, input().split()))
M = max(x)
M = max(M, a)
dp = [[[0]*(n*M+1) for _ in range(n+1)] for _ in range(n+1)]

for j in range(n+1):
    for k in range(n+1):
        for s in range(n*M+1):
            if j == 0 and k == 0 and s == 0:
                dp[j][k][s] = 1
            elif j >= 1 and s < x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
            elif j >= 1 and k >= 1 and s>= x[j-1]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
ans = 0
for k in range(1, n+1):
    ans += dp[n][k][k*a]
print(ans)


### FIXED CODE ###

n, a = map(int, input().split())
x = list(map(int, input().split()))
M = max(x)
M = max(M, a)
dp = [[[0]*(n*M+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for j in range(n):
    for k in range(n+1):
        for s in range(n*M+1):
            if dp[j][k][s]:
                dp[j+1][k][s] += dp[j][k][s]
                dp[j+1][k+1][s + x[j]] += dp[j][k][s]

ans = 0
for k in range(1, n+1):
    ans += dp[n][k][k*a]
print(ans)
### BUGGY CODE ###

def binary_search(cards,n,number):
    low=0
    high=len(cards)-1

    while high-low>1:
        mid=(low+high)//2
        base=cards[mid]
        if base==number:
            for i in range(n):
                cards.insert(mid,number)
            return cards,mid
        if base<number:
            low=mid
        else:
            high=mid

    if cards[high]==cards[low]:
        if number>cards[high]:
            for i in range(n):
                cards.insert(high+1, number)
        else:
            for i in range(n):
                cards.insert(low, number)
    else:
        for i in range(n):
            cards.insert(high,number)
    return cards,mid

#1 3 5 7 9 11 <=8
#1 3 [5] 7 9 11 <= 8
#1 3 (5) 7 9 (11) <=8
#1 3 5 [7] 9 11 <= 8
#1 3 5 (7) 9 (11) <= 8
#1 3 5 7 [9] 11 <= 8
#1 3 5 (7) (9) 11
#1 3 5 [7] 9 11 <=8
#1 3 5 (7)
import sys
from heapq import heappush,heappop

def main():
    inp1=list(map(lambda x:int(x),input().split()))
    cards=list(map(lambda x:int(x),input().split()))
    cards_heap=[]
    for i in cards:
        heappush(cards_heap,i)

    N=inp1[0]
    M=inp1[1]
    B=[]
    C=[]
    for i in range(M):
        changes=list(map(lambda x:int(x),input().split()))
        B.append(changes[0])
        C.append(changes[1])

    cb=zip(C,B)
    cb=sorted(cb,reverse=True)
    C,B=zip(*cb)

    hand=[]
    for i in range(M):
        hand.extend([C[i] for j in range(B[i])])

    for i in hand:
        a=heappop(cards_heap)
        if i>a:
            heappush(cards_heap,i)
        else:
            heappush(cards_heap,a)
            break

    print(sum(cards_heap))

if __name__=="__main__":
    main()

### FIXED CODE ###

from heapq import heappush,heappop

def main():
    inp1=list(map(lambda x:int(x),input().split()))
    cards=list(map(lambda x:int(x),input().split()))
    cards_heap=[]
    for i in cards:
        heappush(cards_heap,i)

    N=inp1[0]
    M=inp1[1]
    B=[]
    C=[]
    for i in range(M):
        changes=list(map(lambda x:int(x),input().split()))
        B.append(changes[0])
        C.append(changes[1])

    cb=zip(C,B)
    cb=sorted(cb,reverse=True)


    for C,B in cb:
        for _ in range(B):
            a=heappop(cards_heap)
            if C>a:
                heappush(cards_heap,C)
            else:
                heappush(cards_heap,a)
                break

    print(sum(cards_heap))

if __name__=="__main__":
    main()