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

import sys
I = lambda:map(int,sys.stdin.readline().split())
pr = lambda x:sys.stdout.write(f'{x}\n')
sys.setrecursionlimit(2000000001)
 
def solve(n,ar,k,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if dp[x] != -1: return dp[x]
	dp[x] = min([*map(lambda i:ab(ar[x]-ar[i])+solve(n,ar,k,dp,i), range(x+1,mn(n,x+k+1)))])
	return dp[x]
 
def main():
	(n,k), ar = [[*map(int,s.split())] for s in [*open(0)]]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,ar,k,dp,0))
 
main()

### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	# t = [ for i in range(x+1,mn(n,x+k+1))]
	t = map(lambda i:ab(ar[x]-ar[i])+solve(n,k,ar,dp,i), range(x+1,mn(n,x+k+1)))
	dp[x] = reduce(lambda a,b : a if a < b else b,t)
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,k,ar,dp,0))

main()
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/submissions/4011183

S,T = input(), input()
S,T = list(map(lambda x: ord(x)-97, S)), list(map(lambda x: ord(x)-97, T))

# print(S,T)

dp = [ [0] * (len(T)+1)] + [[0]+[None]*len(T) for _ in range(len(S))]

for i,s in enumerate(S):
    for j,t in enumerate(T):
        dp[i+1][j+1] = max(
                dp[i][j+1], 
                dp[i+1][j],
                dp[i][j] + (s==t)
                )
res = []

x,y = len(S), len(T)

while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]:
        x -= 1
    elif dp[x][y] == dp[x][y-1]:
        y -= 1
    else:
        x -= 1
        y -= 1
        res.append(chr(S[x]+97))
print(''.join(reversed(res)))





### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/submissions/4011183

S,T = input(), input()
S,T = list(map(lambda x: ord(x)-97, S)), list(map(lambda x: ord(x)-97, T))

# print(S,T)

dp = [ [0] * (len(T)+1)] + [[0]+[None]*len(T) for _ in range(len(S))]

for i,s in enumerate(S):
    for j,t in enumerate(T):
        dp[i+1][j+1] = max(
                dp[i][j+1], 
                dp[i+1][j],
                dp[i][j] + (s==t)
                )
res = []

x,y = len(S), len(T)

while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]:
        x -= 1
    elif dp[x][y] == dp[x][y-1]:
        y -= 1
    else:
        x -= 1
        y -= 1
        res.append(chr(S[x]+97))
print(''.join(reversed(res)))
### BUGGY CODE ###

S = input()
N = len(S)

mod = 10 ** 9 + 7
A, AB, ABC, ALL = 0, 0, 0, 1
for s in S:
    if s == "A":
        A += ALL

    if s == "B":
        AB += A

    if s == "C":
        ABC += AB

    if s == "?":
        ABC = ABC * 3 + AB
        AB = AB * 3 + A
        A = A * 3 + ALL
        ALL *= 3

print(ABC % mod)


### FIXED CODE ###

S = input()
N = len(S)

mod = 10 ** 9 + 7
A, AB, ABC, ALL = 0, 0, 0, 1
for s in S:
    if s == "A":
        A += ALL

    if s == "B":
        AB += A

    if s == "C":
        ABC += AB

    if s == "?":
        ABC = (ABC * 3 + AB) % mod
        AB = (AB * 3 + A) % mod
        A = (A * 3 + ALL) % mod
        ALL = (ALL * 3) % mod

print(ABC % mod)
### BUGGY CODE ###


N=int(input())
A=list(map(int,input().split()))
from math import sqrt
s=set()
A.sort()
a=0
t=0
if A[0]!=1:
    for i in A:
        if i in s:
            if t==i:
                a-=1
                t=0
            continue
        s.add(i)
        for j in range(2,int(sqrt(i)+1.5)):
            if i%j:
                continue
            if j in s:
                break
            if i//j in s:
                break
        else:
            t=i
            a+=1
else:
    if N>1 and A[1]==1:
        a=0
    else:
        a=1
print(a)

### FIXED CODE ###

from math import sqrt
from time import perf_counter
t0=perf_counter()
N=int(input())
A=list(map(int,input().split()))
A.sort()
def main():
    a=0
    s=set()
    t=0
    if A[0]!=1:
        for i in A:
            if i in s:
                if t==i:
                    a-=1
                    t=0
                continue
            for j in range(2,int(sqrt(i)+1.1)):
                if i%j:
                    continue
                if j in s:
                    break
                if i//j in s:
                    break
            else:
                t=i
                a+=1
            s.add(i)
            if perf_counter()-t0>1.9:
                a=N
                break                
    else:
        if N>1 and A[1]==1:
            a=0
        else:
            a=1
    print(a)
