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

import sys
import bisect
input = sys.stdin.readline

class Bisect(object):
    def bisect_max(self, reva, func,M):
        ok = 0 # exist
        ng = 10**9 # not exist
        while abs(ok-ng) > 1:
            cnt = (ok + ng) // 2
            if func(cnt,reva,M):
                ok = cnt
            else:
                ng = cnt
        return ok

    def bisect_min(self, reva, func,M):
        ok = 10**9 # exist
        ng = 0 # not exist
        while abs(ok-ng) > 1:
            cnt = (ok + ng) // 2
            if func(cnt,reva,M):
                ok = cnt
            else:
                ng = cnt
        return ok

def solve1(tgt,reva,M):
    res=0
    n = len(reva)
    for i in range(n):
        tmp = bisect.bisect_left(reva,tgt-reva[i])
        tmp = n - tmp
        res += tmp
    if M <= res:
        return True
    else:
        return False

def solve2(tgt):
    print(tgt)
    if tgt > 12:
        return True
    else:
        return False
N,M = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
reva = a[::-1]
bs = Bisect()
Kmax = (bs.bisect_max(reva,solve1,M))

r=[0]
for i in range(N):
    r.append(r[i]+a[i])

res = 0
cnt = 0
t = 0
for i in range(N):
    tmp = bisect.bisect_left(reva,Kmax-reva[N-i-1])
    tmp2 = bisect.bisect_right(reva,Kmax-reva[N-i-1])
    if tmp!=tmp2:
        t = 1
    tmp = N - tmp
    cnt += tmp
    res += tmp*a[i]+r[tmp]
if t==1:
    res -= (cnt-M)*Kmax
print(res)


### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline

class Bisect(object):
    def bisect_max(self, reva, func,M):
        ok = 0 # exist
        ng = 4*(10**5) # not exist
        while abs(ok-ng) > 1:
            cnt = (ok + ng) // 2
            if func(cnt,reva,M):
                ok = cnt
            else:
                ng = cnt
        return ok

    def bisect_min(self, reva, func,M):
        ok = 10**5 # exist
        ng = 0 # not exist
        while abs(ok-ng) > 1:
            cnt = (ok + ng) // 2
            if func(cnt,reva,M):
                ok = cnt
            else:
                ng = cnt
        return ok

def solve1(tgt,reva,M):
    res=0
    n = len(reva)
    for i in range(n):
        tmp = bisect.bisect_left(reva,tgt-reva[i])
        tmp = n - tmp
        res += tmp
    if M <= res:
        return True
    else:
        return False

def solve2(tgt):
    print(tgt)
    if tgt > 12:
        return True
    else:
        return False
N,M = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
reva = a[::-1]
bs = Bisect()
Kmax = (bs.bisect_max(reva,solve1,M))

r=[0]
for i in range(N):
    r.append(r[i]+a[i])

res = 0
cnt = 0
t = 0
for i in range(N):
    tmp = bisect.bisect_left(reva,Kmax-reva[N-i-1])
    tmp2 = bisect.bisect_right(reva,Kmax-reva[N-i-1])
    if tmp!=tmp2:
        t = 1
    tmp = N - tmp
    cnt += tmp
    res += tmp*a[i]+r[tmp]
if t==1:
    res -= (cnt-M)*Kmax
print(res)
### BUGGY CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n,k = nm()
p = nl()

def exp(num):
  ret = (1+num)/2
  return ret

mx=0

for i in range(n-k+1):
  mx = max(sum(map(exp,p[i:i+k])),mx)
print(mx)

### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n,k = nm()
p = nl()

def exp(num):
  ret = (1+num)/2
  return ret

mx=0

pp = list(map(exp,p))
pd = [0]*(n+1)



for i in range(1,n+1):
  pd[i] = pd[i-1] + pp[i-1]




for i in range(n-k+1):
  mx = max(pd[i+k]-pd[i],mx)

print(mx)
### BUGGY CODE ###

N = int(input())
S = input()

