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

from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(i, n-1-i, j, n-1-j) for i in range(n) for j in range(n)]
exist = [1]*(n**2)


def to_idx(p):
    return divmod(p, n)


def to_v(i, j):
    return i*n+j


def generate_v2(v):
    i, j = to_idx(v)
    if 0 < i:
        yield v-n
    if i < n-1:
        yield v+n
    if 0 < j:
        yield v-1
    if j < n-1:
        yield v+1


def bfs(init_v):
    next_v = deque([init_v])
    exist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        for v2 in generate_v2(v):
            if cost[v2] <= cost[v]+exist[v]:
                continue
            cost[v2] = cost[v]+exist[v]
            next_v.append(v2)


ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)

### FIXED CODE ###

from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(i, n-1-i, j, n-1-j) for i in range(n) for j in range(n)]
exist = [1]*(n**2)


def to_idx(p):
    return divmod(p, n)


def to_v(i, j):
    return i*n+j


def bfs(init_v):
    next_v = deque([init_v])
    exist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = to_idx(v)
        if 0 < i:
            v2 = v-n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if i < n-1:
            v2 = v+n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if 0 < j:
            v2 = v-1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if j < n-1:
            v2 = v+1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
h_list = list(map(int, input().split()))
costs = [0] * n
costs[1] = abs(h_list[0] - h_list[1])
start = 0
for i in range(2, n):
    tmp = []
    v = h_list[i]
    if i-k >= 0:
        start = i-k
    else:
        start = 0
    for l in range(start, i):
        tmp.append(abs(v - h_list[l])+costs[l])
        if abs(v - h_list[l]) == 0:
            break
    costs[i] = min(tmp)
print(costs[-1])


### FIXED CODE ###

n, k = map(int, input().split())
h_list = list(map(int, input().split()))
costs = [0] * n
costs[1] = abs(h_list[0] - h_list[1])
start = 0
for i in range(2, n):
    tmp = []
    v = h_list[i]
    start = max(0, i-k)
    costs[i] = min(abs(v - h_j) + c for h_j, c in zip(h_list[start:i], costs[start:i]))
    # for l in range(start, i):
    #     tmp.append(abs(v - h_list[l])+costs[l])
    #     if abs(v - h_list[l]) == 0:
    #         break
    # costs[i] = min(tmp)
print(costs[-1])
### BUGGY CODE ###

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

for item in s:
    if(item not in bag):
        bag.append(item)

print(len(bag))

### FIXED CODE ###

import collections

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

ans = collections.Counter(s)
print(len(ans))
### BUGGY CODE ###

#coding: utf-8
N, Q = map(int, input().split())
S = input()
for i in range(Q):
    q1, q2 = map(int, input().split())
    qs = S[q1-1: q2]
    print(qs.count("AC"))

### FIXED CODE ###

#coding: utf-8
N, Q = map(int, input().split())
S = input()
T = [0]
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        T.append(T[i] + 1)
    else:
        T.append(T[i])
for j in range(Q):
    l, r = map(int, input().split())
    print(T[r-1] - T[l-1])
### BUGGY CODE ###

n,k = map(int,input().split())
ls = []
b_num = 0

for i in range(n):
    a,b = [int(i) for i in input().split()]
    if b_num <= k:
        tmp = [a] * b
        ls.extend(tmp)
        ls.sort()
        b_num += b
    else:
        if(a <= ls[-1]):
            tmp = [a] * b
            ls.extend(tmp)
            ls.sort()
        
print(ls[k-1])

### FIXED CODE ###

n,k = map(int,input().split())
ls = []

for i in range(n):
    a,b = [int(i) for i in input().split()]
    ls.append([a,b])

ls.sort()
for a,b in ls:
    if b >= k:
        print(a)
        break
    else:
        k -= b
### BUGGY CODE ###

import numpy as np
from sys import stdin
input = stdin.readline
N = int(input())
A = list(map(int, input().split()))
A = np.array(A)
number = np.zeros(N, dtype = int)
for i in range(N):
  number[A[i]-1] += 1
