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

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

dis = 0
done = [A[0]]
not_done = A[1:N]

while True:
    min_d = 1e6
    for a in done:
        for b in range(len(not_done)):
            if a>b:
                d = min(abs(a-not_done[b]), abs(a-not_done[b]-20))
            else:
                d = min(abs(a-not_done[b]), abs(a-not_done[b]+20))
            min_d = min(d, min_d)
            min_idx = b
    dis += min_d
    done.append(not_done.pop(min_idx))
    if len(not_done) ==0:
        break
print(dis)


### FIXED CODE ###

import numpy as np

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

A.append(K+A[0])
l = 0
for i in range(N):
    l = max(l, A[i+1]-A[i])
print(K-l)
### BUGGY CODE ###

n = int(input())
a = list(input().split())
ans = int(a[0])
tmp = 0
for  i in range(1,n):
    if '0' in a:
        ans = 0
        break
    ans = ans * int(a[i])

check = 10**18
if ans <= check:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
check = 10**18

a = sorted(a)
ans = a[0]
tmp = 0


for i in range(n-1,0,-1):
    ans = ans * a[i]
    if ans > check:
        tmp  = 1
        break
    elif a[0] == 0:
        tmp = 2
        break

if tmp == 1:
    print('-1')
elif tmp == 0:
    print(ans)
elif tmp == 2:
    print('0')
### BUGGY CODE ###

import sys
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

input = sys.stdin.buffer.readline

N, M, S, T = map(int, input().split())
S -= 1
T -= 1
UVAB = np.array([tuple(map(int, input().split())) for _ in range(M)]).T
UVAB[:2] -= 1

yen_matrix = csr_matrix((UVAB[2], (UVAB[0], UVAB[1])), shape=(N, N))
yen_path = dijkstra(yen_matrix, indices=S, directed=False).astype(int)

snuuk_matrix = csr_matrix((UVAB[3], (UVAB[0], UVAB[1])), shape=(N, N))
snuuk_path = dijkstra(snuuk_matrix, indices=T, directed=False).astype(int)

path = yen_path + snuuk_path
path_acc = np.minimum.accumulate(path[::-1])[::-1]
print(*(10 ** 15 - path_acc), sep='\n')


### FIXED CODE ###

import sys
import networkx as nx

input = sys.stdin.buffer.readline

MAX = 10 ** 15
N, M, S, T = map(int, input().split())

G = nx.Graph()
G.add_nodes_from(range(1, N + 1))
for _ in range(M):
    u, v, a, b = map(int, input().split())
    G.add_edge(u, v, yen=a, snuuk=b)

yen_path = nx.single_source_dijkstra_path_length(G, S, weight='yen')
snuuk_path = nx.single_source_dijkstra_path_length(G, T, weight='snuuk')

ans = [MAX] * (N + 1)
for i in range(N, 0, -1):
    ans[i - 1] = min(ans[i], yen_path[i] + snuuk_path[i])
for x in ans[:N]:
    print(MAX - x)
### BUGGY CODE ###

n,k=map(int,input().split())
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
a=list(map(int,input().split()))
a.sort()
b=a[::-1]
#print(a,b)
ans=0
for i in range(k-1,n):
    ans+=(a[i]-b[i])*(combination(i, k-1, mod=10**9+7))
print(ans%(10**9+7))


### FIXED CODE ###

n,k=map(int,input().split())
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

mod=10**9+7
f=[1]
for i in range(n):f+=[f[-1]*(i+1)%mod]
def comb(a,b):
    return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod

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

import collections

S = input()
l = [0]
for i in range(1,len(S)+1):
  tmp = int(S[-i:])
  l.append(tmp%2019)

c = collections.Counter(l)

rlt = 0
for k in c:
  rlt += c[k]*(c[k]-1)//2

print(rlt)

### FIXED CODE ###

import collections
 
S = input()
l = [0]
a = 0
b = 1

for i in range(1,len(S)+1):
  a = (a+int(S[-i])*b)%2019
  l.append(a)
  b = (b*10)%2019
  