main()
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
  a = int(input())
  A.append(a)
  
A2 = sorted(A)
mx1 = max(A)
mx2 = A2[-2]

for i in range(N):
  if i == A.index(mx1):
    print(mx2)
  else:
    print(mx1)

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
  a = int(input())
  A.append(a)
  
A2 = sorted(A)
mx1 = A2[-1]
mx2 = A2[-2]
ind = A.index(mx1)

for i in range(N):
  if i != ind:
    print(mx1)
  else:
    print(mx2)
### BUGGY CODE ###

N = int(input())
A = tuple(map(int,input().split()))
S = ''

for i in range(N):
    n = A.index(i+1)
    S = S + str(n+1) + ' '

print(S)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
O = [0] * N

for i , a  in enumerate(A): #リストAのインデックスiと値a
    O[a-1] = i+1

print(*O)
### BUGGY CODE ###

import math
n=int(input())
s=0
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      s += math.gcd(i,math.gcd(j,k))
print(s)

### FIXED CODE ###

import math
  
def main():
  k=int(input())
  cur=0
  for a in range(1,k+1):
    for b in range(1,k+1):
      for c in range(1,k+1):
        cur+=math.gcd(math.gcd(a,b),c)
        
  return cur
print(main())
### BUGGY CODE ###

n,m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m):
    index = a.index(max(a))
    a[index] //= 2
print(sum(a))


### FIXED CODE ###

import heapq
n,m = map(int, input().split())
a = list(map(int, input().split()))
hq = []
for j in range(n):
    aa = a[j] * -1
    heapq.heappush(hq, aa)
for i in range(m):
    maxim = heapq.heappop(hq) * -1
    maxim //= 2
    maxim *= -1
    heapq.heappush(hq, maxim)
print(-1 * sum(hq))
### BUGGY CODE ###

H, W = map(int, input().split())
grid = [input() for _ in range(H)]
ans = 0
vert = [[0] * W for _ in range(H)]; hori = [[0] * W for _ in range(H)];
for i in range(H):
    for j in range(W):
        if grid[i][j] == '.':
            hori[i][j] = hori[i][j-1] + 1 if j > 0 else 1
    for j in range(W-2, -1, -1):
        if grid[i][j] == '.' and grid[i][j+1] == '.':
            hori[i][j] = hori[i][j+1] 
for j in range(W):
    for i in range(H):
        if grid[i][j] == '.':
            vert[i][j] = vert[i-1][j] + 1 if i > 0 else 1
    for i in range(H-2, -1, -1):
        if grid[i][j] == '.' and grid[i+1][j] == '.':
            vert[i][j] = vert[i+1][j]
for i in range(H):
    for j in range(W):
        if grid[i][j] == '.':
            ans = max(ans, hori[i][j] + vert[i][j] - 1)
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
grid = [input() for _ in range(H)]
ans = 0
vert = [[0] * W for _ in range(H)]; hori = [[0] * W for _ in range(H)];
for i in range(H):
    for j in range(W):
        if grid[i][j] == '.':
            hori[i][j] = hori[i][j-1] + 1 if j > 0 else 1
    for j in range(W-2, -1, -1):
        if grid[i][j] == '.' and grid[i][j+1] == '.':
            hori[i][j] = hori[i][j+1] 
for j in range(W):
    for i in range(H):
        if grid[i][j] == '.':
            vert[i][j] = vert[i-1][j] + 1 if i > 0 else 1
    for i in range(H-2, -1, -1):
        if grid[i][j] == '.' and grid[i+1][j] == '.':
            vert[i][j] = vert[i+1][j]
for i in range(H):
    for j in range(W):
        if grid[i][j] == '.':
            ans = max(ans, hori[i][j] + vert[i][j] - 1)
print(ans)
### BUGGY CODE ###