total = 0
for k in range(N):
  tmp = number[k]
  total += tmp * (tmp-1) // 2
for j in range(N):
  print(total - number[A[j]-1] + 1)


### FIXED CODE ###

import numpy as np
from sys import stdin
input = stdin.readline
N = int(input())
A = list(map(int, input().split()))
number = np.zeros(N, dtype = int)
total = 0

dic = {}
a = sorted(A)
now_key = a[0]
value = 1
dic[now_key] = 1
for i in range(1,N):
  if a[i] == now_key:
    value += 1
  else:
    dic[now_key] = value
    if value >= 2:
      total += value * (value-1) // 2
    now_key = a[i]
    value = 1
dic[now_key] = value
if value >= 2:
  total += value * (value-1)//2
for j in A:
  print(total - dic[j] + 1)
### BUGGY CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(k):
    C = [0] * n
    for i in range(n):
        a = A[i]
        l = max(0, i - a)
        r = min(n, i + a + 1)
        C[l] += 1
        if r < n:
            C[r] -= 1
    r = 0
    for i in range(n):
        r += C[i]
        A[i] = r
print(" ".join(map(str, A)))

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    _max = max
    _min = min
    for _ in range(k):
        C = [0] * n
        i = 0
        for a in A:
            l = _max(0, i - a)
            r = _min(n, i + a + 1)
            C[l] += 1
            if r < n:
                C[r] -= 1
            i += 1
        r = 0
        for i in range(n):
            r += C[i]
            A[i] = r
        if A == [n] * n:
            break
    print(" ".join(map(str, A)))
main()
### BUGGY CODE ###

import bisect

n = int(input())
a_li = list(map(int, input().split()))
b_li = list(map(int, input().split()))
c_li = list(map(int, input().split()))

b_li.sort()
c_li.sort()

check_li = [0]*(n+10)

for i in range(len(b_li)):
    s = bisect.bisect_right(c_li, b_li[i])
    check_li[i] = len(c_li[s:])
    

ans = 0

for i in a_li:
    s = bisect.bisect_right(b_li, i)
    ans += sum(check_li[s:])
        
print(ans)

### FIXED CODE ###

import bisect

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

a.sort()
b.sort()
c.sort()

ans = 0

for middle in b:
    tmp1 = bisect.bisect_left(a, middle)
    tmp2 = bisect.bisect_right(c, middle)
    ans += tmp1 * (n - tmp2)

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

import math
from itertools import product
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())
S = [input() for _ in range(h)]


distance = [[math.inf for _ in range(w)] for _ in range(h)]
distance[ch][cw] = 0
queue = deque([(ch, cw)])

while queue:
    i, j = queue.popleft()
    adj = []
    if i > 0 and S[i - 1][j] == '.':
        adj.append((i-1, j))
    if j > 0 and S[i][j - 1] == '.':
        adj.append((i, j - 1))
    if i < h-1 and S[i + 1][j] == '.':
        adj.append((i+1, j))
    if j < w-1 and S[i][j+1] == '.':
        adj.append((i, j+1))
    for u, v in adj:
        if distance[u][v] > distance[i][j]:
            distance[u][v] = distance[i][j]
            queue.appendleft((u,v))

    warp = product(range(max(i-2, 0), min(i+3, h)),
                   range(max(j-2, 0), min(j+3, w)))
    for x, y in warp:
        if (x,y) != (i,j) and (x,y) not in adj and S[x][y] == '.' and distance[x][y] > distance[i][j] + 1:
            distance[x][y] = distance[i][j] + 1
            queue.append((x,y))

print(distance[dh][dw] if distance[dh][dw] != math.inf else -1)



### FIXED CODE ###

import math
from itertools import product
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())
S = [input() for _ in range(h)]


distance = [[math.inf for _ in range(w)] for _ in range(h)]
distance[ch][cw] = 0
queue = deque([(ch, cw)])
pathes = {(0, -1), (-1, 0), (0, 1), (1, 0)}
warps = set(product(range(-2, 3), range(-2, 3))) - {(0, 0)} - pathes