stoi = {'R':0, 'G':1, 'B':2}
itos = {1:'R', 2:'G', 3:'B'}
li = [[0] * N for _ in range(3)]
ans = 0

for ind, s in enumerate(S):
    if(ind == 0):
        li[stoi[s]][ind] = 1
    else:
        for i in range(3):
            li[i][ind] = li[i][ind - 1]
        li[stoi[s]][ind] += 1

for i in range(N):
    for j in range(i + 1, N):
        if(S[i] == S[j]):
            continue
        k = 2 * j - i
        kc = 6 - (stoi[S[i]] + stoi[S[j]] + 2)
        res = li[kc-1][-1] - li[kc-1][j]
        if(k < N and kc == stoi[S[k]] + 1):
            res -= 1
        ans += res

print(ans)

### FIXED CODE ###

N = int(input())
S = input()

stoi = {'R':0, 'G':1, 'B':2}
itos = {1:'R', 2:'G', 3:'B'}
li = [[0] * N for _ in range(3)]
ans = 0

for ind, s in enumerate(S):
    if(ind == 0):
        li[stoi[s]][ind] = 1
    else:
        for i in range(3):
            li[i][ind] = li[i][ind - 1]
        li[stoi[s]][ind] += 1

for i in range(N):
    for j in range(i + 1, N):
        if(S[i] == S[j]):
            continue
        k = 2 * j - i
        kc = 6 - (stoi[S[i]] + stoi[S[j]] + 2)
        res = li[kc-1][-1] - li[kc-1][j]
        if(k < N and kc == stoi[S[k]] + 1):
            res -= 1
        ans += res

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

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

for i in s:
  if i not in ans:
    ans.append(i)

print(len(ans))

### FIXED CODE ###

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

s_set = set(s)

print(len(s_set))
### BUGGY CODE ###

import copy
n = int(input())
a = [int(input()) for _ in range(n)]
b = copy.copy(a)
b.sort(reverse=True)
m = max(a)

for i in range(n):
    if a[i] != max(a):
        print(max(a))
    else:
        print(b[1])

### FIXED CODE ###

import copy
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
b = copy.copy(a)
a.sort(reverse=True)
for i in range(n):
    if b[i] == a[0]:
        print(a[1])
    else:
        print(a[0])
### BUGGY CODE ###

t = int(input())
for i in range(t):
    a, b, c, d = map(int, input().split())
    rec = [a]
    flag = False
    num = 0
    while True and num < 100000:
        if a < b:
            break
        else:
            a = a % b
        if a <= c:
            a += d
        if a in rec:
            flag = True
            break
        num += 1
        rec.append(a)
    if flag:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

T = int(input())


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


for i in range(T):
    a, b, c, d = map(int, input().split())
    if a < b:
        print('No')
    elif d < b:
        print('No')
    elif c >= b:
        print('Yes')
    else:
        g = gcd(b, d)
        if b - g + a % g > c:
            print('No')
        else:
            print('Yes')
### BUGGY CODE ###


l=list(map(int,input().split()))
n=l[0]
w=l[1]
va=[0]*n
wa=[0]*n
for i in range(n):
        
    x=list(map(int,input().split()))
    wa[i]=x[0]
    va[i]=x[1]
dp=[[0 for i in range(w+1)] for j in range(n+1)]
for i in range(1,n+1):
  for j in range(1,w+1):
    if wa[i-1]>j:
      dp[i][j]=dp[i-1][j]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-wa[i-1]]+va[i-1])
print(dp[-1][-1])

### FIXED CODE ###

def knapSack(W, wt, val, n): 
	K = [[0 for x in range(W+1)] for x in range(n+1)] 

	
	for i in range(n+1): 
		for w in range(W+1): 
			if i==0 or w==0: 
				K[i][w] = 0
			elif wt[i-1] <= w: 
				K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]) 
			else: 
				K[i][w] = K[i-1][w] 

	return K[n][W] 




q=list(map(int,input().split()))
n=q[0]
W=q[1]
v=[0]*n
w=[0]*n
for _ in range(n):
  r=list(map(int,input().split()))
  w[_]=r[0]
  v[_]=r[1]
  