MAX = 1005
n = int(input())
dp = [[0 for j in range(MAX)] for i in range(MAX)]
X = Y = ""
len_X = len_X = 0
for _ in range(n):
    X = input()
    Y = input()
    len_X = len(X)
    len_Y = len(Y)

    for i in range(len_X):
        for j in range(len_Y):
            # dp[i + 1][j + 1] = dp[i][j] + 1 if X[i] == Y[j] else max(dp[i][j + 1], dp[i + 1][j])
            if X[i] == Y[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
    print(dp[len_X][len_Y])

### FIXED CODE ###

for _ in range(int(input())):
    a = input()
    b = input()
    if len(a) < len(b):
        a, b = b, a
    indices = []
    for cb in b:
        bgn_idx = 0
        for i, cur_idx in enumerate(indices):
            chr_idx = a.find(cb, bgn_idx) + 1
            if not chr_idx:
                break
            if chr_idx < cur_idx:
                indices[i] = chr_idx
            bgn_idx = cur_idx
        else:
            chr_idx = a.find(cb, bgn_idx) + 1
            if chr_idx:
                indices.append(chr_idx)
    print(len(indices))
### BUGGY CODE ###

import bisect
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    A = [int(input())]
    for k in range(N-1):
        t = int(input())
        if A[0] >= t:
            A = [t] + A
        else:
            A[bisect.bisect_left(A,t)-1] = t
    print(len(A))

if __name__ == '__main__':
    main()



### FIXED CODE ###

import bisect
import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N = int(input())
    A = deque([int(input())])
    for k in range(N-1):
        t = int(input())
        if A[0] >= t:
            A.appendleft(t)
        else:
            A[bisect.bisect_left(A,t)-1] = t
    print(len(A))

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

h,w,k = map(int, input().split())
sx,sy,gx,gy = map(lambda x: int(x)-1, input().split())
board = [list(map(lambda x: int(x=="."), input())) for i in range(h)]
inf = 1<<30
DP = [[inf for j in range(w)] for i in range(h)]
DP[sx][sy] = 0

from collections import deque
que = deque([(sx,sy)])

dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
while que:
    x,y = que.popleft()
    for dx,dy in dxdy:
        nx,ny = x,y
        for i in range(k):
            nx += dx
            ny += dy
            if not(0<=nx<h and 0<=ny<w and board[nx][ny] and DP[nx][ny] >= DP[x][y]+1):
                break
            if DP[nx][ny] > DP[x][y]+1:
                DP[nx][ny] = DP[x][y]+1
            que.append((nx,ny))
ans = DP[gx][gy]
if ans == inf:
    ans = -1
print(ans)


### FIXED CODE ###

h,w,k = map(int, input().split())
sx,sy,gx,gy = map(lambda x: int(x)-1, input().split())
board = [list(map(lambda x: int(x=="."), input())) for i in range(h)]
inf = 1<<30
DP = [[inf for j in range(w)] for i in range(h)]
DP[sx][sy] = 0

from collections import deque
que = deque([(sx,sy)])

dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
while que:
    x,y = que.popleft()
    for dx,dy in dxdy:
        nx,ny = x,y
        for i in range(k):
            nx += dx
            ny += dy
            if not(0<=nx<h and 0<=ny<w and board[nx][ny] and DP[nx][ny] >= DP[x][y]+1):
                break
            # コストが変わらない場合は無視か...
            if DP[nx][ny] == DP[x][y]+1:
                continue
            DP[nx][ny] = DP[x][y]+1
            que.append((nx,ny))
ans = DP[gx][gy]
if ans == inf:
    ans = -1
print(ans)
### BUGGY CODE ###

import itertools

N = int(input())
A = list(map(int, input().split()))
array = list(itertools.combinations(range(N), 2))
count = 0

for x in array:
    if (A[x[1]] + A[x[0]]) == (x[1] - x[0]):
        count += 1
print(count)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
count = 0
l_array = []
r_array = []
for i, X in enumerate(A):
    l_array.append(i + X)
    r_array.append(i - X)

counter = Counter(r_array)

for x in l_array:
    count += counter.get(x, 0)
print(count)
### BUGGY CODE ###

import numpy as np
h,w = map(int,input().split())
ans = [[0]*(w+2) for _ in range(h+2)]
grid = []
grid.append(['#']*(w+2))
for _ in range(h):
    s = list(input())
    grid.append(['#'] + s + ['#'])
grid.append(['#']*(w+2))
for i in range(1,h+1):
    for j in range(0,w+2):
        if grid[i][j] == '#':
            if j >= 1:
                for k in range(j-start):
                    ans[i][start+k] += j-start
            start = j + 1
for j in range(1,w+1):
    for i in range(0,h+2):
        if grid[i][j] == '#':
            if i >= 1:
                for k in range(i-start):
                    ans[start+k][j] += i-start
            start = i + 1
print(np.amax(ans)-1)

### FIXED CODE ###

h,w = map(int,input().split())
ans = [[0]*(w+2) for _ in range(h+2)]
grid = []
grid.append(['#']*(w+2))
for _ in range(h):
    s = list(input())
    grid.append(['#'] + s + ['#'])
grid.append(['#']*(w+2))
for i in range(1,h+1):
    for j in range(0,w+2):
        if grid[i][j] == '#':
            if j >= 1:
                for k in range(j-start):
                    ans[i][start+k] += j-start
            start = j + 1
for j in range(1,w+1):
    for i in range(0,h+2):
        if grid[i][j] == '#':
            if i >= 1:
                for k in range(i-start):
                    ans[start+k][j] += i-start
            start = i + 1
print(max(list(map(lambda x:max(x),ans)))-1)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

x, y, z, k = map(int, readline().split())
a = list(map(int, readline().split()))
b = list(map(int, readline().split()))
c = list(map(int, read().split()))
ab = [0] * x * y
for i, aa in enumerate(a):
    for j, bb in enumerate(b):
        ab[i * y + j] = aa + bb
ab = sorted(ab, reverse=True)[:k]
c = sorted(c, reverse=True)[:k]
ans = [0] * (k ** 2)
for i, abab in enumerate(ab):
    for j, cc in enumerate(c):
        ans[i * k + j] = abab + cc
ans.sort(reverse=True)
print('\n'.join(map(str, ans[:k])))


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

x, y, z, k = map(int, readline().split())
a = list(map(int, readline().split()))
b = list(map(int, readline().split()))
c = list(map(int, read().split()))
ab = [0] * x * y
for i, aa in enumerate(a):
    for j, bb in enumerate(b):
        ab[i * y + j] = aa + bb
ab = sorted(ab, reverse=True)[:k]
c = sorted(c, reverse=True)
ans = [0] * k * z
for i, abab in enumerate(ab):
    for j, cc in enumerate(c):
        ans[i * z + j] = abab + cc
ans.sort(reverse=True)
print('\n'.join(map(str, ans[:k])))
### BUGGY CODE ###

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

mod=10**9+7
sum_all=[]
for i in range(N-1):
    for j in range(i+1,N):
        sum_all.append((A[i]%mod)*(A[j]%mod))

answer=sum(sum_all)%mod
print(answer)

### FIXED CODE ###

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

mod=10**9+7

B=[0]
for i in range(1,N+1):
    B.append(A[i-1]+B[i-1])

ans=0
for i in range(N-1):
    ans+=A[i]*(B[N]-B[i+1])
    ans%=mod

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

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

ans = 1
for a in a_list:
  ans *= a
 
if ans > pow(10, 18):
  print(-1)
else:
  print(ans)


### FIXED CODE ###

import sys

n = int(input())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)