while queue:
    i, j = queue.popleft()
    for pi, pj in pathes:
        u, v = i+pi, j+pj
        if 0 <= u < h and 0 <= v < w and S[u][v] == '.' and distance[u][v] > distance[i][j]:
            distance[u][v] = distance[i][j]
            queue.appendleft((u, v))

    for wi, wj in warps:
        x, y = i + wi, j + wj
        if 0 <= x < h and 0 <= y < w and S[x][y] == '.' and distance[x][y] > distance[i][j] + 1:
            distance[x][y] = distance[i][j] + 1
            queue.append((x, y))

print(distance[dh][dw] if distance[dh][dw] != math.inf else -1)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
score=0
mod=10**9+7
for i in range(0,n-1):
  for j in range(i+1,n):
    score+=a[i]*a[j]
print(score%mod)
    

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b=sum(a)
score=0
for i in range(len(a)):
  b -= a[i]
  score+=a[i]*b
  
print(score%(10**9+7))
### BUGGY CODE ###

N = int(input())
import math

A = []
B = []
for i in range(N):
  a, b = map(int,input().split())
  A.append(int(a))
  B.append(int(b))

count=0
for i in range(N):
  #print(i,A[N-1-i],B[N-1-i])
  if A[N-1-i]%B[N-1-i]==0:
    n=0
  elif A[N-1-i]>B[N-1-i]:
    n=math.ceil(A[N-1-i]/B[N-1-i])*B[N-1-i]-A[N-1-i]
  elif A[N-1-i]<B[N-1-i]:
    n= B[N-1-i]-A[N-1-i]
  count +=n
  #print(n)
  for j in range(N-i):
    A[j]+=n
  #print(A) 
  #print(B) 
print(count)

### FIXED CODE ###

N = int(input())
import math

A = []
B = []
for i in range(N):
  a, b = map(int,input().split())
  A.append(int(a))
  B.append(int(b))

n=0
for i in range(N):
  #print(i,A[N-1-i]+n,B[N-1-i]+n)
  
  if (A[N-1-i]+n)%(B[N-1-i])==0:
    n+=0
  elif A[N-1-i]+n>B[N-1-i]:
    n+=math.ceil((A[N-1-i]+n)/B[N-1-i])*(B[N-1-i])-A[N-1-i]-n
    #print('!',n,math.ceil((A[N-1-i]+n)/(B[N-1-i])))
  elif A[N-1-i]+n<B[N-1-i]:
    n+= B[N-1-i]-A[N-1-i]-n
  #print(n)  
    
  #count +=n
  #print(n)
  #for j in range(N-i):
    #A[j]+=n

print(n)
### BUGGY CODE ###

x, y, a, b, c = map(int, input().split())
Lista = sorted(list(map(int, input().split())), reverse = True)
Listb = sorted(list(map(int, input().split())), reverse = True)
Listc = sorted(list(map(int, input().split())), reverse = True)
if x < a:
    del Lista[x:a]
if y < b:
    del Listb[y:b]
while len(Listc) > 0:
    if Lista[-1] < Listb[-1]:
        if Lista[-1] < Listc[0]:
            Lista[-1] = Listc[0]
            Lista = sorted(Lista, reverse = True)
            del Listc[0]
        else:
            break
    else:
        if Listb[-1] < Listc[0]:
            Listb[-1] = Listc[0]
            Listb = sorted(Listb, reverse = True)
            del Listc[0]
        else:
            break
print(sum(Lista) + sum(Listb))

### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
Lista = sorted(list(map(int, input().split())), reverse = True)
Listb = sorted(list(map(int, input().split())), reverse = True)
Listc = sorted(list(map(int, input().split())), reverse = True)
if x < a:
    del Lista[x : a]
if y < b:
    del Listb[y : b]
List = sorted(Lista + Listb, reverse = True)
i = -1
for n in range(min(x + y, c)):
    if List[-n-1] < Listc[n]:
        i = n
    else:
        break
