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

import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n = onem()

a = l()

b = l()

t = []

for i in range(n):
    hq.heappush(t,[-b[i],i])

co = 0
while True:
    if len(t) == 0:
        break
    k = hq.heappop(t)
    co = co + 1
    k = [-k[0],k[1]]
    if k[1] == 0:
        k[0] -= b[-1] + b[1]
    elif k[1] == n-1:
        k[0] -= b[0] + b[-2]
    else:
        k[0] -= b[k[1]+1] + b[k[1]-1]
    b[k[1]] = k[0]
    if b[k[1]] < a[k[1]]:
        print(-1)
        exit()
    if b[k[1]] != a[k[1]]:
        hq.heappush(t,[-b[k[1]],k[1]])
print(co)

### FIXED CODE ###

import heapq as hq
mod = 10**9+7
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())

def onon():
    n = onem()

    a = l()

    b = l()

    t = []

    for i in range(n):
        if b[i] != a[i]:
            hq.heappush(t,(-b[i],i))
    co = 0
    while t:
        k = hq.heappop(t)
        k = (-k[0],k[1])
        q,w = divmod(k[0] - a[k[1]], b[(k[1] - 1) % n] + b[(k[1] + 1) % n])
        co += q
        if q == 0:
            return -1
        w = a[k[1]] + w
        b[k[1]] = w
        if b[k[1]] != a[k[1]]:
            hq.heappush(t,(-w,k[1]))
    return co
print(onon())
### BUGGY CODE ###

a,b,k = map(int,input().split())
ok = 0
for i in range(a,b+1):
    ok += 1
    if k/2 >= b-a+1:
        print(i)
    else:
        if ok < k+1 or ok > b-a+1-k:
            print(i)

### FIXED CODE ###

a,b,k = map(int,input().split())
if k >= (b-a+1)/2:
    for i in range(a,b+1):
        print(i)
        
else:
    for j in range(a,a+k):
        print(j)
    for l in range(b-k+1,b+1):
        print(l)
### BUGGY CODE ###

import re
n=int(input())
s=input()
ans=0
for i in range(10):
    for j in range(10):
        for k in range(10):
            p=re.compile(r'.*'+str(i)+r'.*'+str(j)+r'.*'+str(k)+r'.*')
            x=p.match(s)
            if x:
                ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
ans=0
for i in range(10):
    for j in range(10):
        for k in range(10):
            x=s.find(str(i))
            y=s.find(str(j),x+1)
            z=s.find(str(k),y+1)
            if(x!=-1 and y!=-1 and z!=-1):
                ans+=1
print(ans)
### BUGGY CODE ###

n,q = map(int,input().split())

s=input()

input_list=[]

for i in range(q):
    input_list.append(list(map(int,input().split())))

for i in range(q):
    temp=0
    for j in range(input_list[i][0]-1,input_list[i][1]-1):
        if s[j]=='A' and s[j+1]=='C':
            temp=temp+1
    print(temp)


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

N = int(input())
A = [int(x) for x in input().split()]
d = []
p = 0
for i in range(N):
    if A[i] in d:
        p = 1
        break
    d.append(A[i])
if p == 0:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
A.sort()
p = 0
for i in range(N-1):
    if A[i] == A[i+1]:
        p = 1
        break
if p == 0:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

from scipy.sparse.csgraph import floyd_warshall
N,X,Y=map(int,input().split())
d=[[10**7 for _ in range(N)] for _ in range(N)]
for a in range(1,N):
    d[a-1][a]=1
    d[a][a-1]=1
d[X-1][Y-1]=1
d[Y-1][X-1]=1

d = floyd_warshall(d)

ans=[0 for _ in range(N)]
for k in range(N):
    for l in range(k+1,N):
        if d[k][l]<N:
            ans[int(d[k][l])]+=1
    
for o in range(N-1):
    print(ans[o+1])


### FIXED CODE ###

N,X,Y=map(int,input().split())

d=[[0 for _ in range(N)] for _ in range(N)]

for i in range(N):
    for j in range(i+1,N):
        d[i][j]=min(abs(i-j),abs(X-1-i)+abs(Y-1-j)+1,abs(X-1-j)+abs(Y-1-i)+1)