print(knapSack(W,w,v,n))
### BUGGY CODE ###

import copy

H,W = map(int,input().split())

S = ["#"] * (H+2)
S[0] = ["#"] * (W+2)
S[H+1] = ["#"] * (W+2)
for i in range(1,H+1):
    S[i] = ["#"]+ list(input()) + ["#"]

#print(S)
inf = 10 ** 3
data = [[[[inf for i in range(W+2)] for j in range(H+2)] for k in range(W+2)] for l in range(H+2)]

for i in range(1,H+1):
    for j in range(1,W+1):
        data[i][j][i][j] = 0

for m in range((H+2)*(W+2)):
    data_ = copy.copy(data)
    for i in range(1,H+1):
      for j in range(1,W+1):
        for k in range(1,H+1):
            for l in range(1,W+1):
                if S[i][j] == "#" or S[k][l] == "#":
                    continue
                data_[i][j][k][l] = min(data[i][j][k][l],data[i][j][k+1][l]+1,data[i][j][k-1][l]+1,data[i][j][k][l+1]+1,data[i][j][k][l-1]+1)

x = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        for k in range(1,H+1):
            for l in range(1,W+1):
                if x < data_[i][j][k][l] and data_[i][j][k][l] != inf:
                    x = data_[i][j][k][l]

print(x)


### FIXED CODE ###

#いい加減深さ優先探索, 幅優先探索をスムーズに実装してえなおい

H,W = map(int,input().split())

S = ["#"] * (H+2)
S[0] = ["#"] * (W+2)
S[H+1] = ["#"] * (W+2)
for i in range(1,H+1):
    S[i] = ["#"]+ list(input()) + ["#"]

inf = 10 ** 3
m = 0
mi = -1
mj = -1
mk = -1
ml = -1
  
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j] == "#":
            continue
        data = [[inf]*(W+2) for k in range(H+2)]
        data[i][j] = 0
        stack = [[i,j,0]]
        while stack:
            x = stack.pop()
            if S[x[0]+1][x[1]] == "." and data[x[0]+1][x[1]]>x[2]+1:
                data[x[0]+1][x[1]] = x[2]+1
                stack.append([x[0]+1,x[1],x[2]+1])
            if S[x[0]][x[1]+1] == "." and data[x[0]][x[1]+1]>x[2]+1:
                data[x[0]][x[1]+1] = x[2]+1
                stack.append([x[0],x[1]+1,x[2]+1])
            if S[x[0]-1][x[1]] == "." and data[x[0]-1][x[1]]>x[2]+1:
                data[x[0]-1][x[1]] = x[2]+1
                stack.append([x[0]-1,x[1],x[2]+1])
            if S[x[0]][x[1]-1] == "." and data[x[0]][x[1]-1]>x[2]+1:
                data[x[0]][x[1]-1] = x[2]+1
                stack.append([x[0],x[1]-1,x[2]+1])
            #print(i,j,stack)

        for k in range(1,H+1):
            for l in range(1,W+1):
                if data[k][l] > m and data[k][l] != inf:
                    m = data[k][l]
                    mi = i
                    mj = j
                    mk = k
                    ml = l

#print(mi,mj,mk,ml)
print(m)

#DFSならワイの実装力でも割とスムーズにできそう？
#なんで昨日これやらなかったんや
#と言いつつWAするアホ
### BUGGY CODE ###

class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    K = int(input())
    S = input()
    l = len(S)
    mod = 10**9 + 7
    c = cmbs(mod)
    r = 0
    x25 = 1
    x26 = pow(26, K, mod)
    inv26 = pow(26, mod-2, mod)
    
    for i in range(K+1):
        r += c.cmb(l+i-1, i) * x25 * x26
        x25 *= 25
        x25 %= mod
        x26 *= inv26
        x26 %= mod
        r %= mod
    return r
print(main())


### FIXED CODE ###

