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

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


def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])

def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res

#####単位元######
ide_ele_max = 0

#num_max:n以上の最小の2のべき乗
# num_max =2**(n-1).bit_length()
num_max = 2**(len(str(bin(n-1))) -2)
seg_max=[ide_ele_max]*2*num_max

for i in range(n):
    h_i = h[i]
    update_max( h_i-1, query_max(0,h_i) + a[i] )

print(query_max(0,n))

### FIXED CODE ###

class SegmentTree:
    def __init__(self, a, mode='min'):
        self.mode = mode
        if self.mode == 'min':
            self.padding = float('inf')
        elif mode == 'max':
            self.padding = -float('inf')
        elif mode == 'sum':
            self.padding = 0
        
        n = len(a)
        self.N = 2 ** (n-1).bit_length()
        self.data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-n)
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = self._segfunc(*[self.data[i], self.data[i-1]])
    
    def _segfunc(self, *v_list):
        if self.mode == 'min':
            return min(v_list)
        elif self.mode == 'max':
            return max(v_list)
        elif self.mode == 'sum':
            return sum(v_list)
    
    def update(self, idx, x):
        idx = self.N - 1 + idx
        self.data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = self._segfunc(
                *[self.data[2*idx+1], self.data[2*idx+2]]
            )
    
    def search(self, i, j):
        # [i, j)の区間の最小値を求める
        idx1 = self.N-1+i
        idx2 = self.N-1+j-1
        result = self.padding
        while idx1 + 1 < idx2:
            if idx1&1 == 0: # idx1が偶数
                result = self._segfunc(*[result, self.data[idx1]])
            if idx2&1 == 1: # idx2が奇数
                result = self._segfunc(*[result, self.data[idx2]])
                idx2 -= 1
            
            idx1 //= 2
            idx2 = (idx2 - 1)//2
        
        if idx1 == idx2:
            result = self._segfunc(result, self.data[idx1])
        else: # idx1 + 1 == idx2
            result = self._segfunc(*[result, self.data[idx1], self.data[idx2]])
        
        return result


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

dp = [0] * (N+1)
st = SegmentTree(dp, mode='max')

ans = 0
for h, a in zip(H, A):
  M = st.search(0, h)
  st.update(h, M + a)

print(st.search(0, N+1))
### BUGGY CODE ###

'''
Created on 2020/08/29

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  N,M=map(int,pin().split())
  cnt=[0]*N 
  dp=[[0]*N for _ in range(N)]
  for i in range(M):
    A,B=map(int,pin().split())
    t=max(A,B)
    s=min(A,B)
    if dp[s-1][t-1]==0:
      cnt[s-1]+=1
      cnt[t-1]+=1
      dp[s-1][t-1]=1
  print(max(cnt)+1)
  return 
main()

### FIXED CODE ###

'''
Created on 2020/09/03