del List[x + y - i -1 : x + y]
del Listc[i + 1 : c]
print(sum(List) + sum(Listc))
### BUGGY CODE ###

N = int(input())
#S = [input() for i in range(N)]
S=[]
ans_list = []
temp_ans = 1
ans = 0
iscalc = [True]*N

for i in range(N):
    S.append(''.join(sorted(list(input()))))

for i in range(N):
    if iscalc[i]:
        for j in range(i+1,N):
            if S[i]==S[j]:
                temp_ans += 1
                iscalc[j]=False
        ans_list.append(temp_ans)
        temp_ans=1


for a in ans_list:
    ans += a*(a-1)/2

print(round(ans))

### FIXED CODE ###

N = int(input())
#S = [input() for i in range(N)]
S=[]
ans_dic={}
temp_ans = 1
ans = 0

for i in range(N):
    temp = sorted(list(input()))
    temp = ''.join(temp)
    #S.append(''.join(temp))
    #alpha_dic[temp[0]].append(i) 
    if temp in ans_dic:
        ans_dic[temp] += 1
    else:
        ans_dic[temp] = 1
    
for key,value in ans_dic.items():
    ans += value*(value-1)/2

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

N = int(input())
ABCs = [
  sorted(map(int, input().split()))
  for _ in range(3)
]

def table(As, Bs):
  ib = 0
  result = []
  for a in As:
    while ib < len(Bs) and Bs[ib] <= a:
      ib += 1
    result.append(ib)
  return result


def f(ABCs):
  AB = table(ABCs[0], ABCs[1])
  BC = table(ABCs[1], ABCs[2])
  return sum(
    N - BC[j]
    for i, ab in enumerate(AB)
    for j in range(ab, N)
  )
  
print(f(ABCs))

### FIXED CODE ###

N = int(input())
As, Bs, Cs = [
  sorted(map(int, input().split()))
  for _ in range(3)
]

from bisect import *

def sums():
  for b in Bs:
  	yield bisect_left(As, b) * (N - bisect_right(Cs, b))

print(sum(sums()))
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline

R,C,K = map(int,input().split())

tb = np.zeros((R+1,C+1),dtype=np.int32)
dp = np.zeros((C+1,4),dtype=np.int64)
prev = np.zeros(C+1,dtype=np.int64)

for i in range(K):
    r,c,v = map(int,input().split())
    tb[r][c] = v

for i in range(1,R+1):
    for j in range(1,C+1):
        for k in range(4):
            dp[j][k] = dp[j-1][k]
            if k > 0:
                dp[j][k] = max(dp[j][k],dp[j-1][k-1]+tb[i][j])
            if k == 0:
                dp[j][k] = max(dp[j][k],prev[j])
            elif k == 1:
                dp[j][k] = max(dp[j][k],prev[j]+tb[i][j])
    prev = np.max(dp,axis=1)

print(prev[C])


### FIXED CODE ###

import sys
input = sys.stdin.readline

R,C,K = map(int,input().split())

dp = [[0]*4 for i in range(C+1)]
prev = [0]*(C+1)
tb = [[0]*(C+1) for i in range(R+1)]

for i in range(K):
    r,c,v = map(int,input().split())
    tb[r][c] = v

for i in range(1,R+1):
    for j in range(1,C+1):
        pmx = 0
        for k in range(4):
            mx = dp[j-1][k]
            if k > 0:
                mx = max(mx,dp[j-1][k-1]+tb[i][j])
            if k == 0:
                mx = max(mx,prev[j])
            elif k == 1:
                mx = max(mx,prev[j]+tb[i][j])
            dp[j][k] = mx
            pmx = max(pmx,mx)
        prev[j] = pmx

print(prev[C])
### BUGGY CODE ###

k,s = map(int, input().split())

count = 0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if(i+j+l == s):
                count += 1
                
print(count)

### FIXED CODE ###

k,s = map(int, input().split())

count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-(x+y)
        if (0 <= z <= k):
            count += 1
                
print(count)
### BUGGY CODE ###

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