c = collections.Counter(l)
 
rlt = 0
for k in c:
  rlt += c[k]*(c[k]-1)//2

print(rlt)
### BUGGY CODE ###

def gcd(a,b):
    return b if not a%b else gcd(b,a%b)
def lcm(a,b):
    return (a*b)//gcd(a,b)

def main():
    n = int(input())
    A=[int(i) for i in input().split()]
    res = 0
    m = 0
    for i in range(n):
        l_m = A[0]
        r_m = A[n-1]
        if(i!=0 and i!=n-1):
            for j in range(1,i):
                l_m = gcd(l_m,A[j])

            for j in range(n-1,i,-1):
                r_m = gcd(r_m,A[j])
            res = max(res,gcd(l_m,r_m))
        else:
            if(i==0):
                for j in range(1,n-1):
                    r_m = gcd(r_m,A[j])
                res = max(res,r_m)
            else:
                for j in range(1,n-1):
                    l_m = gcd(l_m,A[j])
                res = max(res,l_m)
    print(res)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict,deque
import math
def gcd(a,b):
    return b if not a%b else gcd(b,a%b)
def lcm(a,b):
    return (a*b)//gcd(a,b)

def main():
    n = int(input())
    A=[int(i) for i in input().split()]
    res = 0
    m = 0
    l_g = [0,A[0]]
    r_g = [0,A[-1]]
    ind = 2
    for i in A[1:]:
        l_g.append(gcd(l_g[ind-1],i))
        ind += 1
    ind = 2
    for i in range(n-2,-1,-1):
        r_g.append(gcd(r_g[ind-1],A[i]))
        ind += 1
    r_g = r_g[::-1]
    r_g = r_g[1:]

    for i in range(len(r_g)):
        if(r_g[i]!=0 and l_g[i]!=0):
            res = max(res, gcd(r_g[i],l_g[i]))
        else:
            res = max(r_g[i],l_g[i],res)
    print(res)

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

n,m=map(int,input().split())
first=[]
second=[]
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        first.append(bi)
    elif bi==n:
        second.append(ai)
ans="IMPOSSIBLE"
if len(first)!=0 and len(second)!=0:
    for i in first:
        if i in second:
            ans="POSSIBLE"
            break
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
check=[0]*n
ans="IMPOSSIBLE"
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        if check[bi-1]==1:
            ans="POSSIBLE"
            break
        else:
            check[bi-1]+=1
    elif bi==n:
        if check[ai-1]==1:
            ans="POSSIBLE"
            break
        else:
            check[ai-1]+=1
print(ans)
### BUGGY CODE ###

N = int(input())

AList = list(map(int, input().split()))

count = 0
for i in range(0, N):
    for q in range(i, N):
        count += int(AList[i] ^ AList[q])
print(count % (10 ** 9 + 7))

### FIXED CODE ###

import numpy as np

mod = 10 ** 9 + 7

N = int(input())
 
AList = np.array(input().split(), dtype=np.int64)
count = 0
for i in range(60):
    Plus = np.count_nonzero(AList >> i & 1)
    count += 2 ** i * (Plus * (N - Plus))
print(count % mod)
### BUGGY CODE ###

n,q = map(int,input().split())
imos = []
for i in range(n):
    s,t,x = map(int,input().split())
    if t-x > 0:
        imos.append((max(s-x,0),x))
        imos.append((t-x,-x))
ans = set()
j = 0
l = len(imos)
imos.sort()
for i in range(q):
    d = int(input())
    while j < l:
        now,stop = imos[j]
        if now > d:
            break
        if stop > 0:
            ans.add(stop)
        else:
            ans.remove(-stop)
        j += 1
    if ans:
        print(min(ans))
    else:
        print(-1)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,q = map(int,input().split())
imos = []
for i in range(n):
    s,t,x = map(int,input().split())
    imos.append((s-x,x))
    imos.append((t-x,-x))