if a_list[-1] == 0:
  print(0)
  sys.exit()

if a_list[0] > 1000000000000000000:
  print(-1)
  sys.exit()

ans = 1
for a in a_list:
  ans *= a

  if ans > 1000000000000000000:
    print(-1)
    sys.exit()

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

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n = int(input())
ns = defaultdict(set)
uv2e = {}
for i in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
    
m = int(input())
uvs = [None]*m
for i in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    uvs[i] = (u,v)
    
from queue import deque    
def bfs(start):
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = u
                q.appendleft(v)
    return seen
ans = 0
def dfs(l, s):
    if len(l)==m:
        global ans
        val = pow(2, n-1-len(s)) * pow(-1, sum(l))
        ans += val
#         print(val, sum(l), ans)
        return
    dfs(l + [0], s)
    i = len(l)
    u,v = uvs[i]
    seen = bfs(u)
    ss = set()
    z = v
    while z!=u:
        z1 = seen[z]
        ss.add(uv2e[z,z1])
        z = z1
    dfs(l + [1], s|ss)
dfs([], set())
# ans = pow(2,n-1) - ans
print(ans)

### FIXED CODE ###

# ABC152F

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")





from collections import defaultdict
from queue import deque
import itertools
import functools
def find(start,goal):
    q = deque([start])
    seen = [None] * n
    seen[start] = -1
    while q:
        u = q.pop()
        d = seen[u]
        if u==goal:
            break
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = u
                q.appendleft(v)
    u = goal
    es = []
    while True:
        t = (min(u, seen[u]), max(u, seen[u]))
        es.append(t)
        if seen[u]==start:
            break
        u = seen[u]
    return set(es)

n = int(input())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
ans = 0
m = int(input())
paths = [None] * m
for i in range(m):
    u, v = map(int, input().split())
    paths[i] = find(u-1,v-1)

ans = 0

def dfs(ind, s, ans):
    if len(ind)==m:
        if True in ind:
            ans += 2**(n-1-len(s)) * (-1)**(sum(ind)+1)
        return ans
    ans = dfs(ind + [True], s | paths[len(ind)], ans)
    ans = dfs(ind + [False], s, ans)
    return ans
        