count = 0
while n > 0:
    for i in range(a):
        count += 1
        n -= 1
        if n == 0:
            break
    if n != 0:
        for j in range(b):
            n -= 1
            if n == 0:
                break
print(count)

### FIXED CODE ###

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

x = n//(a+b)
y = n%(a+b)

if y <= a:
    print(x*a + y)
else:
    print(x*a + a)
### BUGGY CODE ###

def main():
  h, n = map(int, input().split())
  l = []
  for i in range(n):
    a, b = map(int, input().split())
    l.append([a, b])

  dp = [10 ** 9 for i in range(h+1)]

  for i in range(h+1):
    for j in range(n):
      if l[j][0] >= i:
        if dp[i] > l[j][1]:
          dp[i] = l[j][1]
      else:
        if dp[i] > l[j][1] + dp[i-l[j][0]]:
          dp[i] = l[j][1] + dp[i-l[j][0]]

  print(dp[h])


main()


### FIXED CODE ###

def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for a, b in AB:
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print(min(dp[H:]))


main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
 
answer_list = []
for i in range(N):
    counter = 0
    i_num = N - i
    for j in range(i_num, N+1, i_num):
        if j in answer_list:
            counter += 1
    if counter % 2 == A[i_num - 1]:
        continue
    else:
        answer_list.append(i_num)
print(len(answer_list))
if answer_list:
    print(" ".join(map(str, answer_list)))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
flag = [-1] * (N+1)
answer_list = []
for i in range(N):
    counter = 0
    i_num = N - i
    for j in range(i_num, N+1, i_num):
        if j == i_num:
            continue
        else:
            if flag[j] == 1:
                counter += 1
    if counter % 2 == A[i_num - 1]:
        flag[i_num] = 0
    else:
        flag[i_num] = 1
        answer_list.append(i_num)
print(len(answer_list))
if answer_list:
    print(" ".join(map(str, answer_list)))
### BUGGY CODE ###

N = int(input())
A = map(int, input().split())
ans = 1
for a in A:
    ans *= a

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

### FIXED CODE ###

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

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

ans = 1
for a in A:
    ans *= a
    if ans > 10**18:
        print(-1)
        break
else:
    print(ans)
### BUGGY CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX

for left_i, left_p in enumerate(x_dots):
    for right_i, right_p in enumerate(x_dots[left_i:]):
        for under_i, under_p in enumerate(y_dots):
            for top_i, top_p in enumerate(y_dots[under_i:]):
                counter = 0
                for x, y in dots:
                    if left_p[0] <= x and x <= right_p[0] and under_p[1] <= y and y <= top_p[1]:
                        counter += 1
                
                if counter >= K:
                    area = (top_p[1]-under_p[1]) * (right_p[0]-left_p[0])
                    ans = min(ans, area)


print(ans)