ans = set()
j = 0
for i in range(q):
    d = int(input())
    imos.append((d,1e100))
imos.sort()
m = 1e100
flag = False
for t,stop in imos:
    if stop == 1e100:
        if ans:
            if not flag:
                m = min(ans)
                flag = True
            print(m)
        else:
            print(-1)
    elif stop > 0:
        ans.add(stop)
        if stop < m:
            m = stop
            flag = True
    else:
        ans.remove(-stop)
        if m == -stop:flag = False
### BUGGY CODE ###

n,k=map(int,input().split())
H=list(map(int,input().split()))
A=[float("inf")]*n
A[0]=0
for i in range(1,n):
  for j in range(1,min(i+1,k+1)):
    a=A[i-j]+abs(H[i]-H[i-j]) 
    A[i]=min(A[i],a)
print(A[n-1])

### FIXED CODE ###

def solve():
  n,k=map(int,input().split())
  H=list(map(int,input().split()))
  A=[0]*n
  for i in range(1,n):
    A[i]=min(A[i-j]+abs(H[i]-H[i-j]) for j in range(1,min(i+1,k+1)))
  return A[n-1]
print(solve())
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod
MOD = 10 ** 9 + 7

N = int(input())
X = list(input())

def popcount(n):
    ret = 0
    while n > 0:
        if n % 2 == 1:
            ret += 1
        n //= 2
    return ret

ones = X.count('1')
A_1 = 0
A_2 = 0
d = 1
for a in X[::-1]:
    if ones == 1:
        A_2 += (int(a) * d) % (ones + 1)
    else:
        A_1 += (int(a) * d) % (ones - 1)
        A_2 += (int(a) * d) % (ones + 1)
    d *= 2

for i in range(N):
    ans = 1
    total = ones
    sumA = 0
    if X[i] == '0':
        total += 1
        sumA = A_2 + my_pow(2, N - i - 1, total)
    else:
        total -= 1
        if total != 0:
            sumA = A_1 - my_pow(2, N - i - 1, total)
    if total == 0:
        print(0)
        continue
    n = sumA % total
    while n != 0:
        n = n % popcount(n)
        ans += 1
    print(ans)
    


### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N = int(input())
X = input()

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt
def f(n):
    cnt = 0
    while n != 0:
        n = n % popcount(n)
        cnt += 1
    return cnt

ones = X.count('1')
MOD1 = ones + 1
MOD2 = ones - 1
pow1 = [1] * (len(X) + 1)
pow2 = [0] * (len(X) + 1)
if MOD2 != 0:
    pow1[0] = 1
    pow2[0] = 1
    for i in range(1, len(X) + 1):
        pow1[i] = (pow1[i - 1] * 2) % MOD1
        pow2[i] = (pow2[i - 1] * 2) % MOD2
else:
    for i in range(1, len(X) + 1):
        pow1[i] = (pow1[i - 1] * 2) % MOD1

X1 = 0
X2 = 0
for i in range(N):
    if X[i] == '1':
        X1 += pow1[N - i - 1]
        X2 += pow2[N - i - 1]
X1 %= MOD1
if MOD2 != 0:
    X2 %= MOD2

for i in range(N):
    d = N - i - 1
    if X[i] == '0':
        x = (X1 + pow1[d]) % MOD1
        print(f(x) + 1)
    else:
        if MOD2 != 0:
            x = (X2 - pow2[d]) % MOD2
            print(f(x) + 1)
        else:
            print(0)
### BUGGY CODE ###

# D - AtCoder Express 2

N, M, Q = map(int, input().split())
G = [[0] * (N+1) for _ in range(N+1)]

for _ in range(M):
    L, R = map(int, input().split())
    G[L][R] += 1

for i in range(N+1):
    for j in range(N):
        G[i][j+1] += G[i][j]

for _ in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p, q+1):
        ans += G[i][q] - G[i][p-1]
    print(ans)

### FIXED CODE ###

# D - AtCoder Express 2