ans=[0 for _ in range(N)]
for k in range(N):
    for l in range(k+1,N):
        if d[k][l]<N:
            ans[d[k][l]]+=1
    
for o in range(N-1):
    print(ans[o+1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, W = map(int, input().split())
dp = [[0 for i in range(W + 1)] for j in range(n + 1)]
wv = [[int(x) for x in input().split()] for _ in range(n)]

for i in range(n):
    for j in range(W + 1):
        if j - wv[i][0] >= 0:
            dp[i + 1][j] = max(dp[i][j - wv[i][0]] + wv[i][1], dp[i + 1][j])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(max(dp[-1]))


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, W = map(int, input().split())
dp = [[0 for i in range(W + 1)] for j in range(n + 1)]
wv = [[int(x) for x in input().split()] for _ in range(n)]

for i in range(n):
    for j in range(W + 1):
        if j - wv[i][0] >= 0:
            dp[i + 1][j] = max(dp[i][j - wv[i][0]] + wv[i][1], dp[i + 1][j])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(max(dp[-1]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

import heapq
from collections import deque
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
INF = float('inf')

dists = [[INF]*W for _ in range(H)]
dists[r1][c1] = 0
q = deque([(r1,c1)])
while q:
    y,x = q.popleft()
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if C[ny][nx] == '@': continue
        if dists[ny][nx] <= dists[y][x] + 1: continue
        dists[ny][nx] = dists[y][x] + 1
        q.append((ny,nx))

costs = [INF] * (H*W*4)
costs[(r1*W+c1)*4] = 0
hq = [(r1*W+c1)*4]
heapq.heapify(hq)
while hq:
    v = heapq.heappop(hq)
    cp,d = divmod(v,4)
    cy,x = divmod(cp,W)
    c,y = divmod(cy,H)
    if y==r2 and x==c2:
        print(0--c//K)
        exit()
    for di,(dx,dy) in enumerate(dxy):
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if dists[ny][nx] >= dists[y][x] + 100: continue
        if C[ny][nx] == '@': continue
        if di != d:
            nc = c + (K-c)%K
            if costs[(y*W+x)*4+di] <= nc: continue
            costs[(y*W+x)*4+di] = nc
            heapq.heappush(hq, ((nc*H+y)*W+x)*4+di)
        else:
            if costs[(ny*W+nx)*4+di] <= c+1: continue
            heapq.heappush(hq, (((c+1)*H+ny)*W+nx)*4+di)
print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W,K = map(int,input().split())
r1,c1,r2,c2 = map(lambda x:int(x)-1,input().split())
C = [input() for i in range(H)]

def solve():
    from collections import deque
    dxy = [(0,1),(1,0),(0,-1),(-1,0)]
    INF = float('inf')
    dists = [[INF]*W for _ in range(H)]
    dists[r1][c1] = 0
    q = deque([(r1,c1)])
    while q:
        y,x = q.popleft()
        if y==r2 and x==c2:
            print(dists[y][x])
            exit()
        for dx,dy in dxy:
            for i in range(1,K+1):
                nx,ny = x+dx*i,y+dy*i
                if not 0 <= nx < W: break
                if not 0 <= ny < H: break
                if C[ny][nx] == '@': break
                if dists[ny][nx] <= dists[y][x]: break
                if dists[ny][nx] <= dists[y][x] + 1: continue
                dists[ny][nx] = dists[y][x] + 1
                q.append((ny,nx))
    print(-1)
solve()
### BUGGY CODE ###

import numpy as np
A, B, Q = map(int,input().split())
s_list = np.array([int(input()) for i in range(A)])
t_list = np.array([int(input()) for i in range(B)])
x_list = np.array([int(input()) for i in range(Q)])

def get_dist_to_first_cp(x,li):
    dist1 = li -x
    abs_dist1 = abs(dist1)
    dist_to_first_cp = min(abs_dist1)
    first_cp_num = np.argmin(abs_dist1)
    first_cp_pos = x + dist1[first_cp_num]
    return dist_to_first_cp, first_cp_pos
    


u_list = np.hstack((s_list,t_list))
for x in x_list:
    # shrine first
    dist_to_first_cp, first_cp_pos = get_dist_to_first_cp(x,s_list)
    dist2 = abs(np.array(t_list) - first_cp_pos)
    dist_to_sec_cp = min(dist2)
    ans_s = dist_to_first_cp + dist_to_sec_cp
    # temple first
    dist_to_first_cp, first_cp_pos = get_dist_to_first_cp(x,t_list)
    dist2 = abs(np.array(s_list) - first_cp_pos)
    dist_to_sec_cp = min(dist2)
    
    ans_t = dist_to_first_cp + dist_to_sec_cp

    print(min(ans_s,ans_t))


### FIXED CODE ###

import bisect

A, B, Q = map(int,input().split())
INF = 10**18
s_list = [-INF] +  [int(input()) for i in range(A)] + [INF]
t_list = [-INF] + [int(input()) for i in range(B)] + [INF]
x_list = [int(input()) for i in range(Q)]

for x in x_list:
    
    b, d = bisect.bisect_right(s_list, x), bisect.bisect_right(t_list, x)
    a = b - 1
    c = d - 1 
    ans = INF
    for s in [s_list[a], s_list[b]]:
        for t in [t_list[c], t_list[d]]:
            dist1 = abs(s-x) + abs(t-s)
            dist2 = abs(t-x) + abs(t-s)
            ans = min(ans, dist1,dist2)
    print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
aa=0
for i in range(n):
    for j in range(i+1,n):
        if a[i]==a[j]:
            print('NO')
            aa+=1
            break
        else:
            pass
if aa==0:
    print('YES')
        

### FIXED CODE ###

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

if len(a)==len(s):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

A, B, K = map(int, input().split())

for _ in range(K):
    if A:
        A -= 1
    elif B:
        B -= 1
else:
    print(A, B)



### FIXED CODE ###

A, B, K = map(int, input().split())

if K <= A:
    print(A - K, B)
elif A < K <= A + B:
    print(0, B - (K - A))
else:
    print(0, 0)
### BUGGY CODE ###

N = int(input())
S = [input() for _ in range(N)]
#S = []
ans = 0
for i in range(N):
    dup = False
    if S[i] not in S[:i]:
       ans += 1 
print(ans)



### FIXED CODE ###

N = int(input())
rewards = set()
for _ in range(N):
    rewards.add(input())
print(len(rewards))
### BUGGY CODE ###

n=int(input())
a=[int(_) for _ in input().split()]
l=[a[i]+i for i in range(n)]
r=[i-a[i] for i in range(n)]
ans=0
for i in range(n):ans+=r.count(l[i])
print(ans)

### FIXED CODE ###

import collections
n=int(input())
a=[int(_) for _ in input().split()]
l=[a[i]+i for i in range(n)]
r=[i-a[i] for i in range(n)]
c=collections.Counter(r)
ans=0
for i in range(n):ans+=c[l[i]]
print(ans)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    from itertools import accumulate

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

    B = [0] + A
    B = list(accumulate(B))  # 累積和を格納したリスト作成

    # この問題は長さが1-Nの連続部分の和の最大値を出せというものなので以下の通り
    ans=10**18
    for i in range(1, N):
        snuke=B[i]
        araiguma=sum(A)-B[i]
        ans=min(ans,abs(snuke-araiguma))
    print(ans)
resolve()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    from itertools import accumulate

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

    B = [0] + A
    B = list(accumulate(B))  # 累積和を格納したリスト作成

    ans=10**18
    for i in range(1, N):
        snuke=B[i]
        araiguma=B[N]-B[i]
        ans=min(ans,abs(snuke-araiguma))
    print(ans)
resolve()
### BUGGY CODE ###

list = list(map(int,input().split()))
A = list[0]
B = list[1]
K = list[2]

for num in range(K):
    if A >= 1:
        A -= 1
    elif B >= 1:
        B -= 1
print(A, B)


### FIXED CODE ###

list = list(map(int,input().split()))
A = list[0]
B = list[1]
K = list[2]

if A >= K:
    A = A - K
elif (A + B) >= K:
    B = B - K + A
    A = 0
else:
    A = B = 0

print(A, B)
### BUGGY CODE ###

def main():
    n,k = (int(x) for x in input().split())
    mod = 10**9 + 7
    total = 0
    for i in range(k, n+2):
        l = sum(range(i))
        r = sum(range(n-i+1, n+1))
        total += r-l+1
    print(total%mod)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from itertools import accumulate

def main():
    n,k = (int(x) for x in input().split())
    mod = 10**9 + 7
    left = tuple(accumulate(range(n+1)))
    right = tuple(accumulate(reversed(range(n+1))))
    tot = sum(r-l+1 for l, r in zip(left[k-1:], right[k-1:]))
    print(tot%mod)

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

def main():
  import sys
  input = sys.stdin.readline
  import bisect
  import numpy as np
  n = int(input())
  a = list(map(int,input().split()))
  b = list(map(int,input().split()))
  x = max(max(a),max(b)).bit_length()+1
  b = np.array(b,dtype=np.int32)
  ans = 0
  for i in range(1,x+1):
    d = sorted(b&(1<<i)-1)
    t = 1<<(i-1)
    anstmp = 0
    for j in range(n):
      y = a[j]&(1<<i)-1
      t1 = np.searchsorted(d,t-y)
      t2 = np.searchsorted(d,2*t-y)
      t3 = np.searchsorted(d,3*t-y)
      anstmp += (t2-t1)+(n-t3)
    if anstmp%2:
      ans += t
  print(ans)
main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
x = max(max(a),max(b)).bit_length()+1
a = np.array(a,dtype=np.int32)
b = np.array(b,dtype=np.int32)
ans = 0
for i in range(1,x+1):
  c = a&(1<<i)-1
  d = b&(1<<i)-1
  d.sort()
  t = 1<<(i-1)
  anstmp = 0
  t1 = np.searchsorted(d,t-c).sum()
  t2 = np.searchsorted(d,2*t-c).sum()
  t3 = np.searchsorted(d,3*t-c).sum()
  anstmp += (t2-t1)+(n-t3)
  if anstmp%2:
    ans += t
print(ans)
### BUGGY CODE ###

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

from math import sqrt
from collections import Counter

def is_prime(n):
    if n == 1: return False
    if n == 2: return True
    for i in range(2, int(sqrt(n))+1):
        if n % i == 0: return False
    return True

def prime_factorization(n):
    if is_prime(n):return [n]
    factor = []
    f = 2
    while n > 1:
        if n % f == 0:
            factor.append(f)
            n /= f
        else:
            f += 1
    return factor

p = prime_factorization(P)
c = Counter(p)

l = []
j = []
for k, v in c.items():
    if N <= v:
        l.append(k)
        j.append(v//N)
ans = 1
for i,v in zip(l,j):
    ans *= i**v

print(ans)


### FIXED CODE ###

from collections import Counter

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

def prime_factorization(n):
    factor = []
    f = 2
    while f ** 2 <= n:
        if n % f == 0:
            factor.append(f)
            n //= f
        else:
            f += 1
    if n > 1:
        factor.append(n)
    return factor

p = prime_factorization(P)
c = Counter(p)

l = []
j = []
for k, v in c.items():
    if N <= v:
        l.append(k)
        j.append(v//N)
ans = 1

for i,v in zip(l,j):
    ans *= i**v

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

n = int(input())
h_li = list(map(int, input().split()))
i = 0
count = 0
f = 0
discount = max(h_li)
while True:
    if h_li[i] >= discount:
        count += 1
        h_li[i] -= 1
        while i < len(h_li) - 1:
            if h_li[i + 1] >= discount:
                i += 1
                h_li[i] -= 1
            else:
                break
    if i == len(h_li) - 1:
        i = 0
        discount -= 1
        if max(h_li) == 0:
            f = 1
    else:
        i += 1
    if f == 1:
        break
print(count)


### FIXED CODE ###

n = int(input())
h_li = list(map(int, input().split()))
count = 0
for i in range(100):
    f = 0
    for j in range(n):
        if h_li[j] >= i + 1:
            if f == 0:
                count += 1
                f = 1
        else:
            f = 0
print(count)
### BUGGY CODE ###

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

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
s=1
if 0 in l:
    print(0)
    exit()
for i in l:
    s*=i
    if(s>(10**18)):
        print(-1)
        exit()
print(s)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
a_set = set(a)

# aiの各値の個数を数える
a_dict = {}
for i in a_set:
    a_dict[i] = a.count(i)

ans = 0
for i in range(1, 10 ** 5):
    work = 0
    if (i - 1) in a_set:
        work += a_dict[i - 1]
    if i in a_set:
        work += a_dict[i]
    if (i + 1) in a_set:
        work += a_dict[i + 1]
    ans = max(ans, work)

print(ans)

### FIXED CODE ###

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

# ある値がaに存在するとき、その＋ー1の値を足す
## ans_list[-1]となる場合向けにlistは1個余分に値を設けておく
ans_list = [0] * (10 ** 5 + 2)

for i in a:
    ans_list[i] += 1
    ans_list[i + 1] += 1
    ans_list[i - 1] += 1

ans = max(ans_list)

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


def main():
  x, y, _a, _b, _c = map(int, input().split())
  p = sorted(map(int, input().split()))[-x:]
  q = sorted(map(int, input().split()))[-y:]
  r = sorted(map(int, input().split()), reverse=True)[:x + y]

  arr = sorted(p + q)

  for nc_apple in r:
    apple = arr[0]
    if apple >= nc_apple: break

    arr.pop(0)
    arr.append(nc_apple)

  print(sum(arr))


main()


### FIXED CODE ###


def main():
  x, y, _a, _b, _c = map(int, input().split())
  p = sorted(map(int, input().split()))[-x:]
  q = sorted(map(int, input().split()))[-y:]
  r = sorted(map(int, input().split()), reverse=True)[:x + y]

  arr = sorted(p + q)
  new_num = 0

  for i, nc_apple in enumerate(r):
    if arr[i] >= nc_apple: break

    new_num += nc_apple - arr[i]

  print(sum(arr) + new_num)


main()
### BUGGY CODE ###

import numpy as np
n = int(input())
A = [int(i) * 2 for i in input().split()]

L1 = [[0] * n for _ in range(n)]
for i in range(n):
    if i + 1 <= n-1:
        L1[i][i] = 1
        L1[i][i+1] = 1
    else:
        L1[i][i] = 1
        L1[i][0] = 1
        
L1 = np.linalg.inv(L1)
L2 = np.array(A)
ans = list(np.dot(L1, L2))
print(" ".join([str(int(n)) for n in ans]))

### FIXED CODE ###

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

x1 = sum(A)
for i in range(n):
    if i % 2 != 0:
        x1 -= 2 * A[i]
ans = [x1]
for i in range(n-1):
    tmp = 2 * A[i] - ans[i]
    ans.append(tmp)

print(" ".join([str(int(n)) for n in ans]))
### BUGGY CODE ###

import sys
import copy

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


def get_shortest_steps(S_inner, visited, i_inner, j_inner, steps):
    if i_inner == -1 or i_inner == h or j_inner == -1 or j_inner == w:
        return sys.maxsize
    if visited[i_inner * 20 + j_inner]:
        return sys.maxsize
    if S_inner[i_inner][j_inner] == "#":
        return sys.maxsize
    visited[i_inner * 20 + j_inner] = True
    if shortest_steps_map[i_inner * 20 + j_inner] > steps:
        shortest_steps_map[i_inner * 20 + j_inner] = steps
    get_shortest_steps(S_inner, copy.copy(visited), i_inner + 1, j_inner, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner, j_inner + 1, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner - 1, j_inner, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner, j_inner - 1, steps + 1)
    return


result = -1
for i_outer in range(h):
    for j_outer in range(w):
        visited_outer = [False] * (h * 20 + w + 1)
        shortest_steps_map = [500] * (h * 20 + w + 1)
        get_shortest_steps(S_outer, copy.copy(visited_outer), i_outer, j_outer, 0)

        for i in range(len(shortest_steps_map)):
            if shortest_steps_map[i] == 500:
                shortest_steps_map[i] = 0

        if max(shortest_steps_map) > result:
            result = max(shortest_steps_map)
print(result)


### FIXED CODE ###

import sys
import numpy as np
from collections import deque

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

max_step = 0
for i in range(h):
    for j in range(w):
        largest_step = 0
#        print("start: ", i, j)
        if maze[i][j] == "#":
            continue
        visited = [[False] * w for _ in range(h)]
        distance = [[-1] * w for _ in range(h)]
        plan = deque()
        step = 0
        plan.appendleft((i, j, step))
        distance[i][j] = step
        visited[i][j] = True
        while plan:
            y, x, step = plan.pop()
#            print(" ", x, y, step)
            # if step > largest_step:
            #     largest_step = step
            for next_direction in direction:
                next_y = y + next_direction[0]
                next_x = x + next_direction[1]
                if -1 == next_x or next_x == w or -1 == next_y or next_y == h or maze[next_y][next_x] == "#" or visited[next_y][next_x]:
                    continue
                distance[next_y][next_x] = distance[y][x] + 1
                visited[next_y][next_x] = True
                plan.appendleft((next_y, next_x, step + 1))
#        print(largest_step)
        # if largest_step > max_step:
        #     max_step = largest_step
        max_step = max(max_step, np.max(np.array(distance)))

print(max_step)
### BUGGY CODE ###

n = int(input())
from collections import defaultdict
d = defaultdict(list)
X = []
xl = [tuple(map(int,input().split())) for i in range(n)]
for x,l in xl:
    d[x].append(x-l)
    d[x].append(x+l)
    X.append(x)

X.sort()

i = 1

while len(X)>i:
    x_1 = X[i-1]
    x_2 = X[i]
    min_1 , max_1 = d[x_1]
    min_2 , max_2 = d[x_2]

    if max_1 > min_2:
        if max_2 >= max_1:
            d.pop(x_2, None)
            d.pop(x_2, None)
            X.pop(i)
            i -= 1
        else:
            d.pop(x_1, None)
            d.pop(x_1, None)
            X.pop(i-1)
            i -= 1

    i += 1
ans = len(d)
print(ans)


### FIXED CODE ###

n = int(input())
from collections import defaultdict
d = defaultdict(list)
X = []
xl = [tuple(map(int,input().split())) for i in range(n)]
for x,l in xl:
    d[x].append(x-l)
    d[x].append(x+l)
    X.append(x)

X.sort()


n_remove = 0


for i in range(1,n):
    x_1 = X[i-1]
    x_2 = X[i]
    min_1 , max_1 = d[x_1]
    min_2 , max_2 = d[x_2]

    if max_1 > min_2:
        n_remove += 1
        if max_2 >= max_1:
            d[x_2] = d[x_1]
            X[i] = X[i-1]


ans = n - n_remove
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
d = []
for _ in range(M):
    b, c = map(int, input().split())
    d += [c] * b

ans = []
i_a = 0
i_d = 0
MAX_D = len(d)

A.sort(reverse=True)
d.sort(reverse=True)

while len(ans) < N:
    if i_d < MAX_D and A[i_a] < d[i_d]:
            ans.append(d[i_d])
            i_d += 1
    else:
            ans.append(A[i_a])
            i_a += 1

print(sum(ans))
    

### FIXED CODE ###

N, M = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

X = [list(map(int, input().split())) for _ in range(M)]
X.sort(key=lambda x: x[1], reverse=True)
num_cnt = [x[0] for x in X]
val_cnt = [x[1] for x in X]

idx = 0
cnt = 0
ans = 0
cum = 0
for i in range(min(N, sum(num_cnt))):
  if val_cnt[idx] <= a[i]:
    print(sum(a[i:]) + ans)
    break
  ans += val_cnt[idx]
  cnt += 1
  cum += 1
  if num_cnt[idx] == cnt:
    idx += 1
    cnt = 0
  if cum == N:
    print(ans)
    break
else:
  print(sum(a[sum(num_cnt):] + [val_cnt[i] * num_cnt[i] for i in range(M)]))