@author: harurun
'''
from dataclasses import *
@dataclass
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():
  import sys
  pin=sys.stdin.readline

  N,M=map(int,pin().split())
  uf=UnionFind(N)
  for i in range(M):
    A,B=map(int,pin().split())
    A-=1
    B-=1
    uf.union(A, B)

  ans=0
  for j in range(N):
    ans=max(ans,uf.size(j))
  print(ans)
  return

main()

#解説AC
### BUGGY CODE ###

import sys
from collections import deque

input = sys.stdin.readline
digtmp = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def flatten_2dim(array):
    return [item for sublist in array for item in sublist]

def main():
    H, W = map(int, input().split())
    grid = []; black = deque([])
    grid.append([0]*(W+2))
    for i in range(H):
        tmp = list(input()[:-1])
        for j in range(W):
            if tmp[j] == '#':
                black.append((i+1, j+1))
                tmp[j] = 0
        grid.append([0] + tmp + [0])
    grid.append([0]*(W+2))

    for _ in range(pow(10, 6)):
        fr = black.popleft()
        gfr = grid[fr[0]][fr[1]]
        for d in digtmp:
            to = (fr[0]+d[0], fr[1]+d[1])
            gto = grid[to[0]][to[1]]
            if gto == '.':
                grid[to[0]][to[1]] = gfr + 1
                black.append(to)
            elif gto != '#':
                if gfr + 1 < gto:
                    grid[to[0]][to[1]] = gfr + 1
                    black.append(to)
            else:
                pass
        if len(black) == 0:
            break
    
    ans = max(flatten_2dim(grid))
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque

input = sys.stdin.readline
digtmp = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def flatten_2dim(array):
    return [item for sublist in array for item in sublist]

def main():
    H, W = map(int, input().split())
    grid = []; black = deque([])
    grid.append([0]*(W+2))
    for i in range(H):
        tmp = list(input()[:-1])
        for j in range(W):
            if tmp[j] == '#':
                black.append((i+1, j+1))
                tmp[j] = 0
        grid.append([0] + tmp + [0])
    grid.append([0]*(W+2))

    for _ in range(pow(10, 6)):
        fr = black.popleft()
        gfr = grid[fr[0]][fr[1]]
        for d in digtmp:
            to = (fr[0]+d[0], fr[1]+d[1])
            gto = grid[to[0]][to[1]]
            if gto == '.':
                grid[to[0]][to[1]] = gfr + 1
                black.append(to)
            elif gto != '#':
                if gfr + 1 < gto:
                    grid[to[0]][to[1]] = gfr + 1
                    black.append(to)
            else:
                pass
        if len(black) == 0:
            break
    
    ans = max(flatten_2dim(grid))
    print(ans)

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

MOD = 1000000007

def union(x,y):
    if len(x)==1:
        if len(y)==1:
            return (1 if x[0]==y[0] else 0)
        else:
            return (1 if y[-1]>=x[0] else 0)
    if len(x)>1:
        if len(y)==1:
            return (1 if x[-1]>=y[0] else 0)
        else:
            return min(len(x),len(y))

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = [[] for _ in range(n)]
y = [[] for _ in range(n)]
z = 1
x[0] += [a[0]]
y[n-1] += [b[n-1]]

for i in range(1,n):
    if a[i-1]<a[i]:
        x[i] += [a[i]]
    else:
        x[i] += list(range(1,a[i]+1))

for j in range(n-1, 0, -1):
    if b[j-1]>b[j]:
        y[j-1] += [b[j-1]]
    else:
        y[j-1] += list(range(1,b[j-1]+1))

for i in range(0,n):
    z *= union(x[i],y[i]) % MOD
    z = z % MOD

print(z)


### FIXED CODE ###

import sys

MOD = 1000000007

def union(x,y):
    if len(x)==1:
        if len(y)==1:
            return (1 if x[0]==y[0] else 0)
        else:
            return (1 if y[-1]>=x[0] else 0)
    if len(x)>1:
        if len(y)==1:
            return (1 if x[-1]>=y[0] else 0)
        else:
            return min(len(x),len(y))

n = int(input())
a = list(map(lambda x: int(x) % MOD, input().split()))
b = list(map(lambda x: int(x) % MOD, input().split()))
x = [0 for _ in range(n)]
y = [0 for _ in range(n)]
x[0] = 1
y[-1] = 1
z = 1

for i in range(1,n):
    if a[i-1]<a[i]:
        x[i] = 1
    else:
        x[i] = 0

for j in range(n-1, 0, -1):
    if b[j-1]>b[j]:
        y[j-1] += 1
    else:
        y[j-1] += 0

for i in range(n):
    if x[i] == 1 and y[i] == 0:
        if a[i] > b[i]:
            print(0)
            sys.exit()
    elif x[i] == 0 and y[i] == 1:
        if a[i] < b[i]:
            print(0)
            sys.exit()
    elif x[i] == 1 and y[i] == 1:
        if a[i] != b[i]:
            print(0)
            sys.exit()
    else:
        z *= min(a[i],b[i])
        z = z % MOD

print(z)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

YES = "YES"  # type: str
NO = "NO"  # type: str

def solve(N: int, A: "List[int]"):
    for i in range(0,N):
        if (A[i] in A[i+1:]):
            print(NO)
            return

    print(YES)


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

YES = "YES"  # type: str
NO = "NO"  # type: str

def solve(N: int, A: "List[int]"):
    p = sorted(A)
    for i in range(0,N-1):
        if (p[i] == p[i+1]):
            print(NO)
            return

    print(YES)


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

N = int(input())
A_list = list(map(int, input().split(' ')))
for i in range(N):
    A = A_list.pop(0)
    if A in A_list:
        print('NO')
        exit()
    else:
        A_list.append(A)
print('YES')

### FIXED CODE ###

N = int(input())
A_set = set(list(map(int, input().split(' '))))
if len(A_set) == N:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

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

ans = 217937901270479417
for i in range(1,len(a)):
    ans = min(ans, abs(sum(a[:i]) - sum(a[i:])))
print(ans)

### FIXED CODE ###

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

ans = 217937901270479417
_sum = sum(a)
sum_1 = 0
for i in range(0,len(a)):
    sum_1 += a[i]
    sum_2 = _sum - sum_1
    ans = min(ans, abs(sum_1 - sum_2))
print(ans)
### BUGGY CODE ###

def fib(n):
  if n < 0:
    print("error")
    exit()
  if n < 2:
    return 1
  result = fib(n-1) + fib(n-2)
  return result

#n = int(input())
for n in range(44+1):
	print(fib(n))

### FIXED CODE ###

def fibr(n):
    if arr[n] != 0:
        return arr[n]
    if n < 2:
        arr[n] = 1
    else:
        arr[n] = fibr(n-1) + fibr(n-2)
    return arr[n]

n = int(input())
arr = [0 for i in range(n+1)]
print(fibr(n))
### BUGGY CODE ###

N = int(input())
s = []
count = 0
for _ in range(N):
  s.append(sorted(input()))
for i in range(N):
  for j in range(i+1,N):
    if s[i] == s[j]:
      count += 1
print(count)

### FIXED CODE ###

N = int(input())
s = list(list(input()) for i in range(N))
for i in range(N):
    s[i].sort()
s.sort()
ans = 0
same = 1
for i in range(1,N):
    if s[i] == s[i-1]:
        ans += same
        same += 1
    else:
        same = 1
print(ans)
### BUGGY CODE ###

N,M = map(int, input().split())
l_table = [False for _ in range(N)]
r_table = [False for _ in range(N)]
lr_table = {}
for _ in range(M):
    l_n, r_n = map(int, input().split())
    l_table[l_n-1] = True
    r_table[r_n-1] = True
    lr_table[(l_n-1,r_n-1)] = True

ret = 0
lefts = []
for i in range(N):
    if lefts and r_table[i] and any([(left,i) in lr_table and lr_table[(left,i)] for left in lefts]):
        # print(i,lefts)
        ret += 1
        lefts = []
    if l_table[i]:
        lefts.append(i)

print(ret)

### FIXED CODE ###

N,M = map(int, input().split())
r_table = [-1]*N
for _ in range(M):
    l_n, r_n = map(int, input().split())
    r_table[r_n-1] = max(l_n-1, r_table[r_n-1])

ret = 0
left = -1
for i in range(N):
    if left < r_table[i]:
        ret += 1
        left = i-1

print(ret)
### BUGGY CODE ###

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

from collections import defaultdict
dp = defaultdict(lambda: 0)
dp[(0,0)] = 1
for a in A:
    for (i,j),v in list(dp.items()):
        if j+a > S: continue
        dp[(i+1,j+a)] += v

ans = 0
for (i,j),v in dp.items():
    if j!=S: continue
    ans += pow(2,N-i,MOD) * v
print(ans%MOD)

### FIXED CODE ###

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

dp = [[0]*(S+1) for i in range(N+1)]
dp[0][0] = 1

for i,a in enumerate(A):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j]*2
        dp[i+1][j] %= MOD
        if j+a <= S:
            dp[i+1][j+a] += dp[i][j]
            dp[i+1][j+a] %= MOD
print(dp[-1][-1])
### BUGGY CODE ###

k = int(input())

def mygcd(x,y):
    a = min(x,y)  # 最小値
    b = max(x,y)  # 最大値
    r = 2  # 余り
    while r != 0:
        r = b % a
        b = a
        a = r
    return b

ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans += mygcd(mygcd(i,j),k)

print(ans)

### FIXED CODE ###

K   = int(input())
Sum = 0
def mygcd(x,y):
    a = min(x,y)  # 最小値
    b = max(x,y)  # 最大値
    r = 2  # 余り
    while r != 0:
        r = b % a
        b = a
        a = r
    return b

for A in range(1,K+1):
    for B in range(1,K+1):
        AB = mygcd(A,B)
        if AB==1:
            Sum = Sum+K
        else:
            for C in range(1,K+1):
                Sum = Sum+mygcd(AB,C)
print(Sum)
### BUGGY CODE ###

n = int(input())
s = 0
while True:
    n, m = divmod(n, 10)
    s += m * 10
    if n <= 0:
        break
print('Yes' if s % 9 == 0 else 'No')

### FIXED CODE ###

n = input()
s = 0
for i in range(len(n)):
    s += int(n[i])
print('Yes' if s % 9 == 0 else 'No')
### BUGGY CODE ###

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

ans = 0
for i in range(2 ** n):
    pattern = [0] * n
    for j in range(n):
        if i >> j & 1:
            pattern[j] = 1

    val = 0
    for k in range(n):
        if pattern[k] == 1:
            val += x[k]

    if val != 0 and sum(pattern) != 0:
        if val / sum(pattern) == a:
            ans += 1

print(ans)


### FIXED CODE ###

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

dp = [[[0] * (50 * (n + 10)) for _ in range(n + 10)] for _ in range(n + 10)]
dp[0][0][0] = 1

for i in range(n):
    for use in range(n):
        for total in range(n * a):
            if dp[i][use][total]:
                dp[i + 1][use][total] += dp[i][use][total]
                dp[i + 1][use + 1][total + x[i]] += dp[i][use][total]

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

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


import fractions
K=int(input())
ans=0

for n in range(1,K+1):
    for m in range(1,K+1):
        for l in range(1,K+1):
            gcd=fractions.gcd(n,m)
            gcd=fractions.gcd(gcd,l)
            
            ans+=gcd
   
print(ans)


### FIXED CODE ###


import math
K=int(input())
ans=0
A=0

for n in range(1,K+1):
    for m in range(1,K+1):
        x=math.gcd(n,m)
        for l in range(1,K+1):
            A=math.gcd(x,l)    
            ans+=A
            
print(ans)
### BUGGY CODE ###

from fractions import gcd
n = int(input())
yakusuu = set()
ans = set()
for i in range(1, int((n-1)**(1/2))+1):
    if (n-1) % i == 0:
        yakusuu.add(i)
        yakusuu.add((n-1)//i)

for i in range(1, int(n**(1/2))+1):
    if n % i == 0:
        yakusuu.add(i)
        yakusuu.add(n//i)
yakusuu.remove(1)

for i in yakusuu:
    k = n

    if gcd(i, k) == 1:
        if k % i == 1:
            ans.add(i)
        continue

    k = n
    while k >= i:
        if k % i == 0:
            k //= i
        else:
            k -= i
        if gcd(i, k) == 1:
            if k % i == 1:
                k = 1
            else:
                k = 0

    if k == 1:
        ans.add(i)

print(len(ans))


### FIXED CODE ###

from fractions import gcd
n = int(input())
yakusuu = set()
ans = set()
for i in range(1, int((n-1)**(1/2))+1):
    if (n-1) % i == 0:
        yakusuu.add(i)
        yakusuu.add((n-1)//i)

for i in range(1, int(n**(1/2))+1):
    if n % i == 0:
        yakusuu.add(i)
        yakusuu.add(n//i)
yakusuu.remove(1)



for i in yakusuu:
    k = n
    if gcd(i, k) == 1:
        if k % i == 1:
            ans.add(i)
        continue

    k = n
    while k >= i:
        if k % i == 0:
            k //= i
        else:
            if k % i == 1:
                k = 1
            else:
                k = 0
    if k == 1:
        ans.add(i)

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

#input
N, P = map(int, input().split())
S = list(map(int, list(input())))

# process
def toNum(l):
    n = 0
    for i in range(len(l[::-1])):
        n += l[i]*10**i
    return n

ans = 0
for i in range(N):
    for j in range(i+1, N+1):
#        print("{} {} {}".format(i, j, S[i:j]))
        if toNum(S[i:j])%P == 0:
            ans += 1 

# output
print(ans)

# print("ans: {}".format(ans))


### FIXED CODE ###

#input
N, P = map(int, input().split())
S = input()

# process
ans = 0
if P == 2 or P == 5:
    # 1桁目がPで割り切れる数をカウント
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i+1

else:
    cnt = [0]*P # S[i:N]%Pの結果をカウント
    num = 0
    tenPow = 1
    for i in reversed(range(N)):
        num = (num + int(S[i])*tenPow)%P
        tenPow = tenPow*10%P
        cnt[num] += 1

    ans += cnt[0]
    for c in cnt:
        ans += c*(c-1)//2 # c=0,1のときは0加算

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

S=input()
src=[0]*2019
ans=0
pre=0
for s in range(len(S)):
  x=int(S[-(s+1)])*(10**s)
  a=(x+pre)%2019
  src[a]+=1
  pre+=x
  ans+=src[a]-1
print(ans+src[0])

### FIXED CODE ###

S=input()
N=len(S)

a=0
t=1
d=[0]*2019
d[0]=1
for i in range(N):
  a+=int(S[N-1-i])*t
  a%=2019
  t*=10
  t%=2019
  d[a]+=1

ans=0
for n in d:
  ans += n*(n-1)//2
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

def lcm(a,b):
    return a*b//gcd(a,b)

n = I()
a = LI()
l = 1
for i in range(n):
    l = lcm(l,a[i])

ans = 0
for i in range(n):
    ans += l // a[i]
    ans %= mod
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

n = I()
a = LI()
l = lcm(a)
ans = 0
l %= mod
for i in a:
    ans += l*pow(i,mod-2,mod)
    ans %= mod
print(ans)
### BUGGY CODE ###

# input
n = int(input())

edge = [[0, 0, 0] for i in range(n-1)]
for i in range(n-1):
    edge[i][0] ,edge[i][1] = map(int, list(input().split()))

# process
k = 0
pcolors = [0 for i in range(n)]
for i in range(n):
    color = 0
    for j in range(n-1):
        if edge[j][0] == i+1:
            color += 1
            if color == pcolors[i]: color += 1

            edge[j][2] = color
            pcolors[edge[j][1]-1] = color
            if k < color: k = color
    

# output
print(k)
for e in edge:
    print(e[2])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

# input
n = int(input())

edges = [[] for i in range(n)]
for i in range(n-1):
    a ,b = map(int, list(input().split()))
    edges[a-1].append((b-1, i))

# process
ans = [0]*(n-1)

def f(a, c):
    color = 1
    for b, i in edges[a]:
        if color == c: color += 1
        ans[i] = color 
        f(b, color)
        color += 1

f(0, 0)

# output
print(max(ans))
for i in ans:
    print(i)
### BUGGY CODE ###

N=input()
A=list(map(int, input().split()))
c=0
while len(A)!=0:
  a=A.index(max(A))
  for n in A[a:]:
    c+=(max(A)-n)
  del A[a:]
print(c)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
c=0
for i in range(N-1):
  if A[i]>A[i+1]:
    c+=A[i]-A[i+1]
    A[i+1]=A[i]
print(c)
### BUGGY CODE ###

s = input()
k = int(input())
l = len(s)
substr = set()

for i in range(0,l):
    for j in range(i+1,l+1):
        substr.add(s[i:j])

substr = sorted(list(substr))
print(substr[k-1])


### FIXED CODE ###

s = input()
K = int(input())
idx = [[] for _ in range(26)]

for i in range(len(s)):
    idx[ord(s[i])-ord("a")].append(i)

substr = set()
for i in range(26):
    for j in idx[i]:
        for k in range(j+1,j+6):
            substr.add(s[j:k])
    if len(substr) >= K:
        substr = sorted(list(substr))
        break

print(substr[K-1])
### BUGGY CODE ###

import heapq
import numpy as np
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
A.sort()
A = np.array(A)
for i in range(M):
  b, c = map(int, input().split())
  BC.append([b, c])
  
for i in range(M):
  place = np.where(A < BC[i][1])
  if len(place[0]) >= BC[i][0]:
    A[:BC[i][0]] = BC[i][1]
  else:
    A[:len(place[0])] = BC[i][1]
  A.sort()
print(int(np.sum(A)))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
a = []

for i in range(M):
  b = list(map(int, input().split()))
  a.append(b)
  
from operator import itemgetter
A.sort()
a.sort(key = itemgetter(1))
count = 0
for i in range(N):
  if A[i] < a[-1-count][1]:
    A[i] =  a[-1-count][1]
    a[-1-count][0] -= 1
    if a[-1-count][0] == 0:
      count += 1
    if count == M:
      break
print(sum(A))