N, M, Q = map(int, input().split())
G = [[0] * (N+1) for _ in range(N+1)]

for _ in range(M):
    L, R = map(int, input().split())
    G[L][R] += 1

for i in range(N+1):
    for j in range(N):
        G[i][j+1] += G[i][j]

for _ in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p, q+1):
        ans += G[i][q] - G[i][p-1]
    print(ans)
### BUGGY CODE ###

class Prim():
    def __init__(self,N):
        import collections
        self.N = N
        self.edge = collections.defaultdict(list)
    def add(self,a,b,cost):
        self.edge[a].append((b,cost))
        self.edge[b].append((a,cost))
    def cut_edge(self,start=0):
        import heapq,collections
        #new_edge = collections.defaultdict(list)
        edge_sum = 0
        node_flag = [False for _ in range(self.N)]
        node_flag[start] = True
        q = []
        for to,cost in self.edge[start]:
            heapq.heappush(q,(cost,start,to))
        while q :
            c,s,t = heapq.heappop(q)
            if node_flag[t] is False:
                #new_edge[s].append((t,c))
                edge_sum += c
                node_flag[t] = True
                for to,cost in self.edge[t]:
                    if not node_flag[to]:
                        heapq.heappush(q,(cost,t,to))
        return edge_sum

N = int(input())
graph = Prim(N)
xy = [list(map(int,input().split())) for _ in range(N)]
nx = [(i,xy[i][0]) for i in range(N)]
ny = [(i,xy[i][1]) for i in range(N)]
nx.sort(key=lambda x:x[1])
ny.sort(key=lambda x:x[1])

for i in range(N-1):
    prev_n,prev_x = nx[i]
    next_n,next_x = nx[i+1]
    graph.add(prev_n,next_n,next_x-prev_x)
    prev_n,prev_y = ny[i]
    next_n,next_y = ny[i+1]
    graph.add(prev_n,next_n,next_y-prev_y)
print(graph.cut_edge())

### FIXED CODE ###

class Prim():
    def __init__(self,N):
        import collections
        self.N = N
        self.edge = collections.defaultdict(list)
    def add(self,a,b,cost):
        self.edge[a].append((b,cost))
        self.edge[b].append((a,cost))
    def cut_edge(self,start=0):
        import heapq,collections
        #new_edge = collections.defaultdict(list)
        edge_sum = 0
        node_flag = [False for _ in range(self.N)]
        node_flag[start] = True
        q = []
        for to,cost in self.edge[start]:
            heapq.heappush(q,(cost,start,to))
        while q :
            c,s,t = heapq.heappop(q)
            if node_flag[t] is False:
                #new_edge[s].append((t,c))
                edge_sum += c
                node_flag[t] = True
                for to,cost in self.edge[t]:
                    if not node_flag[to]:
                        heapq.heappush(q,(cost,t,to))
        return edge_sum

N = int(input())
graph = Prim(N)
xy = [list(map(int,input().split())) for _ in range(N)]
nx = [(i,xy[i][0]) for i in range(N)]
ny = [(i,xy[i][1]) for i in range(N)]
nx.sort(key=lambda x:x[1])
ny.sort(key=lambda x:x[1])

for i in range(N-1):
    prev_n,prev_x = nx[i]
    next_n,next_x = nx[i+1]
    graph.add(prev_n,next_n,next_x-prev_x)
    prev_n,prev_y = ny[i]
    next_n,next_y = ny[i+1]
    graph.add(prev_n,next_n,next_y-prev_y)
print(graph.cut_edge())
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q
for i in range(Q):
    B[i], C[i] = map(int,input().split())

S = [0]*Q
for i in range(Q):
    for j in range(N):
        if A[j] == B[i]:
            A[j] = C[i]
    S[i] = sum(A)

for i in range(Q):
    print(S[i])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q
for i in range(Q):
    B[i], C[i] = map(int,input().split())
    
num = [0]*100000
for i in range(len(A)):
    num[A[i]-1] += 1
    