### FIXED CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(s) for s in input().split()]
S = [[0] * 20 for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(20):
        S[i][j] = S[i-1][j] + (1 if A[i-1] & (1 << j) else 0)

ans = 0
i = 0
for j in range(N):
    while not all(S[j + 1][v] - S[i][v] < 2 for v in range(20)):
        i += 1
    ans += j + 1 - i
print(ans)


### FIXED CODE ###

N = int(input())
A = [int(s) for s in input().split()]
S = [[0] * 20 for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(20):
        S[i][j] = S[i-1][j] + (1 if A[i-1] & (1 << j) else 0)

ans = 0
i = 0
for j in range(N):
    while not all(S[j + 1][v] - S[i][v] < 2 for v in range(20)):
        i += 1
    ans += j + 1 - i
print(ans)
### BUGGY CODE ###

def main():
    k, s = input().split()
    k, s = int(k), int(s)

    count = 0
    for x in range(k+1):
        for y in range(k+1):
            for z in range(k+1):
                if x + y + z == s:
                    count += 1

    print(count)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    k, s = input().split()
    k, s = int(k), int(s)

    count = 0
    for x in range(k+1):

        if k*2 + x < s:
            continue

        for y in range(k+1):
            if 0 <= (s - x - y) <= k:
                count += 1

    print(count)


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

def next(X,Xs,Y,Ys):
    Z = (X+Y)//2
    print('{}'.format(Z))
    Zs = input()
    if Zs == 'Vacant':
        sys.exit()
    if (Xs == Zs and (Z-X)%2 == 1)\
    or (Xs != Zs and (Z-X)%2 == 0):
        Y, Ys = Z, Zs
    else:
        X, Xs = Z, Zs
        return X,Xs,Y,Ys

import sys

N = int(input())
print('0\n')
xs = input()
if xs == 'Vacant':
    sys.exit()
print('{}\n'.format(N-1))
ys = input()
if ys == 'Vacant':
    sys.exit()
x, y = 0, N-1
while True:
    x,xs,y,ys = next(x,xs,y,ys)

### FIXED CODE ###

def nexts(X,Xs,Y,Ys):
    Z = (X+Y)//2
    print('{}\n'.format(Z))
    Zs = input()
    if Zs == 'Vacant':
        sys.exit()
    if (Xs == Zs and (Z-X)%2 == 1)\
    or (Xs != Zs and (Z-X)%2 == 0):
        Y, Ys = Z, Zs
    else:
        X, Xs = Z, Zs
    return X,Xs,Y,Ys

import sys

N = int(input())
print('0\n')
xs = input()
if xs == 'Vacant':
    sys.exit()
print('{}\n'.format(N-1))
ys = input()
if ys == 'Vacant':
    sys.exit()
x, y = 0, N-1
while True:
    x,xs,y,ys = nexts(x,xs,y,ys)
### BUGGY CODE ###

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

S = []
for _ in range(M):
    D = list(map(int, input().split()))
    S.append(D)

#S.sort(key=lambda x:x[0])
S.sort()

first = []

for tmp in S:
    if tmp[0]!=1:
        break
    first.append(tmp[1])

for tmp in S:
    if tmp[1] == N and tmp[0] in first:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

### FIXED CODE ###

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

S = []
for _ in range(M):
    D = list(map(int, input().split()))
    S.append(D)

set1=set()
set2=set()

for tmp in S:
    if tmp[0]==1:
        set1.add(tmp[1])
    if tmp[1]==N:
        set2.add(tmp[0])

if len(set1&set2) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")
### BUGGY CODE ###

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

ans = 0
test = 0
while n > test:
    test += a + b
    if n >= test:
        ans += a
    else:
        x = test - n
        if x > b:
            ans += a - (x - b)
        else:
            ans += a

print(ans)

### FIXED CODE ###

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

q = n // (a + b)

x = a * q

w = n % (a + b)
if w >= a:
    y = a
else:
    y = w

ans = x + y

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

def qsort(a):
    if len(a) in (0,1):
        return a
    else:
        p = a[-1]
        l=[x for x in a[:-1] if x >=p]
        r=[x for x in a[:-1] if x <p]
        return qsort(l) + [p] + qsort(r)

def get_num():
    return list(map(int,input().split(' ')))

def main():
    n,m=get_num()
    card = get_num()
    for i in range(m):
        b,c=get_num()
        for i in range(b):
            card.append(c)
    card=qsort(card)
    print(sum(card[:n]))

if __name__=='__main__':
    main()

### FIXED CODE ###

import heapq as hq

def get_num():
    return list(map(int,input().split(' ')))

def main():
    n,m = get_num()
    card = get_num()
    card_sum=sum(card)
    hq.heapify(card)
    d_set=[]
    d=[]
    for i in range(m):
        b,c=get_num()
        hq.heappush(d_set,(-c,b))
    for i in range(m):
        if len(d) ==n:
            break
        cnt = hq.heappop(d_set)
        for i in range(cnt[1]):
            d.append(-cnt[0])
            if len(d)==n:
                break
    for i in range(len(d)):
        c_min=hq.heappop(card)
        d_max=d[i]
        if c_min>=d_max:
            break
        else:
            card_sum += (d_max-c_min)
    print(card_sum)
main()