# for ind in itertools.product(*[(False, True) for _ in range(m)]):
#     num = sum(ind)+1
#     if num==1:
#         continue
#     c = 2**(n - 1 - len(functools.reduce(lambda x,y: x|y, (paths[i] for i in range(m) if ind[i]), set())))
#     ans += (-1)**num * c
ans = dfs([], set(), 0)
print(2**(n-1) - ans)
### BUGGY CODE ###

N = int(input())
nums = [int(e) for e in input().split()]
nums.sort()
t=1
ans = 1
for i in range(0,9):
    t = t*10
t+=7
if(N%2)==1:
    if(nums.count(0) == 1):
        for i in range(2,N,2):
            if(nums.count(i))==2:
                continue
            else:
                print('0')
                break
        else:
            for k in range(0,N//2):
                ans = ans*2
            print(ans%(t))
    else:
        print('0')
else:
    for i in range(1,N,2):
        if(nums.count(i))==2:
            continue
        else:
            print('0')
            break
    else:
        for k in range(0,N//2):
            ans = ans*2
        print(ans%(t))

### FIXED CODE ###

N = int(input())
nums = [int(e) for e in input().split()]
nums.sort()
t=1
ans = 1
t = 10**9
t+=7
i=1
k=0
if(N%2)==1:
    if(nums.count(0) == 1):
        while(i<N):
            if nums[i] == nums[i+1]:
                i+=2
                ans = (ans *2)%t
                continue
            else:
                print('0')
                break
        else:
            print(ans)
    else:
        print('0')
else:
    while(k<N):
        if nums[k] == nums[k+1]:
            k += 2
            ans = (ans * 2)%t
            continue
        else:
            print('0')
            break
    else:
        print(ans)
### BUGGY CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


def main():
    n = int(input())
    As = list(map(int, input().split()))

    ans = 0
    for i in range(n):
        if factorization(As[i])[0][0] == 2:
            ans += factorization(As[i])[0][1]
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    As = list(map(int, input().split()))

    ans = 0
    for i in range(n):
        temp = As[i]
        if temp % 2 == 0:
            cnt = 0
            while temp % 2 == 0:
                cnt += 1
                temp //= 2
            ans += cnt

    print(ans)


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

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


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


BC = [list(map(int,input().split())) for _ in range(M)]

for b,c in BC:
    count=0
    A.sort()
    for (i,a) in enumerate(A):
        if count==b or c<a:
            break
        else:
            A[i]=c
            count+=1
    
suma=0
for i in A:
    suma+=i

print(suma)

### FIXED CODE ###


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


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

A.sort()

BC = [list(map(int,input().split())) for _ in range(M)]

BC.sort(key=lambda x:x[1],reverse=True)

for b,c in BC:
    A.extend([c]*b)
    if len(A)>2*N:
        break

A.sort(reverse=True)
suma=0
#for i in A:
#    suma+=i

print(sum(A[:N]))
### BUGGY CODE ###

import copy
s=[]
i=0
n=int(input())
while i!=n:
    s.append(int(input()))
    i+=1
maxx=max(s)
g=s.count(maxx)
i=0

#print(g)
while i!=n:

    a=s[0]
    del s[0]
    if maxx==a and g<2:
        print(max(s))
    else:
        print(maxx)


    s.append(a)
    i+=1

### FIXED CODE ###

import copy
s=[]
i=0
n=int(input())
while i!=n:
    s.append(int(input()))
    i+=1
maxx=max(s)
g=s.count(maxx)
i=0
j=0

#print(g)
while i!=n:
    a = s[j]
    if maxx == a and g < 2:
        a=s[j]
        del s[j]
        print(max(s))
        s.append(a)
    else:
        print(maxx)
        j+=1

    i+=1
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
  Dn = [None for _ in range(Q+1)]
  for i in range(Q):
    Dn[i] = int(readl().rstrip())
  Dn[Q] = 10**10
  ans = []

  for s,t,x in sorted(STX,key=lambda x:x[2]):
    l = r = bisect_left(Dn,s-x)
    t -= x
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans,Q


if __name__ == "__main__":
  ans,n = main()
  for _ in range(n):
    print(heappop(ans)[1])    


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

n = int(input())

s_list = []

for i in range(n):
    s = str(input())
    if not(s in s_list):
        s_list.append(s)
print(len(s_list))

### FIXED CODE ###

n = int(input())

s_list = []

for i in range(n):
    s = str(input())
    s_list.append(s)
s_list = list(set(s_list))
print(len(s_list))