S =[sum(A)]
for i in range(Q):
    S.append(S[i]+(C[i]-B[i])*num[B[i]-1])
    num[C[i]-1] += num[B[i]-1]
    num[B[i]-1] = 0
 
S.pop(0)    
for i in range(Q):
    print(S[i])
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
a.sort()
b.sort()
c.sort()
ans = 0
for i in range(n):
  for j in range(n):
    if a[i] < b[j]:
      for k in range(n):
        if b[j] < c[k]:
          ans += n-k
          break
    j += 1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

ans = 0
a = tuple(a); b = tuple(b); c = tuple(c)
a = sorted(a)
b = sorted(b,reverse=True)
c = sorted(c)

import bisect
chk_b = [0]*n
for i,bi in enumerate(b):
  y = bisect.bisect_right(c, bi)
  chk_b[i] = max(0,n-y) + chk_b[i-1]
  
chk_b = tuple(chk_b)
b = sorted(b)
for i in a:
  x = bisect.bisect_right(b, i)
  if x <= n-1:
    ans += chk_b[n-1-x]
print(ans)
### BUGGY CODE ###

def trisum(n):
    return n * (n + 1) // 2


def calc(S):
    t = []
    i = S.find('><')
    while i != -1:
        t += [S[:i + 1]]
        S = S[i + 1:]
        i = S.find('><')
    t += [S]
    result = 0
    for u in t:
        nu = len(u)
        l = 0
        for j in range(nu):
            if u[j] == '>':
                break
            l += 1
        result += trisum(max(l, nu - l)) + trisum(min(l, nu - l) - 1)
    return result


S = input()
print(calc(S))

### FIXED CODE ###

def binSearch(N, A, key):
    left = 0
    right = N - 1
    memo = [-1 for _ in range(N)]
    k = (left + right) // 2
    while True:
        if memo[k] == -1:
            memo[k] = 1 if key(A[k]) else 0
        if memo[k] == 1:
            right = k
        else:
            left = k
        _k = (left + right) // 2
        if _k == k:
            if memo[left] == -1:
                memo[left] = key(A[left])
            if memo[right] == -1:
                memo[right] = key(A[right])
            if memo[right] == 0 or memo[left] == 1:
                return -1
            else:
                return right
        else:
            k = _k


def trisum(n):
    return n * (n + 1) // 2


def calc(S):
    t = []
    b = 0
    i = S.find('><', b)
    result = 0
    while i != -1:
        if i - b == 0:
            result += 0
        elif i - b == 1:
            result += 1
        else:
            t += [S[b:i + 1]]
        b = i + 1
        i = S.find('><', b)
    t += [S[b:]]
    for u in t:
        nu = len(u)
        l = binSearch(nu, u, lambda c: c == '>')
        if l != -1:
            result += trisum(max(l, nu - l)) + trisum(min(l, nu - l) - 1)
        else:
            result += trisum(nu)
    return result


S = input()
print(calc(S))
### BUGGY CODE ###

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

for k in range(0, K):
    A = work
    work = [0] * N
    for i in range(0, N):
        for j in range(1, A[i] + 1):
            index = i - j
            if (index >= 0):
                work[index] += 1
        work[i] += 1
        for j in range(1, A[i] + 1):
            index = i + j
            if (index < N):
                work[i + j] += 1

print(" ".join([str(item) for item in work]))

### FIXED CODE ###

import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))
### BUGGY CODE ###

N,M = map(int,input().split())
cities = [[] for _ in range(N)]
order_p = []
order_y = []
for _ in range(M):
    p,y = map(int,input().split())
    cities[p-1].append(y)
    order_p.append(p)
    order_y.append(y)
#print(cities)
for pref in range(N):
    cities[pref].sort()
#print(cities)
for key_pref, key_year in zip(order_p,order_y):
    print(str(key_pref).zfill(6)+str((cities[key_pref-1].index(key_year))+1).zfill(6))




### FIXED CODE ###