class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 2 * (10 ** 6) + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 2 * (10 ** 6):
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    K = int(input())
    S = input()
    l = len(S)
    mod = 10**9 + 7
    c = cmbs(mod)
    r = 0
    x25 = 1
    x26 = pow(26, K, mod)
    inv26 = pow(26, mod-2, mod)
    for i in range(K+1):
        r = (r + c.cmb(l+i-1, i) * x25 * x26) % mod
        x25 = x25 * 25 % mod
        x26 = x26 * inv26 % mod
    return r % mod
print(main())
### BUGGY CODE ###

import math, sys
N , M = list(map(int, input().split()))

Es = [[] for _ in range(N)]
for i in range(M):
    A , B = list(map(int, input().split()))
    Es[A-1].append(B-1)
    Es[B-1].append(A-1)


i = 1
j = 1
d = 0
#ans = [-1 for _ in range(N)]
cand = []
used = [False for i in range(N)]
dis = [math.inf for i in range(N)]
ans = [-1 for i in range(N)]
tar = 0
cnt = 1
print("Yes")
p = 0

cand = [0]
while len(cand)>0:
    tar = cand.pop(0)
    for each in Es[tar]:
        if not used[each]:
            cand.append(each)
            ans[each]=tar+1
            used[each]= True
for i in range(1,N):
    print(ans[i])


### FIXED CODE ###

import math, sys
from collections import deque
N , M = list(map(int, input().split()))

Es = [[] for _ in range(N+1)]
for i in range(M):
    A , B = list(map(int, input().split()))
    Es[A].append(B)
    Es[B].append(A)

used = [False]*(N+1)
used[1] = True

ans = [-1]*(N+1)

cand = deque([1])
while len(cand)>0:
    tar = cand.popleft()
    for each in Es[tar]:
        if used[each]:
            continue
        cand.append(each)
        ans[each]=tar
        used[each]= True

print("Yes")
for i in range(2,N+1):
    print(ans[i])
### BUGGY CODE ###

S = input()
l = len(S)
while True:
    s = S.replace('01', '')
    if s == S:
        break
    S = s
while True:
    s = S.replace('10', '')
    if s == S:
        break
    S = s
print(l - len(S))

### FIXED CODE ###

from collections import Counter
c = Counter(input())
print(2*min(c['0'], c['1']))
### BUGGY CODE ###

n,m=map(int,input().split())
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=list(map(lambda x:int(x)-1,input().split()))
key=[[] for _ in range(n)]
for i in range(m):
    for j in c[i]:
        key[j].append(i)

ans=float('inf')
def serch(keyset,i,box):
    global ans
    if i==n:
        if box==set(range(n)):
            ans=min(ans,sum(a[k] for k in keyset))
    else:
        if i in box:
            serch(keyset,i+1,box)
        else:
            for k in key[i]:
                serch(keyset|{k},i+1,box|set(c[k]))

serch(set([]),0,set([]))
print(-1 if ans==float('inf') else ans)

### FIXED CODE ###

n,m=map(int,input().split())
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=sum(map(lambda x:2**(int(x)-1),input().split()))

dp=[-1]*(2**n)
for i in range(m):
    for j in range(2**n):
        if j|c[i]==c[i]:
            if dp[j]<0:
                dp[j]=a[i]
            else:
                dp[j]=min(dp[j],a[i])
for i in range(m):
    for j in range(2**n):
        if dp[j]<0:
            continue
        if dp[c[i]|j]<0:
            dp[c[i]|j]=dp[j]+a[i]
        else:
            dp[c[i]|j]=min(dp[c[i]|j],dp[j]+a[i])
print(dp[-1])
### BUGGY CODE ###

import itertools

while 1:
    try:
      a, b= map(int, raw_input().split())
    except:
      break
    GCD = a * b
    LCM = 0
    # GCD
    for i, j in itertools.product(range((a if a > b else b) / 2), repeat=2):
        if a * (i+1) == b * (j+1) and GCD > a * (i+1):
            GCD = a * (i+1)
    # LCM
    flag = 0
    for i in range(a if a > b else b, 1, -1):
        if a % i == 0 and b % i == 0 and flag == 0:
            LCM = i
            flag += 1
    print "{} {}".format(str(GCD), str(LCM))