N,M=map(int, input().split())
py=[list(map(int, input().split())) for _ in range(M)]
cnt=[0]*(N+1)
ids={}
for p,y in sorted(py, key=lambda x: x[1]):
	cnt[p] += 1
	ids[y] = "%06d%06d" % (p, cnt[p])
for _,y in py:
	print(ids[y])
### BUGGY CODE ###

from itertools import permutations
inf=10**9
n,m,R=map(int,input().split())
r=list(map(int,input().split()))
rr=permutations(r,R)
dis=[[inf]*n for _ in range(n)]
for i in range(m):
	a,b,c=map(int,input().split())
	dis[a-1][b-1]=c
	dis[b-1][a-1]=c
for i in range(n):
	for j in range(n):
		for k in range(n):
			dis[j][k]=min(dis[j][i]+dis[i][k],dis[j][k])
ans=10**12
for x in rr:
	e=0
	for i in range(R-1):
		e+=dis[x[i+1]-1][x[i]-1]
	ans=min(ans,e)
print(ans)


### FIXED CODE ###

from itertools import permutations
inf=10**9
n,m,R=map(int,input().split())
r=list(map(int,input().split()))
rr=permutations(r,R)
dis=[[inf]*n for _ in range(n)]
for i in range(m):
	a,b,c=map(int,input().split())
	dis[a-1][b-1]=c
	dis[b-1][a-1]=c
for i in range(n):
	for j in range(n):
		for k in range(n):
			dis[j][k]=min(dis[j][i]+dis[i][k],dis[j][k])
ans=10**12
for x in rr:
	e=0
	for i in range(R-1):
		e+=dis[x[i+1]-1][x[i]-1]
	ans=min(ans,e)
print(ans)
### BUGGY CODE ###

F_list = [1,1] + [None]*43

def fibo(n):
  F=F_list[n]
  if n==0 or n==1: return F
  F = fibo(n-1)+fibo(n-2)
  F_list[n]=F
  return F


n = int(input())

print(fibo(n))

### FIXED CODE ###

F =[1,1] + [0 for i in range(44)]

n = int(input())

for i in range(2,n+1):
  F[i]=F[i-1]+F[i-2]

print(F[n])
### BUGGY CODE ###

A,B,K = map(int,input().split())
box = []
for i in range(A,B+1):
	box.append(i)
for j in range(len(box)):
	if box[j] in box[:K]:
		print(box[j])
	elif box[j] in box[-K:]:
		print(box[j])

### FIXED CODE ###

a,b,k = map(int,input().split())
ans = []
for i in range(a,a+k):
    if i <= b:
        ans.append(i)
if b-a+1 >= 2*k:
    for j in range(b-k+1,b+1):
        ans.append(j)
else:
    for j in range(a+k,b+1):
        if j <= b:
            ans.append(j)

for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()

C_list = [0] * N
for i in range(M):
  [B, C] = list(map(int, input().split(' ')))
  if C_list[0] > C:
    continue
  else:
    for k in range(B):
      if C < card_list[k] or C_list[k] >= C:
        break
      else:
        C_list[k] = C
  C_list.sort()
  
C_list.sort()

ans = 0
count = 0
for i in range(N):
  if card_list[-1] > C_list[-1]:
    ans += card_list.pop()
    count += 1
  else:
    ans += C_list.pop()
    count += 1
      
print(ans) 

### FIXED CODE ###

[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()
compare_list = []

for i in range(M):
  (B, C) = list(map(int, input().split(' ')))
  compare_list.append((C,B))
    
compare_list.sort()

ans = 0
for i in range(N):
  if compare_list == []:
    ans += sum(card_list[i:])
    break
  if card_list[-1] > compare_list[-1][0]:
    ans += card_list.pop()
  elif compare_list[-1][1] > 0:
    ans += compare_list[-1][0]
    tmp = compare_list.pop()
    a = tmp[0]
    b = tmp[1]
    if b != 1:
      compare_list.append((a,b-1)) 
      
print(ans)