### FIXED CODE ###

def get_gcd(a,b):
	if a > b: a, b = b, a
	if b % a == 0:
		return a
	else:
		return get_gcd(a, b % a)

def get_lcm(a,b,g):
	return a * b / g

while True:
	try:
		a,b = map(int, sorted(raw_input().split()))
		GCD = get_gcd(a,b)
		LCM = get_lcm(a,b,GCD)
		print "{} {}".format(GCD, LCM)
	except EOFError:
		break
### BUGGY CODE ###

from collections import deque

S = deque(list(str(input())))
Q = int(input())

for i in range(Q):
    Query =  [str(p) for p in input().split()]
    if(int(Query[0]) == 1):
        S.reverse()
    else:
        if(int(Query[1]) == 1):
            S.appendleft(Query[2])
        else:
            S.append(Query[2])

print("".join(list(S)))

### FIXED CODE ###

from collections import deque

S = deque(list(str(input())))
Q = int(input())
flag = False

for i in range(Q):
    Query =  [str(p) for p in input().split()]
    if(int(Query[0]) == 1):
        flag = not(flag)
    else:
        if(int(Query[1]) == 1):
            if(flag):
                S.append(Query[2])
            else:
                S.appendleft(Query[2])
        else:
            if(flag):
                S.appendleft(Query[2])
            else:
                S.append(Query[2])

if(flag):
    S.reverse()

print("".join(list(S)))
### BUGGY CODE ###

n,k,q=map(int,input().split())
d=[k]*n
s=[]

for i in range(q):
  s.append(int(input()))
for i in range(q):
  for j in range(n):
    if s[i]!=(j+1):
      d[j]-=1
for i in range(n):
  if d[i]<=0:
    print("No")
  else:
    print("Yes")



### FIXED CODE ###

n,k,q=map(int,input().split())
d=[]
p=[]
for i in range(n):
   p.append(k-q)
for i in range(q):
   d.append(int(input()))
   p[d[i]-1] +=1
for i in range(n):
   if p[i]>0:
      print("Yes")
   else:
      print("No")
### BUGGY CODE ###

class SegmentTree:
    def __init__(self, n, sentinel=0):
        self.n = 1 << n.bit_length()
        self.offset = self.n - 1
        m = (self.n << 1) - 1
        self.data = [sentinel] * m
        self.sentinel = sentinel

    def update(self, k, x):
        i = k + self.offset
        self.data[i] = max(self.data[i], x)
        while i:
            i = (i - 1) // 2
            self.data[i] = max(self.data[i], x)

    def get_max(self, a, b, i=0, l=0, r=None):
        if r is None:
            r = self.n

        if b <= l or r <= a:
            return self.sentinel

        if a <= l and r <= b:
            return self.data[i]

        m = (l + r) // 2
        li = (i << 1) + 1
        return max(self.get_max(a, b, li, l, m), self.get_max(a, b, li + 1, m, r))


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
srt = sorted((h, i) for i, h in enumerate(hhh))
lst = SegmentTree(n, 0)

for h, i in srt:
    lst.update(i, lst.get_max(0, i) + aaa[i])
    # print(lst.data)
print(lst.get_max(0, lst.n))


### FIXED CODE ###

def solve(n, hhh, aaa):
    n2 = 1 << n.bit_length()
    offset = n2 - 1
    data = [0] * ((n2 << 1) - 1)

    def update(k, x):
        i = k + offset
        data[i] = max(data[i], x)
        while i:
            i = (i - 1) // 2
            data[i] = max(data[i], x)

    def get_max(k):
        i = k + offset
        ret = data[i]
        while i:
            if i % 2 == 0:
                ret = max(ret, data[i - 1])
            i = (i - 1) // 2
        return ret

    srt = sorted((h, i) for i, h in enumerate(hhh))
    for h, i in srt:
        update(i, get_max(i) + aaa[i])

    return data[0]


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
print(solve(n, hhh, aaa))
### BUGGY CODE ###

import copy
import sys

sys.setrecursionlimit(10 ** 7)

N = int(input())
uvw = [list(map(int, input().split(' '))) for _ in range(N - 1)]

# 適当に最初の色を決める
# その点を親として、
# 親からの距離が偶数だったら親と同じ色
# 親からの距離が奇数だったら親と違う色

pool = [1]

result = [0 for i in range(N)]  # 頂点1は白くする

while pool:
    top = pool.pop()
    copy_uvw = copy.deepcopy(uvw)
    for e in copy_uvw:
        if top == e[0]:
            uvw.remove(e)
            pool.append(e[1])
            if e[2] % 2 == 0:
                # 親と同じ色を入れる
                result[e[1] - 1] = 0 if result[e[0] - 1] == 0 else 1
            else:
                # 親と違う色を入れる
                result[e[1] - 1] = 1 if result[e[0] - 1] == 0 else 0
        elif top == e[1]:
            uvw.remove(e)
            pool.append(e[0])
            if e[2] % 2 == 0:
                # 親と同じ色を入れる
                result[e[0] - 1] = 0 if result[e[1] - 1] == 0 else 1
            else:
                # 親と違う色を入れる
                result[e[0] - 1] = 1 if result[e[1] - 1] == 0 else 0

for i in result:
    print(i)


### FIXED CODE ###

import copy
import sys

sys.setrecursionlimit(10 ** 7)

N = int(input())
uvw = [list(map(int, input().split(' '))) for _ in range(N - 1)]

# 適当に最初の色を決める
# その点を親として、
# 親からの距離が偶数だったら親と同じ色
# 親からの距離が奇数だったら親と違う色

children = [[] for _ in range(N + 1)]

for e in uvw:
    children[e[0]].append([e[1], e[2]])
    children[e[1]].append([e[0], e[2]])

pool = [1]
result = [0 for i in range(N + 1)]  # 頂点1は白くする

marked = set()
marked.add(1)

while pool:
    top = pool.pop()
    for child in children[top]:
        child_edge = child[0]
        length = child[1]

        if child_edge not in marked:
            pool.append(child_edge)
            marked.add(child_edge)
        if length % 2 == 0:
            result[child_edge] = 0 if result[top] == 0 else 1
        else:
            result[child_edge] = 1 if result[top] == 0 else 0

for i in result[1:]:
    print(i)
### BUGGY CODE ###

from sys import stdin
N = int(stdin.readline().rstrip())
for h in range(1,3501):
    for n in range(1,3501):
        if (4*h*n-N*h-N*n) != 0:
            w = (N*h*n)/(4*h*n-N*h-N*n)
        else:
            continue
        if w.is_integer() and w > 0:
            print(h,n,int(w))
            break
    else:
        continue
    break

### FIXED CODE ###

from sys import stdin
N = int(stdin.readline().rstrip())
for h in range(1,3501):
    for n in range(1,3501):
        if (4*h*n-N*h-N*n) != 0:
            w = (N*h*n)/(4*h*n-N*h-N*n)
        else:
            continue
        if w.is_integer() and w > 0:
            print(h,n,int(w))
            break
    else:
        continue
    break
### BUGGY CODE ###

import heapq

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for i in range(m)]
bc.sort(key=lambda x: x[1])
heapq.heapify(a)

for i in range(m):
  for j in range(bc[i][0]):
    temp = heapq.heappop(a)
    temp2 = bc[i][1]
    if temp2 > temp:
      heapq.heappush(a, temp2)
    else:
      heapq.heappush(a, temp)
      break
      
print(sum(a))

### FIXED CODE ###

import heapq
 
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for i in range(m)]
bc.sort(key=lambda x: x[1], reverse = True)
heapq.heapify(a)
 
for i in range(m):
  for j in range(bc[i][0]):
    temp = heapq.heappop(a)
    temp2 = bc[i][1]
    if temp2 > temp:
      heapq.heappush(a, temp2)
    else:
      heapq.heappush(a, temp)
      print(sum(a))
      quit()
      
print(sum(a))